## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required 132 CHAPTER 11
Therefore, there are also inﬁnitely many matrices of determinant
1 in GL(2, Z) whose top row is [ab].
6
Solving Matrix Equations
We now go back and look at solving systems of linear equations with
rational coefﬁcients. It is fun to view this problem from the point of
view of GL(n, Q). Suppose we have a system of n Z-equations with n
unknowns, and no exponent greater than 1: a “linear system. As we
explained at the end of chapter 10, we can write this system using
matrices. If we let X be the n-by-1 matrix of unknowns, we can ﬁnd
an n-by-n Q-matrix A and an n-by-1 Q-matrix B so that our system
is expressed by the single matrix equation
7
AX = B. (11.4)
Everything now depends on whether or not A is in GL(n, Q). If
it is, then A has a matrix inverse A
1
. If we multiply both sides of
(11.4) on the left by A
1
—be careful to multiply on the left, because
matrix multiplication is not commutative—we get
A
1
(AX) = A
1
B.
Matrix multiplication is associative, so this is equivalent to
(A
1
A)X = A
1
B.
And A
1
A = I and IX = X so this is equivalent to
X = A
1
B. (11.5)
Do you see what this says? First of all, there is a solution, and
equation (11.5) is telling us what it is: X = A
1
B. Also it is telling
us that the solution is unique. There is no choice. Equation (11.4) is
6
There is the Euclidean Algorithm, which gives you all the pairs of c’s and d’s to go with
a given pair (a, b). You can ﬁnd this in any number theory textbook, but we do not need
it for our purposes.
7
A and B are actually Z-matrices, but since Z is contained in Q, we may consider them
as Q-matrices. This allows us to look for fractional solutions.
GROUPS OF MATRICES 133
equivalent to equation (11.5), so if you want to solve equation (11.4)
you have to take X = A
1
B.
Remember that this was all predicated on the assumption that
A was invertible, that is, A in GL(n, Q). If A is not invertible, then
either (11.4) has no solution at all, or else it has inﬁnitely many
solutions.
EXAMPLE: We solve the simultaneous set of equations
2x + 3y + 4z = 12. (11.6)
x + 0y + 2z = 6. (11.7)
3x + 4y + 8z = 0. (11.8)
Go back to the exercise on page 127 involving the matrices
A and H.IfweletX be the matrix
x
y
z
and B be the matrix
12
6
0
then the system (11.6)–(11.8) can be written as one equation
AX = B.
In the exercise above, we proved that H = A
1
. So from
(11.5) we see that our system has a unique solution, namely
X = HB. If you perform the actual matrix multiplication HB,
you will ﬁnd that
X =
24
0
9
.
In other words, the unique solution is x = 24, y = 0, z =−9.
134 CHAPTER 11
By the way, it is just a coincidence that there are no
fractions in the solution, even though there are fractions
in H. This is because all the integers on the right-hand
side of our system are divisible by the denominators
in H. To convince yourself of this, try to solve the system
2x + 3y + 4z = 13.
x + 0y + 2z = 7.
3x + 4y + 8z = 1.
SOLUTION: x = 77/3, y =−1/3, z =−28/3.
The advantage of knowing H is that it is now easy to solve
any system such as (11.6)–(11.8), where the left-hand sides are
the same but the right-hand side B
might be different. You just
matrix-multiply HB
. The experts will tell you, however, that if
you just want to solve one system, not a whole bunch with the
same left-hand sides, then the fastest thing to do is use something