On the number of different permanents of some sparse (0,1)-circulant matrices.
type: Item
instance of: scholarly article
title: On the number of different permanents of some sparse (0,1)-circulant matrices.
zbMATH Open document ID: 1037.15007
DOI: 10.1016/S0024-3795(03)00649-9
author: Giovanni Resta
author: Giovanni Sburlati
published in: Linear Algebra and its Applications
publication date: 2003-12-04T00:00:00Z
review text: 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})\).
reviewed by: Valeriu Prepeliţă
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15A45
zbMATH DE Number: 2013053
zbMATH Keywords: sparse circulant matrices
zbMATH Keywords: permanent
zbMATH Keywords: permanent inequality
zbMATH Keywords: \((0,1)\)-matrix
MaRDI profile type: Publication
cites work: How fast can one compute the permanent of circulant matrices?
cites work: On the permanent of certain \((0,1)\) Toeplitz matrices
cites work: Computation of sparse circulant permanents via determinants
cites work: Q3516443
cites work: The Lattice Point Covering Theorem for Rectangles
cites work: The complexity of computing the permanent
Recommended article: On very sparse circulant \((0,1)\) matrices
Recommended article: How fast can one compute the permanent of circulant matrices?
Recommended article: The number of terms in the permanent and the determinant of a generic circulant matrix
Recommended article: Q2704232
Recommended article: Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
Recommended article: Q4815662
Recommended article: The asymptotic behaviour of permanents of some (0, 1)-matrices
Recommended article: On the permanent of certain \((0,1)\) Toeplitz matrices
Recommended article: An upper bound on the number of high-dimensional permutations
Recommended article: On the values of permanents of (0, 1) circulant matrices with three ones per row
description: scientific article; zbMATH DE number 2013053