How to determine the number of possible solutions the system of equations in $\mathbf{Z}_2$

Question

Let us consider the system of equations in $\mathbf{Z}_2$:
$\begin{align} & x_1+x_2+x_3=0\\ & x_2+x_3+x_4=0 \end{align}$

Here the operation "+" is "xor", i.e., $x_i+x_j=0$ for $x_i=x_j$ and $x_i+x_j=1$ for $x_i\neq x_j$.

How can I predict how many solutions are there and how can I find them?

What will be the number of solutions if the equations are as follows:
$\begin{align} & x_1+x_2+x_3=1\\ & x_2+x_3+x_4=1 \end{align}$.

Answer 1

\begin{align} & x_1+x_2+x_3=0\\ & x_2+x_3+x_4=0 \end{align}

Since $x+x=0$ for all $x$, adding the two equations gives

$$ x_1+x_4=0$$

adding $x_4$ to both sides gives

$$x_1=x_4$$

Adding $x_1$ to both sides of $x_1+x_2+x_3=0$ gives $x_2+x_3=x_1$.

So there are four solutions:

$$\begin{eqnarray} x&=(1,1,0,1)\\ x&=(1,0,1,1)\\ x&=(0,1,1,0)\\ x&=(0,0,0,0) \end{eqnarray}$$

For the second system

\begin{align} & x_1+x_2+x_3=1\\ & x_2+x_3+x_4=1 \end{align}

adding the two equations together also gives you $ x_1+x_4=0$, so again we have that $x_1=x_4$.

You should be able to finish this one yourself.

Answer 2

Since for $x \in (\mathbb{Z}_2,+)$, we have $x^{-1} = x$, we can put the matrix into row-echelon form quite easily.

$$ \begin{align} x_{1} + x_{2} + x_{3} &= 0 \\ x_{2} + x_{3} + x_{4} &= 0 \end{align} $$

has the corresponding matrix

$$ \left(\begin{array}{cccc|c} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \end{array}\right) $$

Now performing the row operation

$$ R_{1} + R_{2} \rightarrow R_{1} $$

We have our row-echelon matrix.

$$ \left(\begin{array}{cccc|c} 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 \end{array}\right) $$

Notice we have 2 free variables so we have

$$ \begin{align} x_{1} &= t \\ x_{2} &= s + t \\ x_{3} &= s \\ x_{4} &= t \end{align} $$

Or if you prefer column vector notation

$$ \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} s + \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} t $$

Where $s,t \in \mathbb{Z}_{2}$

As for the number of solutions you know you have 2 ways of choosing the first free variable and 2 ways of choosing the second free variable so how many ways can you choose both of them?

You can use this same approach to solve your second problem.