Now, for a fun bit of integer linear algebra!
The usual methods for solving the equation run into a bit of a snag, because you cannot row echelonize the augmented matrix
\left[ \begin{array}{cc|c}5 & 6 & 40 \end{array} \right]
because dividing by 5 is not an integer operation. So how do we do things systematically?
First off, it's usually easier to find nullvectors than to solve systems of equations, so let's rewrite the problem as wanting to find solutions to
\left[ \begin{array}{ccc}-40 & 5 & 6 \end{array} \right]<br />
\left[ \begin{array}{c}1 \\ x \\ y \end{array} \right] = [0]
and now, we can apply one of our trusty techniques: augment our matrix with an identity and column echelonize!
\left[ \begin{array}{ccc}-40 & 5 & 6 \\<br />
\hline<br />
1 & 0 & 0 \\<br />
0 & 1 & 0 \\<br />
0 & 0 & 1<br />
\end{array} \right]
well, we like row operations better than column operations, so let's transpose.
\left[ \begin{array}{c|ccc}<br />
-40 & 1 & 0 & 0 \\<br />
5 & 0 & 1 & 0 \\<br />
6 & 0 & 0 & 1<br />
\end{array} \right]
Recall that the point of this is if I do row reduction to reduce this matrix to
\left[ \begin{array}{c|ccc}<br />
1 & a & b & c \\<br />
0 & 1 & d & e \\<br />
0 & 0 & 1 & f<br />
\end{array} \right]
then I know that
\left[ \begin{array}{ccc}<br />
a & b & c \\<br />
1 & d & e \\<br />
0 & 1 & f<br />
\end{array} \right]<br />
\left[ \begin{array}{c} -40 & 5 & 6<br />
\end{array} \right]<br />
=<br />
\left[ \begin{array}{c} 1 & 0 & 0<br />
\end{array} \right]<br />
from which I can immediately read off the solution to my problem:
-40 * x + 5 * (dx + y) + 6 (ex + fy) = 0
or after fixing x to 1:
5(d + y) + 6(e + fy) = 40
The only snag: how to perform row reduction, if we're not allowed to divide rows by an integer? Well, we're lucky this time; we won't need it. By row permuting:
\left[ \begin{array}{c|ccc}<br />
6 & 0 & 0 & 1 \\<br />
5 & 0 & 1 & 0 \\<br />
-40 & 1 & 0 & 0<br />
\end{array} \right]
and adding multiples of the second row to the first and third:
\left[ \begin{array}{c|ccc}<br />
1 & 0 & -1 & 1 \\<br />
5 & 0 & 1 & 0 \\<br />
0 & 1 & 8 & 0<br />
\end{array} \right]
and of the first to the second
\left[ \begin{array}{c|ccc}<br />
1 & 0 & -1 & 1 \\<br />
0 & 0 & 6 & -5 \\<br />
0 & 1 & 8 & 0<br />
\end{array} \right]
permute again
\left[ \begin{array}{c|ccc}<br />
1 & 0 & -1 & 1 \\<br />
0 & 1 & 8 & 0 \\<br />
0 & 0 & 6 & -5<br />
\end{array} \right]
and reduce a bit more
\left[ \begin{array}{c|ccc}<br />
1 & 0 & 5 & -4 \\<br />
0 & 1 & 2 & 5 \\<br />
0 & 0 & 6 & -5<br />
\end{array} \right]
We have no way to reduce that 6 to a 1, but that's fine: it turns out that this is the standard form of the matrix:
. Each pivot is positive
. Each number below a pivot is zero
. Each number above a pivot is nonnegative, and less than the pivot
So, this gives us the solution:
40 = 5(2 + 6t) + 6(5 - 5t)
The other vector, incidentally, tells is the collective GCD of everything:
1 = -40 * 0 + 5 * 5 + 6 * (-4)
in linear algebra terminology, 1 is the basis for the lattice spanned by -40, 5, and 6. (A lattice is, roughly speaking, a vector space over the integers) If we had had more equations, we'd be in a higher dimensional space, and things would look less trivial.
But I never did answer how to deal with the fact that scaling a row isn't an invertible row operation -- it turns out that you don't need it! The Euclidean algorithm tells you exactly what to do to reduce your matrix. For example, to reduce
\left[ \begin{array}{cc}<br />
5 & 3 \\<br />
7 & 8<br />
\end{array} \right]
I would subtract the first from the second:
\left[ \begin{array}{cc}<br />
5 & 3 \\<br />
2 & 5<br />
\end{array} \right]
twice the second from the first
\left[ \begin{array}{cc}<br />
1 & -7 \\<br />
2 & 5<br />
\end{array} \right]
and twice the first from the second
\left[ \begin{array}{cc}<br />
1 & -7 \\<br />
0 & 19<br />
\end{array} \right]
Don't be tempted to do something like "replace the second row with 3 times the first row minus twice the second row" -- that secretly involves scaling operations. The corresponding row matrix is
\left[ \begin{array}{cc}<br />
1 & 0 \\<br />
3 & -2<br />
\end{array} \right]
which is an invertible real matrix, but not an invertible integer matrix! To do that operation, you actually have to compensate by doing the row operations corresponding to
\left[ \begin{array}{cc}<br />
1 & -1 \\<br />
3 & -2<br />
\end{array} \right]
instead: this is invertible. (Its determinant is 1)
So anyways, here's an exercise: find all integer solutions to the system of equations
5x + 6y + 7z = 10
7x - 3y + 2z = 6
)
