Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is Some TeX fixing Required? –  user21436 Jan 21 '12 at 23:40
    
I am more than a little bit curious about the origin of this question. Something to do with Reed-Muller codes? –  Jyrki Lahtonen Jan 22 '12 at 6:45
    
@JyrkiLahtonen: not really. I added the "coding" tag because it has definite sympathies with it both in motivation and the likely tools, though. I'm dealing with an abstract machine model in which many parallel computations give rise non-deterministically to different answers, and all I have access to is the parity (or the residue mod k for some $k \geqslant 2$) of the number of successful such computations; while I'd like to know if there exists a result which got an odd (or nonzero mod k) number of outcomes. –  Niel de Beaudrap Jan 23 '12 at 17:25

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks! Of course, it may take nearly N applications of T to map a vector to one with odd 1-norm, in the worst case (e.g. given $\mathbf v = \mathbf e_{N-1} + \mathbf e_N$). Do you think that this worst-case behaviour is likely to hold generally, or is there a choice of T which might be more efficient? –  Niel de Beaudrap Jan 22 '12 at 9:57
    
@Niel, that is another interesting question. I don't know the answer. Here it takes a long time with your input, because the smallest $T$-stable subspace generated by that vector is actually the whole space, and so we need a lot of iterations before linear dependencies are forced upon us (and the question, whether the subspace has only even weight vectors can be answered in the affirmative only at that point). I will try and think about this in terms of the irreducible factors of the minimal (resp. characteristic) polynomial of $T$, but it is complicated. –  Jyrki Lahtonen Jan 22 '12 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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