On very sparse circulant \((0,1)\) matrices (Q855544)

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.)