On the index of convergence for imprimitive Boolean matrices (Q1326530)

Let \(B_ n\) be the set of Boolean matrices of order \(n\). A matrix \(A\in B_ n\) is primitive provided for some positive integer \(k\), \(A^ k=J_ n\), the all 1's matrix in \(B_ n\). The set of primitive matrices in \(B_ n\) is denoted \(P_ n\). The set \(\mathbb{P}_ n = \mathbb{B}_ n-P_ n\) is called the set of imprimitive matrices. For \(A \in B_ n\) the sequence of powers \(A\), \(A^ 2,\dots\) clearly forms a finite subsemigroups of \(B_ n\), and then exists a least positive integer \(k=k(A)\) such that \(A^ k = A^{k+t}\) for some \(t>0\). The integer \(k=k(A)\) is called the index of convergence of \(A\). The main result is formulated in the following theorem. Let \(A \in \mathbb{P}_ n\). Then \(k(A) = 1/2(n^ 2 - 4n+8)\) for \(n\) even, and \(k(A) = 1/2 (n^ 2 - 6n+15)\) for \(n\) odd. This upper bound for the index of convergence of imprimitive matrices is of Wielandt type and this is sharp. The author determines the set of matrices for which the index of convergence attains the upper bound. Finally, some gaps of the index of convergence are given.