# Walks of odd Lengths in a Matrix

Consider the following matrix $$A=\left[ \begin {array}{cccc} 1&1&0&0\\ 0&0&1&0\\ 0&0&1&1\\ 1&0&0&0 \end {array} \right].$$ Assume that $B=A^k$ for some positive integer $k$.

My Question:

How to prove there is no $k$ such that all entries of $B$ are odd numbers.

In terminology of graph theory, we should prove there is no positive integer $k$ such that the numbers of walks of length $k$ from any vertex $v_i$ to $v_j$ with $1\leq i,j \leq 4$ are odd numbers.

Thanks for any suggestions.

• Even if $A$ were singular, the powers of $A$ are eventually periodic modulo 2 (as any map on a finite set is eventually periodic) and once you find $k<n$ such that $A^k$ and $A^n$ coincide modulo 2, you just have to check that all matrices $A,A^2,\dots,A^{n-1}$ contain even entries. – Fedor Petrov Aug 22 '18 at 13:07
• Consider $a\in \mathbb{R}$ is a non-zero element. Consider the matrix $\bf A$ in question such that $A[1,1]=A[3,3]=a$. Please call this new matrix $\bf B$. Based on your comment, how to prove that there is no a positive integer $k$ such that all entries of ${\bf B}^k$ be non-zero over $\mathbb{R}$. The determinant of $\bf B$ is $1$ and its characteristic polynomial is $\left( {\lambda}^{2}+a\lambda+1 \right) ^{2}$ over $\mathbb{F}_2$. I appreciate you taking the time to help me. – user0410 Aug 22 '18 at 16:47
• This looks false, the entries of say $B^{10}$ are non-zero polynomials in $a$. – Fedor Petrov Aug 22 '18 at 16:55
• Write $x^n=(x^4+a^2 x^2 +1)h(x)+r(x)$, where $\deg r<4$ over $\mathbb{F}_2 [a]$. For even $n$ the polynomial $r$ is even, for odd $n$ it is odd. We have $B^n=r(B)$. Thus $B^n$ is a linear combination either of $1$ and $B^2$ or of $B$ and $B^3$. This yields zeroes in both cases. – Fedor Petrov Aug 22 '18 at 17:53