Homogeneous system of linear equations with coefficients over $\mathbb{F}_2$

Solve the following homogeneous systems of linear equations with coefficients over field $\mathbb{F}_2$:

 x1+x2+x3+x4+x5+x6+x7 = 0
x1=0
x2+x3+x4 =0
x5=0


I want to output on the Maple or Sympy or Sage program following:

x1=x5=0
x6=x7
x2+x3+x4=0


I want to solve a general homogeneous systems with coefficients over field $\mathbb{F}_2$ and output same as above.

I hope that someone can help. Thanks!

Prelude> let tuples = [ (x1,x2,x3,x4,x5,x6,x7) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1], x5 <- [0,1], x6 <- [0,1], x7 <- [0,1] ]
Prelude> filter (\(x1,x2,x3,x4,x5,x6,x7)->(rem (x1+x2+x3+x4+x5+x6+x7) 2 == 0) && (x1 == 0) && (rem (x2+x3+x4) 2 == 0) && (x5 == 0)) tuples
[(0,0,0,0,0,0,0),(0,0,0,0,0,1,1),(0,0,1,1,0,0,0),(0,0,1,1,0,1,1),(0,1,0,1,0,0,0),(0,1,0,1,0,1,1),(0,1,1,0,0,0,0),(0,1,1,0,0,1,1)]


How many solutions are there?

Prelude> length [(0,0,0,0,0,0,0),(0,0,0,0,0,1,1),(0,0,1,1,0,0,0),(0,0,1,1,0,1,1),(0,1,0,1,0,0,0),(0,1,0,1,0,1,1),(0,1,1,0,0,0,0),(0,1,1,0,0,1,1)]
8


Solving the equations, we obtain

$$x_1 = 0 \qquad \qquad x_2 + x_3 + x_4 = 0 \qquad \qquad x_5 = 0 \qquad \qquad x_6 + x_7 = 0$$

The last equation, $x_6 + x_7 = 0$, has two solutions: $x_6 = x_7 = 0$ and $x_6 = x_7 = 1$. The equation $x_2 + x_3 + x_4 = 0$ over $\mathbb F_2$ is equivalent to the following disjunction over the integers

$$\left( x_2 + x_3 + x_4 = 0 \right) \lor \left( x_2 + x_3 + x_4 = 2 \right)$$

with the constraints $0 \leq x_2, x_3, x_4 \leq 1$. The first disjunct has $1$ solution ($x_2 = x_3 = x_4 = 0$) and the second disjunct has $\binom{3}{2} = 3$ solutions. Hence, the disjunction has $1 + 3 = 4$ solutions. Since we have $x_1 = x_5 = 0$, the total number of solutions is $4 \cdot 2 = 8$.

• No. I just want it to display as follows: x1=x5=0, x6=x7, x2+X3+x4=0 – Mary Feb 12 '17 at 13:28
• No. I just want it to display as follows: $$x_1=x_5=0, x_6=x_7, x_2+x_3+x_4=0$$. Note $x_1,x_2,x_3,x_4,x_5,x_6,x_7\not\in\mathbb{F}_2$ but coeffcient $\in\mathbb{F}_2.$ Hence, $x_6+x_7 = 0,$ we have $$x_6 = -x_7 = x_7\Leftrightarrow x_6=x_7.$$ . – Mary Feb 12 '17 at 13:35

You want to find the null space of a $4 \times 7$ matrix. Start with the RREF to determine the rank:

>>> from sympy import *
>>> A = Matrix([[1,1,1,1,1,1,1],
[1,0,0,0,0,0,0],
[0,1,1,1,0,0,0],
[0,0,0,0,1,0,0]])
>>> A.rref()
(Matrix([
[1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 1]]), [0, 1, 4, 5])


Matrix $\mathrm A$ has full row rank and, thus, its null space is $3$-dimensional. Via visual inspection it is easy to find a basis for the null space of $\mathrm A$. Note that the 3rd and 4th columns of $\mathrm A$ are copies of the 2nd column. Note also that the 7th column is a copy of the 6th.

