Suppose ρ is bijective, so that it is an R-module isomorphism. The inverse

map ρ’1 is also an R-module isomorphism. Let X be the matrix representing

ρ’1 with respect to the standard basis for R1—n , so that for w ∈ R1—n , we

have wX = ρ’1 (w). Since ρ —¦ ρ’1 = ρ’1 —¦ ρ = the identity map, it follows

that XA = AX = I. 2

We also have:

Theorem 15.4. Let A ∈ Rn—n . The following are equivalent:

(i) A is invertible;

(ii) the rows of A form a basis for R1—n ;

(iii) the columns of A form a basis for Rn—1 .

324 Matrices

Proof. The equivalence of (i) and (ii) follows from the previous theorem,

and the fact that the map ρ in that theorem is bijective if and only if the

rows of A form a basis for R1—n . The equivalence of (i) and (iii) follows by

considering the transpose of A. 2

Exercise 15.3. Let R be a ring, and let A be a square matrix over R. Let

us call X a left inverse of A if XA = I, and let us call Y a right inverse

of A if AY = I.

(a) Show that if A has both a left inverse X and a right inverse Y , then

X = Y and hence A is invertible.

(b) Assume that R is a ¬eld. Show that if A has either a left inverse or

a right inverse, then A is invertible.

Note that part (b) of the previous exercise holds for arbitrary rings, but

the proof of this is non-trivial, and requires the development of the theory

of determinants, which we do not cover in this text.

Exercise 15.4. Show that if A and B are two square matrices over a ¬eld

such that their product AB is invertible, then both A and B themselves

must be invertible.

Exercise 15.5. Show that if A is a square matrix over an arbitrary ring,

and Ak is invertible for some k > 0, then A is invertible.

15.4 Gaussian elimination

Throughout this section, F denotes a ¬eld.

A matrix B ∈ F m—n is said to be in reduced row echelon form if there

exists a sequence of integers (p1 , . . . , pr ), with 0 ¤ r ¤ m and 1 ¤ p1 < p2 <

· · · < pr ¤ n, such that the following holds:

• for i = 1, . . . , r, all of the entries in row i of B to the left of entry

(i, pi ) are zero (i.e., B(i, j) = 0 for j = 1, . . . , pi ’ 1);

• for i = 1, . . . , r, all of the entries in column pi of B above entry (i, pi )

are zero (i.e., B(i , pi ) = 0 for i = 1, . . . , i ’ 1);

• for i = 1, . . . , r, we have B(i, pi ) = 1;

• all entries in rows r + 1, . . . , m of B are zero (i.e., B(i, j) = 0 for

i = r + 1, . . . , m and j = 1, . . . , n).

It is easy to see that if B is in reduced row echelon form, the sequence

(p1 , . . . , pr ) above is uniquely determined, and we call it the pivot sequence

of B. Several further remarks are in order:

15.4 Gaussian elimination 325

• All of the entries of B are completely determined by the pivot se-

quence, except for the entries (i, j) with 1 ¤ i ¤ r and j > i with

j ∈ {pi+1 , . . . , pr }, which may be arbitrary.

/

• If B is an n — n matrix in reduced row echelon form whose pivot

sequence is of length n, then B must be the n — n identity matrix.

• We allow for an empty pivot sequence (i.e., r = 0), which will be the

case precisely when B = 0m—n .

4 — 6 matrix B over the rational numbers is

Example 15.2. The following

in reduced row echelon form:

1 ’2 0 0 3

«

0

¬0 0 0 1 0 2·

B=¬ ·.

0 0 0 1 ’4

0

0 0 0 00 0

The pivot sequence of B is (2, 4, 5). Notice that the ¬rst three rows of B

are linearly independent, that columns 2, 4, and 5 are linearly independent,

and that all of other columns of B are linear combinations of columns 2, 4,

and 5. Indeed, if we truncate the pivot columns to their ¬rst three rows, we

get the 3 — 3 identity matrix. 2

Generalizing the previous example, if a matrix is in reduced row echelon

form, it is easy to deduce the following properties, which turn out to be

quite useful:

Theorem 15.5. If B is a matrix in reduced row echelon form with pivot

sequence (p1 , . . . , pr ), then

(i) rows 1, 2, . . . , r of B are linearly independent;

(ii) columns p1 , . . . , pr of B are linearly independent, and all other

columns of B can be expressed as linear combinations of columns

p1 , . . . , p r .

Proof. Exercise ”just look at the matrix! 2

Gaussian elimination is an algorithm that transforms an arbitrary m—n

matrix A into a m—n matrix B, where B is a matrix in reduced row echelon

form obtained from A by a sequence of elementary row operations.

There are three types of elementary row operations:

Type I: swap two rows,

Type II: multiply a row by a non-zero scalar,

Type III: add a scalar multiple of one row to a di¬erent row.

326 Matrices

The application of any speci¬c elementary row operation to an m — n

matrix C can be a¬ected by multiplying C on the left by a suitable m — m

matrix M . Indeed, the matrix M corresponding to a particular elementary

row operation is simply the matrix obtained by applying the same elemen-

tary row operation to the m — m identity matrix. It is easy to see that for

any elementary row operation, the corresponding matrix M is invertible.

We now describe the basic version of Gaussian elimination. The input is

an m — n matrix A.

B ← A, r ← 0

1.

for j ← 1 to n do

2.

← 0, i ← r

3.

while = 0 and i ¤ m do

4.

i←i+1

5.

if B(i, j) = 0 then ← i

6.

7. if = 0 then

r ←r+1

8.

9. swap rows B(r) and B( )

B(r) ← B(r, j)’1 B(r)

10.

for i ← 1 to m do

11.

12. if i = r then

B(i) ← B(i) ’ B(i, j)B(r)

13.

14. output B

The algorithm works as follows. First, it makes a copy B of A (this

is not necessary if the original matrix A is not needed afterwards). The

algorithm proceeds column by column, starting with the left-most column,

so that after processing column j, the ¬rst j columns of B are in reduced row

echelon form, and the current value of r represents the length of the pivot

sequence. To process column j, in steps 3“6 the algorithm ¬rst searches

for a non-zero element among B(r + 1, j), . . . , B(m, j); if none is found,

then the ¬rst j + 1 columns of B are already in reduced row echelon form.

Otherwise, one of these non-zero elements is selected as the pivot element

(the choice is arbitrary), which is then used in steps 8“13 to bring column j

into the required form. After incrementing r, the pivot element is brought

into position (r, j), using a Type I operation in step 9. Then the entry (r, j)

is set to 1, using a Type II operation in step 10. Finally, all the entries above

and below entry (r, j) are set to 0, using Type III operations in steps 11“13.

Note that because columns 1, . . . , j ’ 1 of B were already in reduced row

echelon form, none of these operations changes any values in these columns.

As for the complexity of the algorithm, it is easy to see that it performs

15.4 Gaussian elimination 327