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.

Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe.

$$4x_1 - 2x_2 + 0x_3 = 2$$ $$-x_3 + 4x_4=1$$ Where everything is in modulo = 3

Matrice for this system is $ \left( \begin{array}{ccc} 1 & 1 & 0 & 0 & 2 \\ 0 & 0 & 2 & 1 & 1 \\ \end{array} \right)$ i think. I need only a "smallest"solution. In this case it is $(0,2,0,1)$.

I know that there are 9 solutions for this system.Thanks

share|improve this question
add comment

2 Answers 2

If you are working only over fields $\rm\:\Bbb Z/p,\:$ for prime $\rm\:p,\:$ then Gaussian elimination works fine (as it does over any field). For more general coefficient rings there are various generalizations, such as Hermite and Smith normal form algorithms.

share|improve this answer
    
I still don't get how to get that "smallest"solution from that matrice :/ –  JoshuaM Mar 20 '13 at 17:39
    
@JoshuaM You only now mentioned that you needed only a "smallest" solution. My answer is to your original question - which gave no hint of that constraint. –  Math Gems Mar 20 '13 at 17:43
    
Yea I know, and can you help me with the "smallest"solution ?:) –  JoshuaM Mar 20 '13 at 17:47
    
@JoshuaM For the minimization problem you might find some techniques of interest by searching on "frobenius problem linear programming". –  Math Gems Mar 21 '13 at 3:33
add comment

Everything's modulo $\,3\,$ :

$$4x_1-2x_2=2\iff x_1+x_2=2\iff x_2=2+2x_1$$

$$-x_3+x_4=1\iff 2x_3+x_4=1\iff x_4=1+x_3$$

So the general solution has the form

$$\left\{\,\begin{pmatrix}x_2\\2+2x_1\\x_3\\1+x_3\end{pmatrix}\;;\;\;x_1\,,\,x_3\in\Bbb F\right\}$$

Where $\,\Bbb F\,$ is the algebraic structure from where the variables are taken (seemingly, field with characteristic $\,3\,$)

share|improve this answer
    
Can you explain me how to make algorithm for that? If I am given less equation than variables? I need only the smallest solution. In this case it is (0,2,0,1) –  JoshuaM Mar 20 '13 at 16:39
    
I'm not sure how "smallest" and "biggest" orwhatever work in field with positive characteristic...anyway, the above is just ismple linear algebra appleid to a field of char. $\,3\,$ ... –  DonAntonio Mar 20 '13 at 18:08
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.