O(mn) elementary row operations, each of which takes O(n) operations in

F , so a total of O(mn2 ) operations in F .

Example 15.3. Consider the execution of the Gaussian elimination algo-

rithm on input

«

[0] [1] [1]

3—3

A = [2] [1] [2] ∈ Z3 .

[2] [2] [0]

After copying A into B, the algorithm transforms B as follows:

« « «

[0] [1] [1] [2] [1] [2] [1] [2] [1]

B(1)”B(2) B(1)←[2]B(1)

[2] [1] [2] ’ ’ ’ ’ [0] [1] [1] ’ ’ ’ ’ ’ [0]

’ ’ ’’ ’’’’ [1] [1]

[2] [2] [0] [2] [2] [0] [2] [2] [0]

« «

[1] [2] [1] [1] [0] [2]

B(3)←B(3)’[2]B(1) B(1)←B(1)’[2]B(2)

’ ’ ’ ’ ’ ’ ’ [0] [1] [1] ’ ’ ’ ’ ’ ’ ’ [0] [1]

’’’’’’ ’’’’’’ [1]

[0] [1] [1] [0] [1] [1]

«

[1] [0] [2]

B(3)←B(3)’B(2)

’ ’ ’ ’ ’ ’ [0] [1] [1]

’ ’ ’ ’ ’’

[0] [0] [0]

2

Suppose the Gaussian elimination algorithm performs a total of t elemen-

tary row operations. Then as discussed above, the application of the eth

elementary row operation, for e = 1, . . . , t, amounts to multiplying the cur-

rent value of the matrix B on the left by a particular invertible m—m matrix

Me . Therefore, the ¬nal, output value of B satis¬es the equation

B = M A where M = Mt Mt’1 · · · M1 .

Since the product of invertible matrices is also invertible, we see that M

itself is invertible.

Although the algorithm as presented does not compute the matrix M , it

can be easily modi¬ed to do so. The resulting algorithm, which we call ex-

tended Gaussian elimination, is the same as plain Gaussian elimination,

except that we initialize the matrix M to be the m — m identity matrix, and

we add the following steps:

• Just before step 9, we add the step: swap rows M (r) and M ( ).

• Just before step 10, we add the step: M (r) ← B(r, j)’1 M (r).

• Just before step 13, we add the step: M (i) ← M (i) ’ B(i, j)M (r).

328 Matrices

At the end of the algorithm we output M in addition to B.

So we simply perform the same elementary row operations on M that we

perform on B. The reader may verify that the above algorithm is correct,

and that it uses O(mn(m + n)) operations in F .

Example 15.4. Continuing with Example 15.3, the execution of the ex-

tended Gaussian elimination algorithm initializes M to the identity matrix,

and then transforms M as follows:

« « «

[1] [0] [0] [0] [1] [0] [0] [2] [0]

M (1)”M (2) M (1)←[2]M (1)

[0] [1] [0] ’ ’ ’ ’ ’ [1] [0] [0] ’ ’ ’ ’ ’ [1] [0] [0]

’’’’ ’ ’ ’ ’’

[0] [0] [1] [0] [0] [1] [0] [0] [1]

« «

[0] [2] [0] [1] [2] [0]

M (3)←M (3)’[2]M (1) M (1)←M (1)’[2]M (2)

’ ’ ’ ’ ’ ’ ’ ’ [1] [0] [0] ’ ’ ’ ’ ’ ’ ’ ’ [1] [0] [0]

’’’’’’’ ’’’’’’’

[0] [2] [1] [0] [2] [1]

«

[1] [2] [0]

M (3)←M (3)’M (2)

’ ’ ’ ’ ’ ’ ’ [1] [0] [0]

’’’’’’

[2] [2] [1]

2

Exercise 15.6. For each type of elementary row operation, describe the

matrix M which corresponds to it, as well as M ’1 .

Exercise 15.7. Given a matrix B ∈ F m—n in reduced row echelon form,

show how to compute its pivot sequence using O(n) operations in F .

Exercise 15.8. In §4.4, we saw how to speed up matrix multiplication over

Z using the Chinese remainder theorem. In this exercise, you are to do

the same, but for performing Gaussian elimination over Zp , where p is a

large prime. Suppose you are given an m — m matrix A over Zp , where

len(p) = ˜(m). Straightforward application of Gaussian elimination would

require O(m3 ) operations in Zp , each of which takes time O(m2 ), leading to

a total running time of O(m5 ). Show how to use the techniques of §4.4 to

reduce the running time of Gaussian elimination to O(m4 ).

15.5 Applications of Gaussian elimination

Throughout this section, A is an arbitrary m — n matrix over a ¬eld F , and

M A = B, where M is an invertible m — m matrix, and B is in reduced

row echelon form with pivot sequence (p1 , . . . , pr ). This is precisely the in-

formation produced by the extended Gaussian elimination algorithm, given

15.5 Applications of Gaussian elimination 329

A as input (the pivot sequence can easily be “read” directly from B ” see

Exercise 15.7).

Let V := F 1—m , W := F 1—n , and ρ : V ’ W be the F -linear map that

sends v ∈ V to vA ∈ W .

Computing the image and kernel

Consider ¬rst the row space of A, that is, the vector space spanned by the

rows of A, or equivalently, the image of ρ.

We claim that the row space of A is the same as the row space of B. To

see this, note that for any v ∈ V , since B = M A, we have vB = v(M A) =

(vM )A, and so the row space of B is contained in the row space of A. For the

other containment, note that since M is invertible, we can write A = M ’1 B,

and apply the same argument.

Further, note that row space of B, and hence that of A, clearly has di-

mension r. Indeed, as stated in Theorem 15.5, the ¬rst r rows of B form a

basis for the row space of B.

Consider next the kernel of ρ, or what we might call the row null space

of A. We claim that the last m ’ r rows of M form a basis for ker(ρ).

Clearly, just from the fact that M A = B and the fact that the last m ’ r

rows of B are zero, it follows that the last m ’ r rows of M are contained

in ker(ρ). Furthermore, as M is invertible, its rows form a basis for V

(see Theorem 15.4), and so in particular, they are linearly independent. It

therefore su¬ces to show that the last m ’ r rows of M span the entire

kernel. Now, suppose there were a vector v ∈ ker(ρ) outside the subspace

spanned by the last m ’ r rows of M . As the rows of M span V , we may

write v = a1 M (1) + · · · + am M (m), where ai = 0 for some i = 1, . . . , r.

Setting v := (a1 , . . . , am ), we see that v = v M , and so

˜ ˜

ρ(v) = vA = (˜M )A = v (M A) = v B,

v ˜ ˜

and from the fact that the ¬rst r rows of B are linearly independent and

the last m ’ r rows of B are zero, we see that v B is not the zero vector

˜

(and because v has a non-zero entry in one its ¬rst r positions). We have

˜

derived a contradiction, and hence may conclude that the last m ’ r rows

of M span ker(ρ).

Finally, note that if m = n, then A is invertible if and only if its row space

has dimension m, which holds if and only if r = m, and in the latter case,

B will be the identity matrix, and hence M is the inverse of A.

Let us summarize the above discussion:

330 Matrices

• The ¬rst r rows of B form a basis for the row space of A (i.e., the

image of ρ).

• The last m ’ r rows of M form a basis for the row null space of A

(i.e., the kernel of ρ).

• If m = n, then A is invertible (i.e., ρ is an isomorphism) if and

only if r = m, in which case M is the inverse of A (i.e., the matrix

representing ρ’1 ).