Obtain all vectors from a Matrix in Java

Question

I'm facing a little problem and I'd like to get some help. The thing is I'm given this control matrix H.

      0000111111111
H =   0111000111222
      1012012012012

I'm asked to obtain all the words of this code. The theory of linear and block codes says that a word V is that word which H*Vt=0 (zero) where Vt is transposed V.

At the moment I do know there are 3^10 = 59049 possible words. That is the size of the matrix which is obtained by powering the body q in this case q=3 of the matrix to the dimension which is columns-rows.

My problem is I dont know how to generate all the vectors (words) so H*Vt = 0. How could I do that on Java? All possible combinations using 13-n vectors with 0,1 and 2. I'd also like to know if there is possible to work with matrices in Java.

[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,1] 
[0,0,0,0,0,0,0,0,0,0,0,1,0]
[0,0,0,0,0,0,0,0,0,0,0,1,1]
.... 
[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,2] 
[0,0,0,0,0,0,0,0,0,0,0,2,0]
[0,0,0,0,0,0,0,0,0,0,0,2,2]
....
[0,0,1,1,1,1,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1]
...
[1,1,2,2,2,2,2,2,2,2,2,2,2]
[1,2,2,2,2,2,2,2,2,2,2,2,2]
[2,2,2,2,2,2,2,2,2,2,2,2,2]

Thank you so much! I'd like to implement it in a general way, I mean, not only for this matrix but for every matrix I could work with

Answer 1

What you are looking for is basically enumerating all the vectors in the kernel of H. To avoid reinventing the wheel, you'll want to find a Java linear algebra library that supports solving linear systems on finite fields (which rules out most of the popular Java linear algebra libraries).

I googled "Java linear algebra finite fields" and found this library: JLinAlg, which claims to support it.

All you have to do is find a basis for the kernel of H; after that, enumerating is simply a matter of listing all the linear combinations (coordinates) in this basis.

I would go for the org.jlinalg.LinSysSolver#solutionSpace() method, which yields an AffineSubSpace that has generatingSystem() method which gives you the desired basis.