# Solving system of linear equations over GF(2)

I tried solving system of equations using Matrix's solve_right(x) method. However, I want to check if the solution is unique. How can I achieve this? For a square matrix I do it by checking if A.determinant() != 0 (where A is the coefficients matrix). Is there some built in function to test uniqueness of matrix equation solution? I would like to return the solution if it is unique and show a message if there is no solution, or multiple solutions exist.

Thank you in advance!

edit retag close merge delete

Sort by ยป oldest newest most voted

You should use the kernel of a linear map (or a matrix, in which case you should specify whether the action is left or right). Both are implemented in Sage.

Here is an example:

sage: A = random_matrix(ZZ,3,4)
sage: A
[  1  -3  -2   0]
[  2   1   1  -1]
[-31   1 -12   1]

sage: b = vector((1,1,1))
sage: a = A.solve_right(b)
sage: a
(26/29, 43/29, -66/29, 0)
sage: A*a == b
True


So, in this case there is a solution to the equation you are trying to solve (if there is no solution, Sage will raise a ValueError: matrix equation has no solutions, so you have to use a try: except: statement to deal with that).

Now, the set of solutions is the set of a+c where c belongs to the kernel of A. You can get this kernel as follows:

sage: K = A.right_kernel()
sage: K
Free module of degree 4 and rank 1 over Integer Ring
Echelon basis matrix:
[ 37  69 -85  58 ]


And check the previous statement:

sage: k = K.basis()[0]
sage: k
(37, 69, -85, 58)
sage: A*k
(0, 0, 0)
sage: A * (a+k) == b
True
sage: A * (a+42*k) == b
True

more