How to check a special form of Companion Matrix is a Primitive Matrix or not?

Question

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: If the graph associated to $A$ is strongly connected and has two cycles of relatively prime lengths, then $A$ is primitive.[2]

Corollary 8.5.8 (Wielandt): Let $A\in M_n$ be non-negative. Then $A$ is primitive if and only if $A^{n^2-2n+2}>0$.[3]

Now consider the following form of the Companion Matrix $$ C_n=\left( \begin{array}{cccccc} 0 &1 &0 &\cdots &\cdots &0 \\ 0 &0 &1 &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &0 \\ 0 &\cdots &\cdots &0&0 &1 \\ 1 &u_1 &u_2 &\cdots &u_{n-2} &u_{n-1} \end{array} \right)_{n\times n} $$ where $u_i\in \{0,1\}$, for $1\leq i \leq n-1$. Based on the Corollary 8.5.8, for every selection of $u_i$'s, we compute $C_n^{n^2-2n+2}$ and if all entries of $C_n^{n^2-2n+2}$, denoted by $C_n^{n^2-2n+2}[i,j]$, $1\leq i,j\leq n$, be positive integer numbers then we conclude that $C_n$ is a primitive matrix, otherwise it results that $C_n$ is not a primitive matrix.

Example: For $n=6$, assume that $V=(u_1,u_2,u_3,u_4,u_5)$ then, with selections $V=(1,0,0,0,0)$ and $V=(0,0,0,0,1)$, the $C_6$ is a primitive matrix and by choosing $V=(0,1,0,0,0)$, $V=(0,0,1,0,0)$ and $V=(0,0,0,1,0)$, the $C_6$ is not a primitive matrix.

My question: Is there other methods to verify that with selection $u_i$'s the $C_n$ is a primitive matrix or not? For example, suppose that $n=2m$ and $V=(u_1,\cdots,u_{2m-1})=(0,1,0,1,0,\cdots,1,0)$ then how to prove that $C_n$ is not a primitive matrix?

I know that the characteristic polynomial of $C_n$ is $char(C_n)=x^n-u_{n-1}x^{n-1}-\cdots -u_1x-1$, but how to use $char(C_n)$ to answer question.

Thanks for any suggestions

Answer 1

Your second definition is actually a lemma, and it is quite powerful:

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.

If you draw the graph associated to $A$, you can notice that if $u_{i_1},u_{i_2},\dots,u_{i_s}$ are the only 1 entries, then the graph has only the simple cycles of length $n,n-i_1,n-i_2,\dots,n-i_s$.

Using the above result, you get that $A$ is primitive if and only if $$ gcd(n,n-i_1,n-i_2,\dots,n-i_s)=1 $$