Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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?

share|improve this question
1  
Check out Cramer's rule for the answer to your first question. –  Erik Vesterlund Jul 28 '13 at 1:45
    
What have you tried so far? Where did you run into difficulty? –  AnonSubmitter85 Jul 28 '13 at 1:46
    
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
show 1 more comment

1 Answer

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


Addendum #1

The answer to your second comment is no. Let

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

share|improve this answer
    
i'm wondering how to get the solutions for a given b. –  Charles Bao Jul 28 '13 at 3:50
    
is that mean if and only if it has more than four 0s in b, than it has solutions. –  Charles Bao Jul 28 '13 at 3:55
    
@CharlesBao Look at my addendum. –  Fixed Point Jul 28 '13 at 4:17
    
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
    
@CharlesBao No, this is wrong. There are four conditions in this case. And only your condition 3 is one of the four correct conditions. The first two are wrong. –  Fixed Point Jul 28 '13 at 10:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.