Exponents of primitive companion matrices (Q2326037)

A square nonnegative (positive) matrix \(A\), i.e., their entries are nonnegative (positive) real numbers, is called primitive if there exists a positive integer number \(m\) such that \(A^{m}\) is a positive matrix. The smallest among such positive integer numbers is said to be the exponent of \(A, \) denoted by \(\exp (A).\) For a class \(X\) of nonnegative matrices of size \(n\times n\), the exponent set \(E_{n}(X)= \{m\in N : \text{ there exists a primitive matrix } A\in X , \exp (A)=m\}.\) A sharp upper bound for the exponent of a primitive matrix is \(\omega_{n}= (n-1)^{2} +1, \) the so called Wielandt bound (for a proof, see [\textit{H. Schneider}, Linear Algebra Appl. 353, No. 1--3, 5--10 (2002; Zbl 1006.15023)]). For a given class \(X\) of non negative matrices, the problem of finding \(E_{n}(X)\), bounds on \(E_{n}(X)\) and matrices in \(X\) such that the bounds are attained constitute a relevant challenge. Let us denote by \(C_{n}\) the set of all \((0,1)\) companion matrices of polynomials \(x^{n} - \sum_{k=0}^{n-1} a_{k} x^{k},\) where \(a_{k}\in \{0,1\}.\) The subset of all primitive \((0,1)\) companion matrices is denoted by \(CP_{n}.\) In this paper the authors deduce the cardinal of \(CP_{n}\) (Theorem 2.1) as well as the exponent of a matrix \(A\in CP_{n}\) assuming that the trace of \(A\) is positive (Theorem 2.4). In a next step, the exponents of matrices in \(CP_{n}\) with zero trace are obtained (see Theorem 3.2). Indeed, if \(A\in CP_{n},\) then \(n\leq \exp (A) \leq \omega_{n}. \) Moreover, there exists a matrix \(B\in CP_{n}\) such that \(\exp (B)=n.\) Finally, some elements of \(E_{n}( CP_{n})\) are described. The techniques of directed graph (digraph) theory are extensively used in the proofs. Let us remind that for a (0,1)-matrix \(A= [a_{i, j}]_{i, j=1}^{n}\) of size \(n\times n,\) the adjacency digraph \(D(V ,E)\) has as vertex set \(V=\{1,2, \cdots, n\}\) and as edge set \(E= \{(i, j): a_{i, j}=1\}.\) On the other hand, for a digraph \(D\) its adjacency matrix \(A\) has as entries \(a_{i,j}=1\) if there is an edge from \(i\) to \(j\) in \(D\) and \(a_{i, j}=0\) otherwise.