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

called “Gaussian elimination.” (You can read about it in those linear

algebra textbooks.)

Start Free Trial

No credit card required