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