Combinatorial structure of \(k\)-semiprimitive matrix families (Q2821889)

The paper deals with the combinatorial structure of special matrix families.NEWLINENEWLINELet us recall that a nonnegative matrix \(A\) is said to be primitive (semiprimitive) if some power of \(A\) contains only positive entries (contains a positive column). From the general definition of primitivity related to so-called Hurwitz products, the concept of \(k\)-primitivity is introduced.NEWLINENEWLINEA family of nonnegative \(n \times n\) matrices \({\mathcal A}=\{ A_1, A_2, \dots, A_k \}\) is said to be \(k\)-primitive if \({\mathcal A}^{\alpha}\) is positive for some family \(\alpha = \{ \alpha_1, \alpha_2, \dots, \alpha_k \}\), where \({\mathcal A}^{\alpha}\) denotes the sum of all the products of matrices in \({\mathcal A}\) that contain precisely \(\alpha_q\) occurrences of matrix \(A_q\), \(q=1,2, \dots, k\).NEWLINENEWLINEAs a generalization of the semiprimitivity property, the authors introduce in this paper the following concept. A family of nonnegative \(n \times n\) matrices \({\mathcal A}=\{ A_1, A_2, \dots, A_k \}\) is said to be \(k\)-semiprimitive if \({\mathcal A}^{\alpha}\) contains a positive column for some family \(\alpha = \{ \alpha_1, \alpha_2, \dots, \alpha_k \}\).NEWLINENEWLINECorresponding to the family \({\mathcal A}\) in a natural way is the coloured directed multigraph with vertex set \(N=\{ 1,2,\dots,n \}\) whose arcs are coloured using colours in the set \(\{ 1,2,\dots,k\}\). An arc \(ij\) of colour \(q\) exists if \((A_q)_{ij} >0\). A family of numbers \(\alpha = \{ \alpha_1, \alpha_2, \dots, \alpha_k \}\) is referred to as a colour vector of a path if an arc of \(q\)th colour occurs in this path \(\alpha_q\) times, \(q=1,2,\dots,k\).NEWLINENEWLINEA coloured graph is said to be \(k\)-semiprimitive if there exists a colouring \(\alpha\) such that some vertex of the graph is accessible from any other vertex by a path of colouring \(\alpha\). Of course, a matrix family is \(k\)-semiprimitive if and only if the coloured graph of the family is \(k\)-semiprimitive.NEWLINENEWLINEThe main result of this paper is the generalization of Protasov's theorem (a classification of \(k\)-primitive sets of matrices) to \(k\)-semiprimitive matrix families. The proof of this result is based on the binary relation of colour compatibility on the vertices of the coloured graph of the matrix family.