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

Hi !

I have a parity check matrix $H$ for a code $C$
0 0 0 1 1 1 1 0
0 1 1 0 0 1 1 0
1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1

I am allowed to assume that
1) the dual of an $(n,k)$-code is an $[n,n-k]$-code
2) $(C^{\perp})^{\perp} = C$ (Here $\perp$ denotes the dual)

I want to prove that my code $C$ is self-dual. (ie that $C=C^{\perp}$)

Here is my logic:

I know that, since $H$ is a parity check matrix for $C$,
$H$ is a generator matrix for $C^{\perp}$.

Since $C^{\perp}$ is an $[n,n-k]$-code, the generator matrix $H$ is a matrix: $[n-k]$ x $ n$

So now looking at $H$, n=8 and k=4, so the corresponding $C$ code is a $8$x$4$ matrix.

Now let $G=[g_{i,j}]$ be the generator matrix for $C$.
$(GH^T)=0$ since every vector in the rowspace of $G$ is orthogonal to every vector in the rowspace of $H$;

Can anyone tell me what is missing to finish off my proof?

Note: i see that each row in $H$ has even number of entries and that the distance between any two rows is even. maybe this helps if I can right a definition of weight relating to duals...

share|cite|improve this question
If you can show that the rows of $C$ are orthogonal to each other, then every codeword in $C$ is a member of $C^{\perp}$ since any given codeword $x$ is orthogonal to all the codewords in $C$ and thus $x \in C^{\perp}$. Next, conclude from your given assertion that $C^{\perp}$ is a $[n, n-k] = [8, 4]$ code that there are no other codewords in $C^{\perp}$. – Dilip Sarwate Apr 30 '12 at 17:45
>Can anyone tell me... What you have shown is that $C^{\perp}$ has generator matrix $H$. What you need to show is that all the codewords in $C^{\perp}$ are codewords in $C$ and vice versa. Proving inclusion in one direction and then asserting equality on the grounds that the two sets have the same cardinality works since we are dealing with finite sets. – Dilip Sarwate Apr 30 '12 at 17:52
does it suffice to look at the generator matrix of C (for the inclusion part) ? – Kiv Efehe Apr 30 '12 at 18:06
>does it suffice? Yes it does, but see rschwieb's answer which shows one inclusion without having to look for (or look at) the generator matrix of $C$. – Dilip Sarwate Apr 30 '12 at 18:58

The rows of $H$ generate $C^\perp$.

By definition of the parity check, $xH^\mathrm{T}=0$ iff $x\in C$.

What can you conclude from the fact that $HH^\mathrm{T}=[0]$?

share|cite|improve this answer

Your Answer


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.