Unimodular matrices without stable sub-spaces of even weight?

105 Views Asked by At

For each N, is there an N×N invertible matrix T over ℤ/2ℤ which does not have a stable subspace of "even weight" -- i.e.  such that there does not exist a set of vectors over ℤ/2ℤ which all have an even number of 1s, and which span a space which is preserved under the action of T?

Equivalently (I think): is there an N×N unimodular matrix T over the integers, for each N, which "eventually" (by applying it enough times, possibly zero) maps each integer vector with at least one odd coefficient to a vector with odd 1-norm?

I'm most interested in the case where N is a power of 2, but remarks on the general case would be interesting.

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, such a matrix can be found for any size $N$. Let $J$ be the binary matrix with ones immediately above the diagonal and zeros elsewhere $$ J=\left( \begin{array}{cccccc} 0&1&0&0&\cdots&0\\ 0&0&1&0&\cdots&0\\ 0&0&0&1&0&\vdots\\ \vdots&\vdots&\vdots&\ddots&\ddots&\vdots\\ 0&0&\cdots&\ddots&0&1\\ 0&0&\cdots&0&0&0\\ \end{array}\right), $$ and let $T=I+J$.

Then $T$ is invertible by virtue of being upper triangular. I claim that there is no non-trivial subspace $V\subseteq F_2^N$ with both the properties:

  1. for all $v\in V, v$ has an even weight, and
  2. for all $v\in V,\ Tv\in V$.

Assume contrariwise that such a subspace $V$ of dimension at least $1$ exists. Let $v\in V$ be a non-zero vector. Then $Tv=v+Jv\in V$, so because $V$ is a subspace, we also have $Jv=Tv-v\in V$. By induction, we can conclude that $J^kv\in V$ for all integers $k>0$.

But $J(v_1,v_2,\ldots,v_N)^T=(v_2,v_3,\ldots,v_N,0)^T$, so if $k$ is the index of the first non-zero component, we have that the weights of $v=(v_1,v_2,\ldots,v_N)^T$ and $J^kv$ differ by exactly one. Thus either $v$ or $J^kv$ will violate the first condition.