✦ LIBER ✦

How fast can one compute the permanent of circulant matrices?

✍ Scribed by A. Bernasconi; B. Codenotti; V. Crespi; G. Resta

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 665 KB
Volume: 292
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(99)00012-9

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we address the problem of computing the permanent of (0,1)-circulant matrices. We investigate structural properties of circulant matrices, showing that (i) if they are dense enough, then they contain large arbitrary submatrices, and (ii) if they are very sparse, then they are not too ``far'' from convertible matrices. Building upon (ii), we then develop an ecient algorithm, which allows us to compute permanents of very sparse circulants of size up to 200.

📜 SIMILAR VOLUMES

On the parity of permanents of circulant

On the parity of permanents of circulant matrices

✍ Giovanni Sburlati 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 120 KB

On the number of different permanents of

On the number of different permanents of some sparse (0,1)-circulant matrices

✍ Giovanni Resta; Giovanni Sburlati 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 235 KB

Starting from known results about the number of possible values for the permanents of (0, 1)-circulant matrices with three nonzero entries per row, and whose dimension n is prime, we prove corresponding results for n power of a prime, n product of two distinct primes, and n = 2 • 3 h . Supported by

On the values of permanents of (0, 

On the values of permanents of (0, 1) circulant matrices with three ones per row

✍ Giovanni Sburlati 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 250 KB