Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am asked to prove the fact that if $C$ is an $[N,k]$ code, and $C^{\perp} = x \in \mathbb{F}_2^N$ $|$ $(x,c) = 0$  $\forall c \in C$, then $\dim C + \dim C^{\perp} = N$. I am regrettably far behind in my studies and still do not know too much about codes, but isn't this basically a straight application of the rank-nullity theorem?

In particular, can I just think of it like this: $C$ has $k$ free values in its vectors, so $C^{\perp}$ has to have $k$ $0$'s in it's vector, so $C^{\perp}$ can only have $N - k$ free values? Or am I oversimplifying things? This seems like a trivial question, but maybe I am not thinking of it right...

share|cite|improve this question
I think you're off track in your second paragraph. Consider the very simple code $C=\{[0,0],[1,1]\}=C^\perp$. – rschwieb Nov 6 '12 at 1:13
What if I amended it to free variable instead of 1 – tacos_tacos_tacos Nov 6 '12 at 1:14
I'm not sure what you mean by free variable. The fact is that you won't be predicting how many zeroes and ones are in vectors... How about you clear up your idea about the rank nullity theorem! What would you need to check to see if it applies here? – rschwieb Nov 6 '12 at 1:17
In the past, I've had a transformation matrix to consider. I guess my question is, what is the transformation matrix in this case? – tacos_tacos_tacos Nov 6 '12 at 1:25
Yes. You are on the right track. This is an application of rank-nullity. Consider the linear mapping from $\mathbb{F}_2^N$ to $\mathbb{F}_2^k$ defined by calculating the `inner products' with the $k$ basis vectors. Another way of looking at is to observe that the information positions (leading ones of the rows of a generator matrix in a reduced row-echelon form) become check positions of the dual code (you can solve that particular coordinate from the single linear equation involving it). – Jyrki Lahtonen Nov 6 '12 at 7:43

Your Answer


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

Browse other questions tagged or ask your own question.