On very sparse circulant \((0,1)\) matrices
type: Item
instance of: scholarly article
title: On very sparse circulant \((0,1)\) matrices
zbMATH Open document ID: 1110.15014
author: Norma Zagaglia Salvi
author: Rodolfo Salvi
published in: Linear Algebra and its Applications
publication date: 2006-12-07T00:00:00Z
review text: This paper is concerned with the structure of circulant \((0,1)\)-matrices with 3 ones per row. Suppose that \(A=P^0+P^i+P^j\) where \(0<i<j<n\) and \(P\) is the \(n\times n\) permutation matrix corresponding to the \(n\)-cycle \((123\cdots n)\). Let \(G[A]\) denote the bipartite graph associated with \(A\) in the usual way. Various results about the structure of \(A\) and \(G[A]\) are proved. The most important concern the genus of \(G[A]\). It is shown that in most cases \(G[A]\) has genus 1. Under some special conditions \(G[A]\) is planar. The final section of the paper opens with a promise to find a lower bound on the number of different values taken by per\((A)\), the permanent of \(A\). Confusingly, it seems this promise is not fulfilled. Instead, it is shown that per\((A)\geq 2^k+1\) where \(k\) is the maximum of the three gcd's \((n,i)\), \((n,j-i)\), \((n,n-j)\). Examples are used to show that this bound is sometimes better and sometimes worse than the general bound per\((A)\geq (4/3)^n\) which applies to all binary matrices with 3 ones per row and column. (This last bound is a simplified but weakened version of the result per\((A)\geq 6(4/3)^{n-3}\) proved by \textit{M. Voorhoeve} [Indag. Math. 41, 83--86 (1979; Zbl 0401.05005)]. The original form of Voorhoeve's result does better than the authors' new bound on the example they give, but there are larger examples where this is not the case.)
reviewed by: Ian M. Wanless
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 5077994
zbMATH Keywords: circulant matrix
zbMATH Keywords: permanent
zbMATH Keywords: bipartite graph
zbMATH Keywords: genus
zbMATH Keywords: \((0,1)\)-matrices
MaRDI profile type: Publication
full work available at URL: j.laa.2006.02.029
OpenAlex ID: W1965202611
cites work: Q4821520
cites work: An update on Minc's survey of open problems involving permanents
cites work: On the permanent of certain \((0,1)\) Toeplitz matrices
cites work: Computation of sparse circulant permanents via determinants
cites work: Q3208805
cites work: Q5605168
cites work: On the number of different permanents of some sparse (0,1)-circulant matrices.
cites work: Permanents
cites work: Permanents of (0, 1)-Circulants
cites work: Recurrence formulas for permanents of (0,1)-circulants
cites work: Q4815662
cites work: Q4039989
cites work: Matchings in graphs on non-orientable surfaces
DOI: 10.1016/J.LAA.2006.02.029
Recommended article: On the number of different permanents of some sparse (0,1)-circulant matrices.
Recommended article: Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
Recommended article: Q2704232
Recommended article: On the values of permanents of (0, 1) circulant matrices with three ones per row
Recommended article: Computing permanents via determinants for some classes of sparse matrices
Recommended article: Computation of sparse circulant permanents via determinants
Recommended article: Q4815662
Recommended article: Q3378338
Recommended article: Q3317108
Recommended article: Q6134941
description: scientific article; zbMATH DE number 5077994