# Find all solutions for a system of linear equations over a given field

My Problem is: to find all Solutions for the following given System of linear equations over the Field $K = \mathbb{Z}_{/7}$

The System is given with:

$$$$\begin{split} x_1\quad\quad\quad + 3x_3 &= 5 \\ 5x_1 + 3x_2 + 6x_3 &= 3 \\ 6x_1 + 2x_2 + 5x_3 &= 6 \\ \end{split}$$$$

My Approach was: i can see this is inhomogenous System of linear Equations. The given Field is $$\mathbb{Z}_{/7}=\{ 0,1,2,3,4,5,6\}$$ so i have to calculate in Modulo 7, i think. My task seems to be to find the general solution of this System.

I tried the Cramer's rule.

$$(A\ \ b)=\left(\begin{array}{ccc|c} 1 & 0 & 3 & 5 \\ 5 & 3 & 6 & 3 \\ 6 & 2 & 5 & 6 \end{array}\right)$$

Since this is not Zero: $$\det A = \left|\begin{array}{ccc} 1 & 0 & 3 \\ 5 & 3 & 6 \\ 6 & 2 & 5 \end{array}\right|=-8 \neq 0$$ there must be a solution. i think.

$$x_1 = \frac{\det A_1}{\det A}=\frac{ \left|\begin{array}{ccc} 5 & 0 & 3 \\ 3 & 3 & 6 \\ 6 & 2 & 5 \end{array}\right| }{ \left|\begin{array}{ccc} 1 & 0 & 3 \\ 5 & 3 & 6 \\ 6 & 2 & 5 \end{array}\right| } =\frac{0}{-8}=0$$

$$x_2 = \frac{\det A_2}{\det A}=\frac{ \left|\begin{array}{ccc} 1 & 5 & 3 \\ 5 & 3 & 6 \\ 6 & 6 & 5 \end{array}\right| }{ \left|\begin{array}{ccc} 1 & 0 & 3 \\ 5 & 3 & 6 \\ 6 & 2 & 5 \end{array}\right| }=\frac{0}{-8}=0$$

$$x_3 = \frac{\det A_3}{\det A}=\frac{ \left|\begin{array}{ccc} 1 & 0 & 5 \\ 5 & 3 & 3 \\ 6 & 2 & 6 \end{array}\right| }{ \left|\begin{array}{ccc} 1 & 0 & 3 \\ 5 & 3 & 6 \\ 6 & 2 & 5 \end{array}\right| }=\frac{-7}{-8}=\frac{7}{8}$$

Okay now i have a solution. $$\left(\begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array}\right) = \left(\begin{array}{c} 0 \\ 0 \\ \frac{7}{8} \end{array}\right)$$That Looks cool. But my Task is to find ALL Solutions. But the given System has as many unknowns as equations. So i learned there should be only one solution.

My conclusion is: there is either just one solution (and this one is "all") or i made one (or more) mistakes.

My question is: am i right? And in case i am wrong, what are my mistakes? How can i solve such a Task?

• I am definitly sure, my determinants are incorrect. :/ – Toralf Westström Dec 10 '13 at 22:16

\begin{align} (A\ \ b)= \left(\begin{array}{ccc|c} 1 & 0 & 3 & 5 \\ 5 & 3 & 6 & 3 \\ 6 & 2 & 5 & 6 \end{array}\right) &\to \left(\begin{array}{ccc|c} 1 & 0 & 3 & 5 \\ 0 & 3 & 5 & 6 \\ 0 & 2 & 1 & 4 \end{array}\right)\quad R_2-5R1, R_3-6R_1 \\ &\to \left(\begin{array}{ccc|c} 1 & 0 & 3 & 5 \\ 0 & 1 & 4 & 2 \\ 0 & 2 & 1 & 4 \end{array}\right)\quad 5R_2 \\ &\to \left(\begin{array}{ccc|c} 1 & 0 & 3 & 5 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0 \end{array}\right)\quad R_3-2R_2 \end{align} So the solution set is $$\begin{pmatrix}5-3h\\2-3h\\h\end{pmatrix}\quad (h\in\mathbb{Z}/7\mathbb{Z})$$
• oh allright.. and so the solution set consits of seven different solutions/vectors like: $$\left(\begin{array}{c} 5-3\cdot 1 \\ 2-3\cdot 1 \\ 1 \end{array}\right) = \left(\begin{array}{c} 2 \\ 6 \\ 1 \end{array}\right)$$ right? – Toralf Westström Dec 10 '13 at 23:41
• @ToralfWestström Yes, any choice for $h$ is good. Since $\mathbb{Z}/7\mathbb{Z}$ is a field, the elimination method works the same as in the real numbers; just the arithmetic is different. – egreg Dec 10 '13 at 23:43