The characterization of symmetric primitive matrices with exponent \(n-1\). (Q1870069)

The authors characterize completely the symmetric primitive matrices with exponent \(n-1\). An \(n\times n\) nonnegative matrix \( A=(a_{ij}) \) is said to be primitive if \(A^{k}>0\) for some positive integer \(k\), and the least such \(k\) is called the exponent of the matrix \(A\). The associated graph to an \(n\times n\)\ symmetric matrix \(A\), \(G(A)\), has \(n\) vertices and there exists an edge from \(i\) to \(j\) in \(G(A)\) if and only if \( a_{ij}>0\). A graph \(G\) is called primitive if there exists an integer \(k>0\) such that for all ordered pairs of vertices \(i,j\) of \(G\) there is a walk from \(i\) to \( j \) of length \(k\), and the least such \(k\) is called the exponent of the graph \(G.\) To prove the characterization the authors use graphs instead of matrices since a symmetric matrix \(A\) is primitive if and only if its associated graph \(G(A)\) is primitive, and moreover their exponents coincide. \textit{J. Shao} [Sci. Sin., Ser. A 30, 348--358 (1987; Zbl 0628.15017)] proved that the possible exponents for a symmetric primitive matrix are \(\{1,2,\dots ,2n-2\}-S\), where \(S\) are all odd numbers among \(\{n,n+1,\dots,2n-2\}\). In an earlier paper \textit{J. L. Cai} and \textit{K. M. Zhang} [Linear Multilinear Algebra 39, 391--396 (1995; Zbl 0843.15008)] characterize the symmetric primitive matrices with exponent \(2n-2r\) \((\geq n)\) and in this paper the authors give the first characterization with exponent less than \(n\).