Primitive matrix

The primitiveness of matrices is a concept of linear algebra , which is used especially in the theory of positive eigenvalues, see e.g. Perron-Frobenius theorem .

definition

A square matrix is called primitive if all entries are nonnegative and if there is a natural number such that all entries of are positive . ${\displaystyle X=(x_{ij})_{i,j}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle X^{n}}$

The smallest such is called the exponent of the primitive matrix. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \gamma (X)}$

properties

• Primitive matrices are irreducible .
• If the matrix is irreducible, then (the sum with the identity matrix ) is a primitive matrix. ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle E_{n}+A}$
• For the exponent of a primitive matrix is valid , wherein the degree of the minimal polynomial , respectively. ${\displaystyle A}$ ${\displaystyle \gamma (A)\leq (m-1)^{2}+1}$ ${\displaystyle m}$

Examples

The matrix is irreducible, but not primitive. The matrix is primitive. ${\displaystyle \left({\begin{matrix}0&1\\1&0\end{matrix}}\right)}$ ${\displaystyle \left({\begin{matrix}0&1\\1&1\end{matrix}}\right)}$

Applications

• The Perron-Frobenius theorem applies to primitive matrices : the spectral radius is a positive, simple eigenvalue .
• Let be the adjacency matrix of a graph. Then is primitive if and only if the graph is connected and there are two cycles of coprime length. ${\displaystyle A}$ ${\displaystyle A}$
• Primitive stochastic matrices are important in the theory of Markov chains .

literature

• E. Seneta: Non-negative matrices. An introduction to theory and applications. Halsted Press, New York, 1973.

Individual evidence

1. ^ Jian Shen: Proof of a conjecture about the exponent of primitive matrices. Linear Algebra Appl. 216: 185-203 (1995).