1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\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
    Commented Aug 22, 2018 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
    Commented Aug 22, 2018 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
    Commented Aug 22, 2018 at 16:47
  • 1
    $\begingroup$ This looks false, the entries of say $B^{10}$ are non-zero polynomials in $a$. $\endgroup$
    – Fedor Petrov
    Commented Aug 22, 2018 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
    Commented Aug 22, 2018 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .