2
$\begingroup$

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{equation} \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} \end{equation}$$

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?

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

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

Let's look at the determinant, if you don't trust Gauss Elimination. I'll develop with respect to the first row: \begin{align} \det A&=(-1)^{1+1}\det\begin{pmatrix}3 & 6 \\ 2 & 5\end{pmatrix} +0+(-1)^{1+3}\cdot 3\det\begin{pmatrix}5 & 3 \\ 6 & 2\end{pmatrix}\\ &=(15-12)+3(10-18)\\ &=3+3(-8)=3-24=-21=0 \end{align} so you can't apply Cramer's rule.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Toralf Westström Dec 10 '13 at 23:41
  • 1
    $\begingroup$ @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. $\endgroup$ – egreg Dec 10 '13 at 23:43

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.