# Why is every irreducible matrix with period 1 primitive?

In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried to prove the theorem by myself, I found that I was unable to come up with a formal proof. Intuitively, of course, I am sure that the theorem holds (and the converse statement is in fact easy to prove), but I am unable to prove it.

According to the text, the theorem should be obvious from the graph-theoretic interpretation of these notions. For a given nonnegative matrix, it is possible to construct a digraph as follows: There is an edge from the $i$-th vertex to the $j$-th vertex if and only if the entry $(i,j)$ of the matrix is positive. Thus, the matrix is irreducible if and only if its digraph is strongly connected. The period is defined to be the greatest common divisor of lengths of cycles (more precisely, the closed paths) of the graph. And finally, the matrix is said to be primitive if there is a positive integer $n$ such that for each pair of vertices of the graph there is a path of length $n$ interconnecting these vertices.

The theorem to be proved can thus be restated as follows: For every strongly connected digraph with the greatest common divisor of the lengths of closed paths equal to $1$, there is a positive integer $n$ such that for every pair of vertices of the digraph there is a path of length $n$ interconnecting these vertices.

It seems to me that the theorem might be proved by means of number theory, but I have not been able to find a proof up to now. To be more specific, I am looking for a proof without the use of the Perron-Frobenius theorem (the proposition is used in the text to prove the Perron-Frobenius theorem). Any ideas?

Thank you in advance.

-
Hi -- I did some copyediting -- note that "each" and "every" are largely synonymous, but "each" is usually only used for a finite number of things. –  joriki Jul 18 '12 at 9:44
Here's one approach. first show that aperiodicity+irreducibility implies that for any vertex $v$, there is an integer $N$ such that for every $n>N$, there is a closed path of length $n$ going from $v$ to $v$. Then show that this and irreducibility implies primitivity. –  Colin McQuillan Jul 18 '12 at 10:00

Here is the argument given in section 1.3 of Gregory F. Lawler's Introduction to Stochastic Processes. It treats stochastic matrices $P$, but I think the argument applies to general non-negative matrices.

For each state $i$ define $J_i=\{n: P^n(i,i)>0\}$. This is a semigroup and since we have assumed that $P$ is aperiodic, we have $\gcd(J_i)=1$ and it follows that $J_i$ contains all sufficiently large integers. That is, there is some integer $M(i)$ so that for all $n\geq M(i)$ we have $P^n(i,i)>0$.

Since $P$ is irreducible, there exists some $m(i,j)$ such that $P^{m(i,j)}(i,j)>0$. Hence for $n\geq M(i)$, $$P^{n+m(i,j)}(i,j)\geq P^n(i,i)\,P^{m(i,j)}(i,j)>0.$$

Let $M$ be the maximum value of $M(i)+m(i,j)$ over all pairs $(i,j)$. Then for $n\geq M$, $P^n(i,j)>0$ for all states $i,j$.

Essentially the same argument is found in section 1.3 of Markov Chains and Mixing Times by Levin, Peres, and Wilmer. So it looks like probabilists have not found a better proof.

-

If the matrix is irreducible, given two vertices you can find a path from one to the other that visits every cycle. Then you can add an arbitrary number of traversals of each cycle. By the Chinese remainder theorem, since the $\gcd$ of the cycle lengths is $1$, you can make the path length have any residue you want modulo their $\operatorname{lcm}$. You can also add integer multiples of the $\operatorname{lcm}$ to the path length. Thus there is some integer such that you can achieve all path lengths greater than that, and the desired integer $n$ is the maximum of all these integers over all pairs of vertices.

-
Thanks for the answer. My thoughts have followed a similar train of thought, however I have found this approach quite problematic. The first problem is that the Chinese remainder theorem (up to my poor knowledge of number theory) requires that those numbers are pairwise coprime. Thus, if the lengths of the cycles are for instance 4,6,9, and some more, there is a problem. Moreover, the second problem is that the cycles need not have a common vertex, and thus extra steps might be needed that spoil the property of the residue. However, it is possible that I have overlooked something. –  042 Jul 18 '12 at 11:00
@042 The C.R.T. conditions can be "weakened" in some sense, from definition, $\gcd(a_1,\dots,a_k)$ is such positive integer $g$ that $a_1\Bbb Z+a_2\Bbb Z+\dots+a_k\Bbb Z=g\Bbb Z$. Therefore if $g=1$, you can combine any number $n$ as an integer combination of $a_i$'s. To make it a natural combination notice that if you add $a_2\cdot a_3\dotsm a_k$ to the coefficient of $a_1$, the result will be the same modulo the $\mathrm{lcm}$. This way you can arbitrarily enlarge all the coefficients. –  tohecz Dec 6 '12 at 15:02