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.


This matrix is invertible modulo 2, thus so is each its power, but all-ones matrix is singular.

  • $\begingroup$ Very clear and sweet answer. You know, how much I was thinking about this problem from graph theory point of view. Really, really thanks. $\endgroup$ – user0410 Aug 22 '18 at 13:03
  • 4
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov Aug 22 '18 at 13:07
  • $\begingroup$ 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. $\endgroup$ – user0410 Aug 22 '18 at 16:47
  • 1
    $\begingroup$ This looks false, the entries of say $B^{10}$ are non-zero polynomials in $a$. $\endgroup$ – Fedor Petrov Aug 22 '18 at 16:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov Aug 22 '18 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.