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


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.

| cite | improve this answer | |
  • $\begingroup$ I still don't get how to get that "smallest"solution from that matrice :/ $\endgroup$ – JoshuaM Mar 20 '13 at 17:39
  • $\begingroup$ @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. $\endgroup$ – Math Gems Mar 20 '13 at 17:43
  • $\begingroup$ Yea I know, and can you help me with the "smallest"solution ?:) $\endgroup$ – JoshuaM Mar 20 '13 at 17:47
  • $\begingroup$ @JoshuaM For the minimization problem you might find some techniques of interest by searching on "frobenius problem linear programming". $\endgroup$ – Math Gems Mar 21 '13 at 3:33

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\,$)

| cite | improve this answer | |
  • $\begingroup$ 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) $\endgroup$ – JoshuaM Mar 20 '13 at 16:39
  • $\begingroup$ 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\,$ ... $\endgroup$ – DonAntonio Mar 20 '13 at 18:08

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.