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.

I am working with a Linear Code, C, over $F_{2^5}$, and its dual, $C^{\perp}$. I have the generator matrix for $C$, $G$, and have calculated the generator matrix for $C^{\perp}$, $G^{\perp}$. I need to find a permutation matrix $P$ such that $GP = G^{\perp}$. I have determined that, if $G = (I_2\ |\ A)$, then $G^{\perp} = (I_2\ |\ A^{-1})$. However, I have no idea how to invert only part of a matrix, and was hoping someone could get me started in the right direction.

This is a homework problem, so I am not asking for a solution or anything, I have just run out of ideas and was hoping for some new ones.

Thanks in advance.

share|improve this question

1 Answer 1

I don't think that you need to invert $A$ - transposing it will do. Let's first review the definitions. Most of this you probably know, but it also looks like some lingering confusions may be there.

If $G$ is a generator matrix for a code $C$, then $C$ is the row space of $G$, i.e. the span of the rows of $G$. For several good reasons we usually assume that the rows of $G$ are linearly independent. So if the length of your code is $n$ and the dimension (=number of information symbols per block) is $k$, then $G$ is a $k\times n$ matrix with entries from your symbol alphabet $F_{32}$. What we often (but not always) do is to put this into a systematic form, i.e. we carry out some row operations on $G$, and, if necessary, permute some columns, and end up with $$ G=(I_k | A), $$ where $A$ is some matrix with $k$ rows and $(n-k)$ columns.

[Edit] There is no such thing as the generator matrix of a code. There are several. Any matrix that has the right rowspace will work. OTOH, if you use an error-correcting code for adding redundancy to transmitted/stored data, then you do have to select one, because you encode a message vector $m\in F_{32}^k$ as $x=Gm^T$, and selecting a different generator matrix will change the encoding function. It doesn't matter as long as the transmitter and the receiver use the same $G$. The code $C$ = the set of vectors $x$ that comes out is the same for all generator matrices of $C$. Only the encoding "which $m$ corresponds to which $x$" depends on the choice of $G$. [/Edit]

Then the dual code $C^\perp$ consists of vectors $y\in F_{32}^n$ with the property $yx^T=0$ for all the vectors $x\in C$. It suffice to check this for the rows of $G$. In other words $y\in C^\perp$, iff $y G^T=0$. Standard linear algebra shows that the dual code $C^\perp$ is an $(n-k)$-dimensional subspace of $F_{32}^n$ (the superscript $^T$ denotes the transpose here, so it is also a way of turning a row vector into a column vector).

Consider the matrix $H=(A^T| I_{n-k})$. It obviously has $n-k$ linearly independent rows. Furthermore $$ HG^T=(A^T)I_k+I_{n-k}A^T=A^T+A^T=0, $$ because for any matrix $M$ over $F_{32}$ we have $M+M=2M=0$. This means that all the rows of $H$ are vectors of the dual code $C^\perp$. Putting these bits together we see that $H$ is a generator matrix for the dual code.

So the shortest possible answer to your question is that the matrix $(A^T|I)$ is an answer. You may prefer to put this into a more standard systematic form with an identity block on the left. However, there is no guarantee that we can do this by simply doing row operations on $H$ (if need be I will cook up a counterexample). When we put a generator matrix into a systematic form, we must always be prepared to also permute the columns. This will change the code, but it will stay equivalent to the code we started with. So here we can simply swap the two blocks, and also say that $(I|A^T)$ is a generator matrix of a code that is equivalent to the dual code $C^\perp$.

In coding theory parlance it is standard to call the above matrix $H=(A^T|I_{n-k})$ the parity check matrix of the code $C$, because we can use that to check for membership in the code $C$. A vector $x\in F_{32}^n$ is an element of $C$, if and only if $Hx^T=0$. Here we use double-duality: $(C^\perp)^\perp=C$. So a parity check matrix of $C$ is a generator matrix of $C^\perp$ and vice versa.

share|improve this answer

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.