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

Question

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!

Answer 1

Brute-forcing in Haskell:

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$.

Answer 2

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]])]

Answer 3

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.

Answer 4

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):