ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 10 Jan 2016 13:00:41 -0600Solving system of linear equations over GF(2)http://ask.sagemath.org/question/32145/solving-system-of-linear-equations-over-gf2/ 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!Sun, 10 Jan 2016 09:02:14 -0600http://ask.sagemath.org/question/32145/solving-system-of-linear-equations-over-gf2/Answer by tmonteil for <p>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.</p>
<p>Thank you in advance!</p>
http://ask.sagemath.org/question/32145/solving-system-of-linear-equations-over-gf2/?answer=32146#post-id-32146You 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
Sun, 10 Jan 2016 13:00:41 -0600http://ask.sagemath.org/question/32145/solving-system-of-linear-equations-over-gf2/?answer=32146#post-id-32146