Definition: A non-negative matrix square $A$ is called primitive if there is a $k$ such that all the entries of $A^k$ are positive.1
Lemma: Given a graph, then the associated matrix A is primitive if and only if the graph is strongly connected and has two cycles of relatively prime lengths..[2]
Now consider the following matrix
$$
A= \left(
\begin {array}{cccccc}
0&0&0&0&1&1\\
0&0&1&0&0&0\\
1&1&0&0&0&0\\
0&0&0&0&1&0\\
0&0&1&1&0&0\\
1&0&0&0&0&0
\end {array} \right).
$$
Its associated graph, denoted $G$ is provided here:
The graph $G$ is a
strongly connected graph and just have a cycle of length $3$ which results in there is no two cycles of relatively prime lengths in graph $G$.
Therefore, based on the mentioned lemma, the matrix $A$ is not a primitive matrix.
But we can check that $A^6$ is a positive matrix which means A is a primitive matrix that is in contradiction to above discussion.
I do not know where I made a mistake that is caused this contradiction. I am assumed that a cycle is a path which has no repeated vertices on it.
I am really confused, please help me.
Thanks for any suggestions.
Best Answer
The cycle $4\to 5\to 4$ has length $2$, which is coprime to $3$, so the graph does satisfy the conditions on the lemma.
One objection here is that $a\to b\to a$ is not a simple cycle in an undirected graph. However, the graph is directed, so $4\to 5$ and $5\to 4$ are different edges. The cycle $4\to 5\to 4$ has no repeated edges, and no repeated vertices except for the common start and end vertex.
Even more to the point, the lemma is only true if one accepts cycles of length $1$ (that is, loops) and $2$. A graph has a primitive matrix iff there is some number $k$ such that any two vertices have at least one walk of length exactly $k$ between them. This is clearly true for a strongly connected graph with a loop: we may take $k$ to be the largest possible distance from anywhere to the loop vertex, plus the largest possible distance from the loop vertex to anywhere.
So for example, a graph consisting as just one large cycle plus a loop at one of the vertices will have a primitive matrix. The lemma had better accept it then, but it only will if we recognize the loop as a cycle of length $1$.
We can also see that it doesn't even matter if the two cycles we use in the lemma are simple or not. Even if they are not simple, if their lengths are coprime, any given vertex will have (non-simple) cycles of every sufficiently large length, thanks to the Frobenius coin problem. So we can simply choose $v_1$ and $v_2$ in the two coprime cycles, and then take $k$ to be the sum of the largest distance to $v_1$, plus the distance from $v_1$ to $v_2$, plus the largest distance from $v_2$, plus the Frobenius number for the cycle lengths.
There are some other contexts where it is useful not to consider loop edges to be cycles (I think), but this is not one of them.