Prove Matrix is Primitive

Question

I have been asked the following question

A stochastic matrix is called primitive if there exists a positive integer $k$ such that $A^k$ is a positive matrix

Prove that

$$S = \begin{pmatrix} 1/3 & 1/3 & 0 & 1/3 \\ 1/3 & 1/3 & 1/3 & 0 \\ 0&1/3&1/3&1/3& \\ 1/3 &0 &1/3&1/3 \end{pmatrix} $$

is a primitive stochastic matrix

I have attempted to prove this using induction however I am not certain if the proof is correct and would appreciate any advice for answering this question

ATTEMPTED PROOF:

Proof by Induction

Case k = 1 $$S^1 = \begin{pmatrix} 1/3 & 1/3 & 0 & 1/3 \\ 1/3 & 1/3 & 1/3 & 0 \\ 0&1/3&1/3&1/3& \\ 1/3 &0 &1/3&1/3 \end{pmatrix} $$ Since each element is positive it holds for k = 1

Case k = 2 $$S^2 = \begin{pmatrix} 1/3 & 2/9 & 2/9 & 2/9 \\ 2/9 & 1/3 & 2/9 & 2/9 \\ 2/9 &2/9 &1/3&2/9\\ 2/9 & 2/9 &2/9 &1/3 \end{pmatrix} >0 $$

therefore assumption holds for k = 2

Assume true for k = n such that $S^n > 0$

Case k = n+1

$S^{(n+1)} = S^nS^1$

Since $S^{n} > 0$ and $S^1 >0$ then it follows that $S^{n+1} >0 $

Therefore S is a positive matrix for any integer k

Answer 1

A sufficient condition to prove a matrix is primitive is for the matrix to be non-negative, irreducible and with positive elements in the main diagonal. It's clear $S$ is non-negative and there is positive elements in the main diagonal. A matrix is irreducible if it is not similar via permutation to a block upper triangular matrix ( that has more than one block of positive size ). To show that $S$ is irreducible, create an adjacency matrix by replacing the positive values in $S$ with $1$ and show that it is strongly-connected. See: https://en.wikipedia.org/wiki/Strongly_connected_component

Answer 2

You only have to prove it for one such $k$. In any case, once you have found a matrix $A^k >0$, all $A^n >0$ for any $n > k$.