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

The number of values Per(\(M_{n}\)) is investigated, where \(M_{n}\) are \(n\times n\) (0,1)-circulant matrices with three nonzero entries per row and Per(\(M_{n}\)) is the permanent of \(M_{n}\). \textit{A. Bernasconi}, \textit{B. Codenotti}, \textit{V. Crespi} and \textit{G. Resta} [Linear Algebra Appl. 292, 15--37 (1999; Zbl 0933.65045)] have shown that for any prime \(n>2\) the number \(N_{\text{tot}}(n)\) of all possible values of Per(\(M_{n}\)) verifies the inequality \(N_{\text{tot}}\leq [n/6]\). In the present paper a general inequality is obtained for any odd \(n\). Then particular inequalities are derived for the cases \(n=p^{h}\), \(n=2^{h}\), \(n=pq\), \(n=2p\) and \(n=2\cdot3^{h}\) where \(p\) and \(q\) are distinct odd primes and \(h\in\mathbb{N}\). Some experimental results show that these particular inequalities are tight for \(n\leq121\). A few open questions are emphasized. Similar inequalities are experimentally verified for \(n\times n\) (0,1)-circulant matrices with \(n\) prime and four, five or six nonzero entries per row. On this basis the authors conjecture that if \(n\) is prime, then the number of (0,1)-circulant matrices with \(k\) nonzero entries per row is asymptotically equal to \(n^{k-2}/k!+\text{O}(n^{k-3})\).