Solving a linear system over $\mathbb{Z}_{5}$

Question

I would like to ask how to solve this matrix, if I substitute for z (x, y, z) z = 4, I can't calculate the matrix. I tried to adjust the matrix to this shape, but I don't know how to proceed.

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 1 & 0 & 0 & 4\\ 1 & 3 & 4 & 0 \end{array} } \right)$ in $\mathbb{Z}_{5}$

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 0 & 1 & 3 & 2\\ 0 & 0 & 0 & 0 \end{array} } \right)$

Answer 1

start:

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 1 & 0 & 0 & 4\\ 1 & 3 & 4 & 0 \end{array} } \right)$

first steps: subtract 1st row from 2nd and 3rd, to eliminate the other 1's in the first column

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 0 & 3 & 4 & 1\\ 0 & 1 & 3 & 2 \end{array} } \right)$

where I use that $-1 \equiv 4, -2 \equiv 3, -3 \equiv 2$ in $\Bbb Z_5$. The pivot 3 on place $(2,2)$ has an inverse 2 over $\Bbb Z_5$ so I multiply the 2nd row by $2$ (modulo $5$) to make for easier computations:

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 0 & 1 & 3 & 2\\ 0 & 1 & 3 & 2 \end{array} } \right)$

We subtract the two identical rows at the end to get:

$\left( {\begin{array}{ccc|c} 1 & 2 & 1 & 3\\ 0 & 1 & 3 & 2\\ 0 & 0 & 0 & 0 \end{array} } \right)$

So we have a consistent system (so there are solutions) that is underdetermined. So there will be $5$ solutions, depending on the value we pick for the free variable $z$, we can solve it in terms of this free variable:

$y + 3z = 2$ so $y = 2-3z = 2 + 2z$

$x+2y+z = 3$ so $x+ 4z + 4+ z = 3$ so $x+4=3$ so $x=4$, as $5z\equiv 0$.

So we get the solutions $\{(4,2+2z, z) \mid z \in \Bbb Z_5\}$, a set of $5$ vectors, as expected.

Answer 2

This is the linear system $Ax=b\;$ with $$ A=\pmatrix{1 & 2 & 1 \\1 & 0 & 0 \\1 & 3 & 4}\qquad b = \pmatrix{3\\4\\0} $$ Using ${\mathbb Z}_{5}$ arithmetic and examining the powers of $A^k$ one finds that $$\eqalign{ A^5 &= A \quad&\big({\rm periodic}\big) \\ A^4 &\ne I \quad&\big({\rm not\,invertible}\big) \\ A^3 &= A^+ \quad&\big({\rm generalized\,inverse}\big) \\ }$$ Using the generalized inverse, one can write the solution of the system as $$\eqalign{ x &= A^+b + \left(I-A^+A\right)z \\ &= A^3b + \left(I-A^4\right)z \\ }$$ where $z$ is an arbitrary vector and $(I-A^4)$ is the nullspace projector.
In terms of components, this becomes $$\eqalign{ x &= \pmatrix{4&3&4\\4&0&0\\4&2&1}\pmatrix{3\\4\\0} + \pmatrix{0&0&0\\1&3&1\\3&4&3}\pmatrix{z_1\\z_2\\z_3} \\ &= \pmatrix{4\\2\\0} + \pmatrix{0\\z_1+3z_2+z_3\\3z_1+4z_2+3z_3} \\ }$$ Check the result by setting $z_k=0\,$ to obtain $$\eqalign{ Ax &= \pmatrix{1&2&1\\1&0&0\\1&3&4}\pmatrix{4\\2\\0} &= \pmatrix{3\\4\\0} &= b \\ }$$ To connect this with Henno's result note that $$\eqalign{ \lambda &= 3z_1+4z_2+3z_3 \\ 2\lambda &= 6z_1+8z_2+6z_3 \;\overset{{\mathbb Z}_{5}}{\longrightarrow}\; z_1+3z_2+z_3 \\ }$$