On very sparse circulant \((0,1)\) matrices
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.)
scientific article; zbMATH DE number 5077994
scientific article