Classification of \(k\)-primitive sets of matrices (Q2866230)

The author develops a new approach for characterizing \(k\)-primitive matrix families, which gives a classification of \(k\)-primitive sets of matrices and a polynomial-time algorithm to recognize them.NEWLINENEWLINELet \({\mathcal A}=\{A_1,A_2, \ldots, A_k \}\) be a family of nonnegative \(d \times d\) matrices and \(\alpha = \{ \alpha_1, \alpha_2, \ldots, \alpha_k \}\) a \(k\)-tuple of nonnegative integers such that \(\sum_{i=1}^k \alpha_i = m \geq 1\). \({\mathcal A}^{\alpha}\) denotes the sum of all products of \(m\) matrices from \({\mathcal A}\), in which every product contains exactly \(\alpha_i\) factors equal to \(A_i\). \({\mathcal A}\) is called \(k\)-primitive if there exists a \(k\)-tuple \(\alpha\) such that \({\mathcal A}^{\alpha}\) is entrywise strictly positive.NEWLINENEWLINEThe family \({\mathcal A}\) is called reducible if all its matrices share a common invariant coordinate subspace. The reducibility is equivalent to the existence of a suitable permutation of the basis of \(\mathbb{R}^d\), after which all matrices from \({\mathcal A}\) have a block upper-triangular form.NEWLINENEWLINEThe author considers the following two conditions for \({\mathcal A}\):NEWLINENEWLINE(a) The family \({\mathcal A}\) is irreducible.NEWLINENEWLINE(b) Either no matrix of \({\mathcal A}\) has a row of zeros or no matrix of \({\mathcal A}\) has a column of zeros.NEWLINENEWLINEFrom (a) and (b), a criterion of \(k\)-primitivity is presented:NEWLINENEWLINE A family \({\mathcal A}\) satisfying (a) and (b) is not \(k\)-primitive if and only if there exists a nontrivial partition \(\Omega= \bigcup_{i=1}^n \Omega_i\) of the set \(\Omega=\{1,2,\ldots,d \}\) on which all matrices from \({\mathcal A}\) act as commuting permutations.NEWLINENEWLINEFinally, the author describes a polynomial-time algorithm for deciding \(k\)-primitivity and finding the maximal partition \(\Omega= \bigcup_{i=1}^n \Omega_i\). The complexity of this algorithm is also analyzed.