IMC 2010 · Day 2 · P9

Denote by $e_k$ ($1 \le k \le m$) the $m$-dimensional vector over $\mathbb{F}_2$, whose $k$-th entry is 1 and all the other elements are 0. Furthermore, let $u$ be the vector whose all entries are 1. The $k$-th column of $A^n$ is $A^n e_k$. So the statement can be written as $A^n e_k \ne u$ for all $1 \le k \le m$ and all $n \ge 1$.

For every pair of vectors $x = (x_1, \dots, x_m)$ and $y = (y_1, \dots, y_m)$, define the bilinear form $(x, y) = x^T y = x_1 y_1 + \dots + x_m y_m$. The product $(x, y)$ has all basic properties of scalar products (except the property that $(x, x) = 0$ implies $x = 0$). Moreover, we have $(x, x) = (x, u)$ for every vector $x \in \mathbb{F}_2^m$. It is also easy to check that $(w, Aw) = w^T A w = 0$ for all vectors $w$, since $A$ is symmetric and its diagonal elements are 0.

Lemma. Suppose that $v \in \mathbb{F}_2^m$ a vector such that $A^n v = u$ for some $n \ge 1$. Then $(v, v) = 0$.

Proof. Apply induction on $n$. For odd values of $n$ we prove the lemma directly. Let $n = 2k + 1$ and $w = A^k v$. Then $$(v, v) = (v, u) = (v, A^n v) = v^T A^n v = v^T A^{2k+1} v = (A^k v, A^{k+1} v) = (w, Aw) = 0.$$ Now suppose that $n$ is even, $n = 2k$, and the lemma is true for all smaller values of $n$. Let $w = A^k v$; then $A^k w = A^n v = u$ and thus we have $(w, w) = 0$ by the induction hypothesis. Hence, $$(v, v) = (v, u) = v^T A^n v = v^T A^{2k} v = (A^k v)^T (A^k v) = (A^k v, A^k v) = (w, w) = 0.$$ The lemma is proved.

Now suppose that $A^n e_k = u$ for some $1 \le k \le m$ and positive integer $n$. By the Lemma, we should have $(e_k, e_k) = 0$. But this is impossible because $(e_k, e_k) = 1 \ne 0$.