# Finding all solutions for an equation system

I have a vector of numbers $x_i$ that can only have the values $0$ or $1$.

I need to find all the possible combinations $(x_1,x_2,x_3,x_4,x_5,x_6)$ such that:

$$\begin{cases} x_1+x_5+x_6 \ \mathrm{is\ odd}\\ x_2+x_4+x_6 \ \mathrm{is\ odd} \\ x_3+x_4+x_5 \ \mathrm{is\ odd} \end{cases}$$

How could I do this? I mean, I can think of some combinations but I don't know how to find all of them, or the number of possible solutions.

### First a preliminary remark:

If we fix one number $N$ in such a conditional, we find $$a + b + N \text{ odd}, a,b,N \in \{0, 1\}$$ implies for $N = 1$: $$a + b + 1 \text{ odd} \Leftrightarrow a = b$$ and for $N = 0$: $$a + b + 0 \text{ odd} \Leftrightarrow a \ne b \Leftrightarrow a = 1 - b$$

### Now we can start by systematically making cases:

• $x_1 = 1$
Equation (I) now reads $1 + x_5 + x_6$ is odd, i.e. $x_5 = x_6$
• $x_5 = x_6 = 1$
Now Equations (II) and (III) combine to $x_2 = x_3 = x_4$, so we have $(1, 0, 0, 0, 1, 1)$ and $(1, 1, 1, 1, 1, 1)$ as solutions
• $x_5 = x_6 = 0$
This means $x_2 \ne x_4$ and $x_3 \ne x_4$, so $x_2 = x_3 = 1 - x_4$.
Again we find two solutions:
$(1, 0, 0, 1, 0, 0)$ and $(1, 1, 1, 0, 0, 0)$
• $x_1 = 0 \Rightarrow x_5 \ne x_6$
• $x_5 = 1, x_6 = 0$ gives us $x_3 = x_4$ and $x_2 \ne x_4$, so $x_2 = 1 - x_3 = 1 - x_4$ and we get the two solutions $(0, 1, 0, 0, 1, 0)$ and $(0, 0, 1, 1, 1, 0)$
• $x_5 = 0, x_6 = 1$ and we get $x_2 = x_4$ and $x_3 \ne x_4$, so $x_2 = 1 - x_3 = x_4$ yielding the final two solutions $(0, 1, 0, 1, 0, 1)$ and $(0, 0, 1, 0, 0, 1)$
• That was smooth! Thank you. Those would be all the solutions, right? I'm asking just in case, because I don't think there are more possibilities – Tendero Nov 3 '16 at 17:40
• @Tendero Yes, these are all by exhaustion. I provided reason for the derivations in a preliminary note, just to clarify. Can you prove these statements yourself? – AlexR Nov 3 '16 at 17:41
• Yes, I get that but I didn't know if there was some systematic method to follow to get all the possibilities. Thanks again! – Tendero Nov 3 '16 at 17:42

This question is really about solving the system

$$\begin{cases} x_1+x_5+x_6 =1 \\ x_2+x_4+x_6 =1 \\ x_3+x_4+x_5 =1 \end{cases}$$

in $\mathbb{Z}/2\mathbb{Z}$. Since that's a field, we should be able to use all the techniques of linear algebra, and just reduce a matrix:

$\left[\begin{array}{cccccc|c} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array}\right]$

This matrix is already in reduced row-echelon form, so there are three free variables, and 8 solutions, corresponding to the eight possible values of $x_4$, $x_5$, and $x_6$, and completed by the equations $x_1=1+x_5+x_6$, $x_2=1+x_4+x_6$, and $x_3=1+x_4+x_5$, with all addition being performed in $\mathbb{Z}/2\mathbb{Z}$.

Namely:

\begin{align} (x_4,x_5,x_6)=(0,0,0) &\implies (1,1,1,0,0,0) \\ (x_4,x_5,x_6)=(0,0,1) &\implies (0,0,1,0,0,1) \\ (x_4,x_5,x_6)=(0,1,0) &\implies (0,1,0,0,1,0) \\ (x_4,x_5,x_6)=(0,1,1) &\implies (1,0,0,0,1,1) \\ (x_4,x_5,x_6)=(1,0,0) &\implies (1,0,0,1,0,0) \\ (x_4,x_5,x_6)=(1,0,1) &\implies (0,1,0,1,0,1) \\ (x_4,x_5,x_6)=(1,1,0) &\implies (0,0,1,1,1,0) \\ (x_4,x_5,x_6)=(1,1,1) &\implies (1,1,1,1,1,1) \end{align}

Reflecting back on the original problem, since each of $x_1, x_2, x_3$ each occur in precisely one condition, we see that the other three variables can be chosen freely, and then $x_1$ picked to make the first condition work, etc.

• Much cleaner than my solution. You might want to list all eight solutions obtained this way. +1 – AlexR Nov 3 '16 at 18:19