ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 06 Jul 2021 21:32:54 +0200Find binary solution over non square matrixhttps://ask.sagemath.org/question/57894/find-binary-solution-over-non-square-matrix/ I have system of m homogeneous linear equations of n variables over GF(2) where m>n.
We know all zero is a solution. How to find any other solution? I know
there are other solutions as rank of the corresponding matrix < n.
Tue, 06 Jul 2021 20:53:51 +0200https://ask.sagemath.org/question/57894/find-binary-solution-over-non-square-matrix/Answer by Max Alekseyev for <p>I have system of m homogeneous linear equations of n variables over GF(2) where m>n.
We know all zero is a solution. How to find any other solution? I know
there are other solutions as rank of the corresponding matrix < n. </p>
https://ask.sagemath.org/question/57894/find-binary-solution-over-non-square-matrix/?answer=57898#post-id-57898So you have a matrix equation over $GF(2)$ of the form $${\bf M}x = {\bf 0},$$ where $M$ is an $m\times n$ matrix. The solutions to this equation form the (right) [kernel](https://en.wikipedia.org/wiki/Kernel_(linear_algebra)) of $M$, which is a linear subspace of $GF(2)^n$.
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.Tue, 06 Jul 2021 21:32:54 +0200https://ask.sagemath.org/question/57894/find-binary-solution-over-non-square-matrix/?answer=57898#post-id-57898