\(g\)-circulant solutions to the (0,1) matrix equation \(A^m=J_n\) (Q1347955)

A \(g\)-circulant (\(g\in {\mathbb N}\)) is a matrix each of whose rows except the first one is obtained by cyclically shifting the previous row \(g\) columns to the right (\(g\) is called the shifting parameter). The first row \((a_0,\ldots ,a_{n-1})\) of a \(g\)-circulant \(A\) defines its Hall polynomial \(\theta _A(x)=\sum _{i=0}^{n-1}a_ix^i\). A \((0,1)\) matrix is a matrix whose entries are zeros and/or units. The all-one matrix of order \(n\) is denoted by \(J_n\). Given \(s,t\in {\mathbb N}\), define the de Bruijn digraph \(B(s,t)\) as follows [cf. \textit{N. C. de Bruijn}, Nieuw Arch. Wiskd., III. Ser. 4, 15-17 (1956; Zbl 0073.02704)]. Its vertex set \(V(B(s,t))\) consists of all \(t\)-tuples \((b_1,\ldots ,b_t)\) with integral coordinates: \( 0\leq b_i\leq s-1\), \(1\leq i\leq t\); \((b_1,\ldots ,b_t)\) is joined to \((b_1',\ldots ,b_t')\) if and only if \(b_i'=b_{i+1}\) for \(1\leq i\leq t-1\). Consider the equation \((*)\) \(A^m=J_n\) (the case \(m=2\), when the unknown matrix \(A\) must be a \((0,1)\) one, has been considered by \textit{A. J. Hoffman} [Research problems 2-11. J. Combin. theory 2, 393 (1967)]). Partially verifying a conjecture of \textit{J. Wang} [The number and construction of solutions of some congruence and their combinatorial applications. PhD Thesis, Dalian University of Technology (1990, in Chinese)] about the form of the solutions to \((*)\), the authors discover a close relationship among the Hall polynomial \(\theta _A(x)\), the shifting parameter \(g\), and the order \(n\) of any \((0,1)\) \(g\)-circulant solution \(A\) to \((*)\). In the case when \(n\) is a prime power all \(g\)-circulant solutions are completely determined. When the line sum \(r\) of \(A\) is constant and square-free, all \(g\)-circulant solutions to \((*)\) are proved to be permutation similar to the adjacency matrix of the de Bruijn digraph \(B(r,m)\). In the paper all \((0,1)\) \(g\)-circulant solutions to \((*)\) are identified whose Hall polynomials have some specific properties, the values of \(g\) are determined for which such solutions occur, and the uniqueness of the solutions up to isomorphism is investigated. The authors conjecture that all factorizations of \((x^n-1)/(x-1)\) into a product of \((0,1)\) polynomials must be standard, and point out a similarity between Wang's conjecture and a conjecture appearing in the study of perfect graph.