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 have more a systems background, but I have a math-y type question so I figured I'd give it a shot here...This is more of an implementation question, I don't need to prove anything at the moment.

I'm trying to find the basis of the null space over $\mathbb{F}_2^N$ for a given basis quickly and I was hoping someone here would know how.

For example if I have the following basis in $\mathbb{F}_2^{16}$:

$$ \left( \begin{array}{cccccccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \right) $$

How would I find the null space basis for this matrix?

If I put my basis into reduced row echelon form, I could find it easily, but for my particular problem I cannot do that. I know there are exhaustive search methods, but the matrices I'm dealing with can be quite large, which make those impractical.

BEGIN EDIT

@Neil de Beaudrap, It has to do with the fact that I am actually splitting up the vector space and using part of it for another purpose. If I change this matrix with elementary row operations and put it into reduced-row-echelon form it messes things up....

I am unfamiliar with column operations, could you explain in a bit more detail what you are talking about? Thanks!

END EDIT

share|improve this question
1  
You could use sage for a one-time calculation (if wieldly), or C++ with bitwise XOR for row reduction. How large is quite large? –  bgins Apr 10 '12 at 22:52
    
Should most of the "basis" in this question have been "matrix"? Otherwise I have trouble making sense of it. –  Henning Makholm Apr 10 '12 at 22:59
    
Why can't you use row-echelon form -- something again to do with size constraints? The particular example you give lends itself quite well to column reduction; perhaps the structure of your problem is amenable to such an approach. –  Niel de Beaudrap Apr 10 '12 at 23:04
    
This is such a small matrix that row reduction is a viable option. Of course, in practice you would really use the well documented structure of this particular matrix (see Dilip's answer). You would have a real problem, if your parity check matrix were that of a, say, (64800,43200) LDPC-code. For something like that you do need to utilize other structures of the code in order to be able to encode efficiently. –  Jyrki Lahtonen Apr 11 '12 at 5:26
    
@NieldeBeaudrap, column reduction would be ok, if you only wanted to compute the rank, but that is not an option for the OP. He needs a basis for the null space. Elementary row operations don't change the null space, but elementary column operations would. –  Jyrki Lahtonen Apr 11 '12 at 5:28

1 Answer 1

Your particular example has a simple answer. The subspace whose basis is the rows of your matrix is called a first-order Reed-Muller code of length 16, and its dual (null space) is the second-order Reed-Muller code of length 16. Denoting the rows by $1, x_1, x_2, x_3, x_4$ respectively, the dual code has basis vectors that are $$1, x_1, x_2, x_3, x_4, x_1x_2, x_1x_3, x_1x_4, x_2x_3, x_2x_4, x_3x_4$$ where $x_ix_j$ is the element-by-element product of the row vectors, e.g. $x_1x_2=0000000000001111$ and $x_2x_3=0000001100000011$. More generally, the dual of the first-order Reed-Muller code of length $2^m$ is the $(m-2)^{\text{th}}$-order Reed-Muller code of length $2^m$, also known as the extended Hamming code of length $2^m$, and the basis vectors can be taken as all the monomials of degree $m-2$ or less.

More generally, in $\mathbb F_2^n$, given a $k\times n$ matrix of row rank $k$, express it in row-echelon form, interchange columns and rows as needed to express the matrix in the form $[I_{k\times k}\quad P]$ where $P$ is a ${k\times(n-k)}$ matrix. The null space is spanned by $[P^T\quad I_{(n-k)\times(n-k)}]$. Now undo the column permutations to get the basis vectors for the original problem. For vector spaces $\mathbb F_q^n$ where $q$ is not a power of $2$, use $-P^T$ instead of $P^T$.

share|improve this answer
    
That is the technique I am currently using. It works well if I can put the code into systematic form, but for my particular application I don't have that luxury which is what is making this so difficult...Are there any other ways to find the dual code when given the matrix of a primary code? –  Adam Apr 11 '12 at 13:05
    
@Adam As Jyrki Lahtonen has noted in comments on the problem, there is no easy answer for the general case. If there is structure that can be used, there would be some reduction in the computational burden. –  Dilip Sarwate Apr 11 '12 at 14:00
    
If column operations are reversible, it sounds like there is a general answer I can use. I can put it into [I P] form so long as I can undo all the operations I had to do to get it there in the dual basis. –  Adam Apr 11 '12 at 15:56
    
This particular fact about reed-muller codes is really useful though. Thanks! –  Adam Apr 11 '12 at 16:59
    
@Adam Thanks. I just edited my answer to add more information about the codes. –  Dilip Sarwate Apr 11 '12 at 17:13

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.