>>> A.nullspace()
[Matrix([
[ 0],
[-1],
[ 1],
[ 0],
[ 0],
[ 0],
[ 0]]), Matrix([
[ 0],
[-1],
[ 0],
[ 1],
[ 0],
[ 0],
[ 0]]), Matrix([
[ 0],
[ 0],
[ 0],
[ 0],
[ 0],
[-1],
[ 1]])]

• How to display it in precisely as above $$x_1=x_5=0$$ $$x_6=x_7$$ $$x_2+x_3+x_4=0$$ – Mary Feb 14 '17 at 0:12
• I don't understand what you mean. – Rodrigo de Azevedo Feb 14 '17 at 0:20
• To determine the rank of any $m\times n$ matrix.then start with the ''RREF''? – Mary Feb 14 '17 at 0:53
• That would be one option. – Rodrigo de Azevedo Feb 14 '17 at 0:57
• @ Rodrigo de Azevedo. I use it in sage then it error. – Mary Feb 14 '17 at 1:03

Similar to what Rodrigo de Azevedo says in his answer, but for Sage:

sage: A = Matrix(GF(2), [[1,1,1,1,1,1,1], [1,0,0,0,0,0,0], [0,1,1,1,0,0,0], [0,0,0,0,1,0,0]])


Then compute its right kernel or its echelon form or whatever is most helpful to find your answer. It would take a little work to display it in precisely the form you want: $x_1 = x_5 = 0$, etc.

• No, it feels like I'm doing your homework for you. Work through the Sage tutorial to learn the basics, and go on from there. – John Palmieri Feb 13 '17 at 6:40
• Let us know what your progress is and what you have tried so far, and ask some specific questions. – John Palmieri Feb 13 '17 at 16:13

In Maple, the msolve command natively solves modular systems of equations. For the listed example:

msolve({x1 = 0, x5 = 0, x2+x3+x4 = 0, x1+x2+x3+x4+x5+x6+x7 = 0}, 2);


gives:

{x1 = 0, x2 = _Z1+_Z2, x3 = _Z1, x4 = _Z2, x5 = 0, x6 = _Z3, x7 = _Z3}


where the _ZNN are integers parameters. If you want to reformat the output without parameters you can use the eliminate command and digest the output.

    sol := msolve({x1 = 0, x5 = 0, x2+x3+x4 = 0, x1+x2+x3+x4+x5+x6+x7 = 0}, 2):
sol := eliminate(sol,indets(sol, suffixed(_Z,integer))):
sol := map(x-> if(op(0, x) = + and nops(x) = 2, (op(1, x) mod 2) = (op(2, x) mod 2), (x mod 2) = 0), sol[2]);


which is not identical to the OP's desired output, but close:

{x1 = 0, x5 = 0, x6 = x7, x2+x3+x4 = 0}


If you want to print each equation an a separate line, you can use the print command mapped over the solution set.

print~(sol):

• .Thank you very much! Now, I want to output in Maple: $$\{x1 = 0, x5=0, x6+x7 = 0, x2+x3+x4 = 0\}$$ arrangement of lines following: $$\{x1=0,$$ $$x5=0,$$ $$x6=x7,$$ $$x2+x3+x4=0\}$$ – Mary Apr 23 '17 at 8:29
• If you just want to print each on separate lines, you can use: print~(sol): – JP May Apr 24 '17 at 19:55
• The homogeneous systems of linear equations $$x1+x2+x3 = 0$$ $$x1+x5+x6 = 0$$ $$x7 = 0$$ $$x8 = 0$$ $$x7+x10+x11 = 0$$ $$x12+x13 = 0$$ $$x12+x14+x15 = 0$$ Results of the output in Maple: $$x10 = x11$$ $$x7 = 0$$ $$x8 = 0$$ $$x1 + x5 + x6 = 0$$ $$x12 + x14 + x15 = 0$$ $$x13 + x14 + x15 = 0$$ $$x2 + x3 + x5 + x6 = 0$$ – Mary Apr 25 '17 at 23:48
• but I want to output in Maple following: : $$x7= 0$$ $$x8=0$$ $$x10=x11$$ $$x12=x13$$ $$x1 + x5 + x6 = 0$$ $$x1 + x2 + x3 = 0$$ $$x12+x14+x15 = 0$$ – Mary Apr 25 '17 at 23:52