2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ No. I just want it to display as follows: x1=x5=0, x6=x7, x2+X3+x4=0 $\endgroup$ – Mary Feb 12 '17 at 13:28
  • $\begingroup$ 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.$$ . $\endgroup$ – Mary Feb 12 '17 at 13:35
0
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Palmieri Feb 13 '17 at 6:40
  • $\begingroup$ Let us know what your progress is and what you have tried so far, and ask some specific questions. $\endgroup$ – John Palmieri Feb 13 '17 at 16:13
0
$\begingroup$

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):
$\endgroup$
  • $\begingroup$ .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\}$$ $\endgroup$ – Mary Apr 23 '17 at 8:29
  • $\begingroup$ If you just want to print each on separate lines, you can use: print~(sol): $\endgroup$ – JP May Apr 24 '17 at 19:55
  • $\begingroup$ 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$$ $\endgroup$ – Mary Apr 25 '17 at 23:48
  • $\begingroup$ 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$$ $\endgroup$ – Mary Apr 25 '17 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.