The semigroup of primitive generalized circulant Boolean matrices. (Q877752)

An \(r\)-circulant Boolean matrix is one where each row, except the first, is obtained from the preceding row by shifting the elements cyclically \(r\) columns to the right. Let \(G_n\) denote the semigroup of \(n\times n\) circulant Boolean matrices and \(G(J_n)\) be the semigroup of all its primitive members, meaning those matrices for which some power is \(J_n\), the \(n\times n\) matrix of 1's. It is proved that asymptotically the orders of \(G_n\) and \(J(G_n)\) are the same and approach in ratio \(n\cdot 2^n\). Algebraic results are also presented including the fact that the nilpotency index of \(J(G_n)\) is \(n-1\) and the nature of the embedding of \(J(G_n)\) in the semigroup \(SG_n\) of all doubly stochastic matrices is investigated. In particular \(J(G_n)\) is the intersection of all prime ideals of \(SG_n\).