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

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

• Hint: just as with the regular systems of linear equations make the matrix of your system uppertriangular – Michael Freimann Aug 5 '16 at 15:14
• Did you mean to say for $x_i \neq x_j$ instead of $i \neq j$? – m1cky22 Aug 5 '16 at 15:14
• @m1cky22, I mean if $x_i=1$ then $x_j=0$ and conversely – user356595 Aug 5 '16 at 15:42
• @MichaelFreimann, can you illustrate it with answer – user356595 Aug 5 '16 at 15:47
• The usual results about underdetermined systems from linear algebra apply. You get all the solutions to the unhomogeneous system by adding an arbitrary solution of the homogeneous system to a particular solution of the unhomogeneous system (assuming one exists). The solutions of the homogeneous system form a subspace of dimension $t$ (=number of variables minus the rank of the matrix). Therefore there will be $2^t$ solutions if there is at least one. – Jyrki Lahtonen Aug 5 '16 at 16:42

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.

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