Every primitive matrix is 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.


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.

Tags:

Matrices