0
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ Hint: just as with the regular systems of linear equations make the matrix of your system uppertriangular $\endgroup$ – Michael Freimann Aug 5 '16 at 15:14
  • 1
    $\begingroup$ Did you mean to say for $x_i \neq x_j$ instead of $i \neq j$? $\endgroup$ – m1cky22 Aug 5 '16 at 15:14
  • $\begingroup$ @m1cky22, I mean if $x_i=1$ then $x_j=0$ and conversely $\endgroup$ – user356595 Aug 5 '16 at 15:42
  • $\begingroup$ @MichaelFreimann, can you illustrate it with answer $\endgroup$ – user356595 Aug 5 '16 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 5 '16 at 16:42
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.