On the index of convergence for imprimitive Boolean matrices (Q1326530)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the index of convergence for imprimitive Boolean matrices |
scientific article |
Statements
On the index of convergence for imprimitive Boolean matrices (English)
0 references
24 October 1994
0 references
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.
0 references
imprimitive Boolean matrices
0 references
index of convergence
0 references