# How to solve this 0-1 linear equations?

$A=\left(\begin{matrix} 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{matrix}\right)$

how to solve the linear equations $Ax=b \pmod 2$.

$x=(x_1,x_2,x_3, ... , x_9)$, $x_i\in\{0,1\}$.

$b=(b_1,b_2,b_3, ... , b_9)$, $b_i\in\{0,1\}$.

for any vector b, is there always a solution?

And I need a optimal solution $\min\sum{}x_i$, is it identical?

• Check out Cramer's rule for the answer to your first question. – Erik Vesterlund Jul 28 '13 at 1:45
• i get this linear equations from a Lights out like game, and i got difficulty to calculate the det(A). – Charles Bao Jul 28 '13 at 1:49
• I get $\operatorname{det}\mathbf{A} = 80$. Can you figure it out from here? – AnonSubmitter85 Jul 28 '13 at 1:55
• actually it's a 0-1 system, i've find out the det(A)=0 – Charles Bao Jul 28 '13 at 2:08
• @CharlesBao I calculated it in $\mathbb{Q}$ not $\mathbb{Z}_2$. – AnonSubmitter85 Jul 28 '13 at 2:18

The general rule is that if the determinant of your coefficient matrix $A$ is invertible in whatever number system you are working in, then the matrix $A$ will be invertible as well meaning that you are guaranteed a unique solution $x$ for any $b$ where $Ax=b$. This condition is both necessary and sufficient.

Working in $\mathbb{F}_2$ in this case, $det(A)=0$ so $A$ is not invertible meaning that for some $b$'s you may have many solutions (but finitely many in this case because the underlying field $\mathbb{F}_2$ is a finite field) and for some $b$'s you won't have any solutions at all. For example,

$$b = [1,1,1,1,1,1,1,1,0]^T$$

doesn't have any solution with your given $A$. On the other hand, if we let

$$b = [0,0,0,0,0,0,0,0,0]^T$$

then we actually have four different solutions

$$x_1=[0,0,1,1,1,0,0,0,1]^T$$ $$x_2=[1,0,1,0,1,0,0,1,0]^T$$ $$x_3=[0,1,1,1,0,0,1,0,0]^T$$ $$x_4=[1,1,1,1,1,1,0,0,0]^T$$

and the reason for this is that when we row reduce this matrix in $\mathbb{F}_2$ we get

$$\left(\begin{matrix} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix}\right).$$

Note that in the real field $\mathbb{R}$, $det(A)=80$ which is indeed invertible in $\mathbb{R}$ so the row reduced form in $\mathbb{R}$ will be the $9\times9$ identity matrix and in that case you will have a unique solution for every real $b$.

$$b=[0,0,0,0,0,0,0,0,1]^T$$
and even for this $b$ there is no solution. The answer to your first comment is in general for a small system like this just simple gaussian elimination would work. If you want to use software like MATLAB/Mathematica then it is fairly easy. It is just a matter of which software (versions/toolboxes/etc.) do you have available. It won't be that hard to do. If you want to do this by hand or write your little solver like in FORTRAN/C++, then there are a few nice tricks which working in $\mathbb{F}_2$ speed up things such as addition being the same as subtraction in $\mathbb{F}_2$ because $-1=1$. Also to get (almost no speed increase in this small 9x9 case) instead of using integers, you can use booleans (to save memory as well) and then just XOR instead of addition.
It all depends on the scope of the problem. Is 9x9 the only case or will you work with bigger matrices like $100000000\times100000000$ matrices? How many $b$'s do you need to solve for? Just a single $b$? A few $b$'s or a lot of $b$'s? Do you want to do this by hand or by software? If software, then which software do you have available? Do you want to write your own code or use like MATLAB/Mathematica? If coding, how much do you value the complexity of the code versus the timing and the memory requirements of the code? The basic method will be gaussian elimination though. Because of the underlying field being finite, a lot of methods which work in reals don't work here.
• i've tried gaussian elimination, and got that the $9\times9$ equations has solution if and only if the $b$ satisfies: 1) $b_3+b_4+b_5+b_9=0$, 2) $b_2+b_4+b_6+b_8=0$, 3) $b_1+b_5+b_6+b_7=0$. Am i right? and can this be simplified? – Charles Bao Jul 28 '13 at 9:13