# Every primitive matrix is irreducible?

$A$ is reducible if there is some permutation matrix $P$ such that $$PAP^T = \begin{bmatrix} B & C \\ O & D \\ \end{bmatrix}$$

And, if $A^k > O$ for some k, then $A$ is called primitive.

Then, how can I show that every primitive matrix is irreducible?

An easier way (IMO) to understand that every non-negative primitive matrix $$A$$ is also irreducible is by simply examining the definitions (some of them might be considered as alternative - but equivalent - definitions):

Let $$A$$ be a non-negative matrix.

1. $$A$$ is primitive if the following holds:

$$\exists k \forall (i,j) : A^k_{ij} > 0$$

2. $$A$$ is irreducible if the following holds:

$$\forall (i,j) \exists k : A^k_{ij} > 0$$

Notice the slight difference between the 2 definitions - for (2) it means that every pair $$(i,j)$$ has its own value of $$k$$ (or perhaps it's better to denote it as a function: $$k(i,j)$$), while in (1) it's the same value of $$k$$ for all the $$(i,j)$$ pairs. Thus, (1) is clearly a particular case of (2), and therefore, if a non-negative matrix is primitive, then it's also irreducible.

Your definition of primitive matrix is wrong. A primitive matrix is a nonnegative matrix $A$ such that $A^k>0$ for some natural integer $k$. You cannot remove the nonnegativity requirement on $A$ and the positivity requirement on $k$.

If $A$ is reducible, then it is, by definition, permutation-similar to a block upper triangular matrix $M$. Since $M^k$ is block upper triangular for all $k\in\mathbb{N}$, it always contains a zero block. Yet $M^k$ is permutation-similar to $A^k$. So, $A^k$ always contains a zero entry and hence it is not primitive.

• Oh your 'B' is not same with the B in the problem. I seriously worried for nothing. Thank you!
– plhn
Jun 10, 2013 at 2:30
• @plhn Uhh, my bad. I've changed the symbol now. Sorry for the confusion. Jun 10, 2013 at 2:33

For n ≥ 2, an n × n non-negative matrix $$A$$ is irreducible if $$\sum_{k=0}^{n-1}A_k$$ is positive matrix.

For n ≥ 2, an n × n non-negative matrix A is primitive if there exists $$k\in N$$ such that $$A_k$$ is positive matrix.

According to the definition, we can get example: $$A=[0,1;1,0]$$, with $$spec(A)=\{1,-1\}$$ and eigenvector are $$[1,0]^T, [0,1]^T$$. So diagonalization is : $$\left[ \begin{matrix} 1&0\\0&-1 \end{matrix} \right]=D=Q^{-1}AQ$$ Look at this! the sum of A^k (from k=1 to n-1) is positive definitely. But does it primitive? No$$\lim_{k\rightarrow \infty}A^k=\lim_{k\rightarrow \infty}QD^kQ^{-1}$$, but A is primitive if the following holds: $$∃k,∀(i,j):A_{ij}^k>0$$ . Obviously can we say A is primitive when k approaching infty?

So the irreducible matrix may not be the primitive matrix.

A nonnegative, irreducible matrix is called primitive if and only if its maximal modulus eigenvalue is simple (algebraic and geometric multiplicities both equal to one). See Definition 8.5.0 in Matrix Analysis by Horn and Johnson. A nonnegative, irreducible matrix is primitive if and only if it is aperiodic (ibid. Theorem 8.5.3). According to this source, we wouldn't ever call a reducible matrix primitive. Though a reducible matrix can still have a simple maximal modulus eigenvalue, e.g. the zero matrix with a lone positive number at one location in the diagonal.

So we can see that a nonnegative matrix being primitive is the same thing as being irreducible and aperiodic.