3
$\begingroup$

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

  • 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?2012-04-10
  • 0
    Should most of the "basis" in this question have been "matrix"? Otherwise I have trouble making sense of it.2012-04-10
  • 0
    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.2012-04-10
  • 0
    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.2012-04-11
  • 0
    @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.2012-04-11
  • 0
    Elementary column operations are invertible. He can find a basis for the reduced matrix, and then apply the inverse of the column reduction operations.2012-04-11
  • 0
    @NieldeBeaudrap, yeah that would work. For this example matrix it would actually work very well, indeed! But I don't see much advantage in the general case. Let's wait for the OP to comment.2012-04-11
  • 0
    @Adam, could you please tell a bit more. Do you know anything else about your check matrices? What is the application you are working on? I have seen instances of this problem that I wouldn't want to touch with a bargepole (e.g. LDPC-codes for a Chinese Broadcasting standard) :-)2012-04-11
  • 0
    @Adam: In reference to your edit, could you clarify what you mean when you say that you are splitting the vector space and using some of it elsewhere? Do you mean that your matrix is large enough that you would prefer not to make a second copy to perform the reduction, and cannot transform the original copy either as it is used elsewhere? Or perhaps that some of the rows/columns are used by another part of your program?2012-04-12

1 Answers 1

4

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$.

  • 0
    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?2012-04-11
  • 0
    @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.2012-04-11
  • 0
    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.2012-04-11
  • 0
    This particular fact about reed-muller codes is really useful though. Thanks!2012-04-11
  • 0
    @Adam Thanks. I just edited my answer to add more information about the codes.2012-04-11