The index set problem for Boolean (or nonnegative) matrices (Q1313969): Difference between revisions

Let \({\mathcal B}_ n\) denote the set (finite multiplicative semigroup) of \(n\)-square Boolean matrices, and let \(A\in {\mathcal B}_ n\). Then the sequence of powers \(I= A^ 0,A^ 1,A^ 2,\dots\) forms a finite subsemigroup of \({\mathcal B}_ n\), and there exists a least nonnegative integer \(k= k(A)\) (index of convergence of \(A\)) such that \(A^ k= A^{k+t}\) for some \(t>0\). The index set problem can be stated in the following way: for a given subset \({\mathcal A}\subset {\mathcal B}_ n\), determine the set of indices \(\text{IS}({\mathcal A}):= \{k:\) there exists a matrix \(A\in {\mathcal A}\) such that \(k(A)= k\}\). In order to determine \(\text{IS}({\mathcal A})\) one usually starts solving the so-called maximum index problem: for a given subset \({\mathcal A}\subset {\mathcal B}_ n\) determine the maximum index \(\text{MI}({\mathcal A}):= \max\{a: a\in \text{IS}({\mathcal A})\}\). It is of particular interest to know those matrices \(A\) in \(\mathcal A\) for which the numbers \(k(A)\) and \(\text{MI}({\mathcal A})\) coincide (external matrix problem): for a given subset \({\mathcal A}\subset{\mathcal B}_ n\), determine the set of matrices \(\text{EM}({\mathcal A}):= \{A\in {\mathcal A}: k(A)= \text{MI}({\mathcal A})\}\). Classical work on the three problems mentioned dates back to \textit{H. Wielandt} [Math. Z. 52, 642-648 (1950; Zbl 0035.291)] who devoted himself to the case of \(\mathcal A\) being the set of \(n\)-square primitive matrices. In the paper under review, the authors present a survey on more recent developments in the investigation of those problems for several other classes of matrices. Some related research problems are suggested.