Find binary solution over non square matrix

savecancel

So you have a matrix equation over $GF(2)$ of the form

In Sage, the kernel can be computed with function .right_kernel() - like in the example below:

sage: M = matrix(GF(2), [[1, 0, 1, 1], [1, 0, 0, 1]])                                                                                                                                                      
sage: K = M.right_kernel()                                                                                                                                                                                 
sage: K                                                                                                                                                                                                    
Vector space of degree 4 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 0 0 1]
[0 1 0 0]
sage: list(K)                                                                                                                                                                                              
[(0, 0, 0, 0), (1, 0, 0, 1), (0, 1, 0, 0), (1, 1, 0, 1)]

In this example, the kernel $K$ of $M$ is spanned by two vectors. So, $K$ is composed of $2^2=4$ vectors, including the zero vector.