How to solve 3 equations over $\mathbb{Z}$?

Question

I have those 3 equations: $$-5x+2y+4z+w=8\\ 27x+10y+2z+7w=6\\ -20x-6y-4w=-10$$

I tried to solve them over $\mathbb{Z}$ via making a matrix at $SNF$ (Smith Normal Form), So I began with this matrix: $$\begin{bmatrix}-5 & 2 & 4 & 1\\ 27 & 10 & 2 & 7\\ -20 & -6 & 0 & -4 \end{bmatrix}$$

And what I get is this (after many calculations):

\begin{bmatrix}1 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0 \end{bmatrix}

But when I trying to solve via this, I get:

• $x=\frac 8 1=8 $
• $y = \frac 6 {2}=3$
• $z=\frac {-10}{2} =-5$
  (Because we learn that we need to divide $x$ by $d_1$, $y$ by $d_2$ and so on...)

Now it's wrong because I can fit any $w$ for this solution.
Can you help me please and tell me where is my mistake?

Thank you!

Answer 1

You wish to solve the system $Ax=b$ over $\Bbb Z$ where \begin{align*} A &= \left[\begin{array}{rrrr} -5 & 2 & 4 & 1 \\ 27 & 10 & 2 & 7 \\ -20 & -6 & 0 & -4 \end{array}\right] & b&=\left[\begin{array}{r} 8 \\ 6 \\ -10 \end{array}\right] \end{align*} To do so, consider the Smith form $$ \overset{U}{\left[\begin{array}{rrr} 1 & 0 & 0 \\ 4 & 0 & 1 \\ 1 & 1 & 2 \end{array}\right]} \overset{A}{\left[\begin{array}{rrrr} -5 & 2 & 4 & 1 \\ 27 & 10 & 2 & 7 \\ -20 & -6 & 0 & -4 \end{array}\right]} \overset{V}{\left[\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 1 & -8 & -4 \\ 0 & 0 & 1 & 3 \\ 1 & -2 & 12 & 1 \end{array}\right]}=\overset{D}{\left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 6 & 0 \end{array}\right]} $$ Here, $U$ and $V$ are unimodular, which means that $U$ and $V$ are invertible over $\Bbb Z$.

Now, note that $Ax=b$ is $UAVV^{-1}x=Ub$ which reduces to $DV^{-1}x=Ub$. So, we can solve our system by first solving $Dy=Ub$ for $y$ and then taking $x=Vy$.

The system $Dy=Ub$ is $$ \overset{D}{\left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 6 & 0 \end{array}\right]} \overset{y}{\left[\begin{array}{r} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array}\right]} = \overset{Ub}{\left[\begin{array}{r} 8 \\ 22 \\ -6 \end{array}\right]} $$ This gives $y=\langle 8, 11, -1, y_4\rangle$.

Finally, we have $x=Vy$ which gives $$ x=\left[\begin{array}{r} y_{4} \\ -4 \, y_{4} + 19 \\ 3 \, y_{4} - 1 \\ y_{4} - 26 \end{array}\right] $$

To compute the above Smith form, consider the following operations. \begin{align*} \left[\begin{array}{rrrr|rrr} -5 & 2 & 4 & 1 & 1 & 0 & 0 \\ 27 & 10 & 2 & 7 & 0 & 1 & 0 \\ -20 & -6 & 0 & -4 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right] & \to \left[\begin{array}{rrrr|rrr} 1 & 2 & 4 & -5 & 1 & 0 & 0 \\ 7 & 10 & 2 & 27 & 0 & 1 & 0 \\ -4 & -6 & 0 & -20 & 0 & 0 & 1 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \\ &\to \left[\begin{array}{rrrr|rrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & -4 & -26 & 62 & -7 & 1 & 0 \\ 0 & 2 & 16 & -40 & 4 & 0 & 1 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & -2 & -4 & 5 & 0 & 0 & 0 \end{array}\right] \\ &\to \left[\begin{array}{rrrr|rrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 16 & -40 & 4 & 0 & 1 \\ 0 & -4 & -26 & 62 & -7 & 1 & 0 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & -2 & -4 & 5 & 0 & 0 & 0 \end{array}\right] \\ &\to \left[\begin{array}{rrrr|rrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 4 & 0 & 1 \\ 0 & 0 & 6 & -18 & 1 & 1 & 2 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & -8 & 20 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & -2 & 12 & -35 & 0 & 0 & 0 \end{array}\right] \\ &\to \left[\begin{array}{rrrr|rrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 4 & 0 & 1 \\ 0 & 0 & 6 & 0 & 1 & 1 & 2 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & -8 & -4 & 0 & 0 & 0 \\ 0 & 0 & 1 & 3 & 0 & 0 & 0 \\ 1 & -2 & 12 & 1 & 0 & 0 & 0 \end{array}\right] \end{align*}

Answer 2

Let's first solve the system in the reals.
We get $$ {\bf x} = {\bf x}_{\,0} + \lambda \;{\bf x}_{\,1} = \left( {\matrix{ {26} \cr { - 85} \cr {77} \cr 0 \cr } } \right) + \lambda \;\left( {\matrix{ 1 \cr { - 4} \cr 3 \cr 1 \cr } } \right) $$

Now the $\gcd$ of the components of ${\bf x}_{\,1}$ is $1$, and ${\bf x}_{\,1}, \; {\bf x}_{\,2}$ are independent, so any integer value of $\lambda$ is a solution over $\mathbb Z$.

Answer 3

Above equation shown below:

$-5x+2y+4z+w=8 ------ (A)\\ 27x+10y+2z+7w=6 -----(B)\\ -20x-6y-4w=-10 -----(C)$

From, $[2(B)-(A)+3(C)]$ we get: $w=(x-26)$

From, $(C)$ we get, $w=[-(y+85)/(4)]$

From, $(A)$ we get, $w=[(z-77)/(3)]$

Taking, $w=1$, we get:

$(x,y,z,w)=(27,-89,80,1)$