# Finding Null Space Basis over a Finite Field

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

-
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

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