116 CHAPTER 4. ROW OPERATIONS

where B is obtained from A by replacing the jth row of A with itself added to c times theith row of A.

The next theorem is the main result.

Theorem 4.1.6 To perform any of the three row operations on a matrix A it suffices to dothe row operation on the identity matrix obtaining an elementary matrix E and then takethe product, EA. Furthermore, each elementary matrix is invertible and its inverse is anelementary matrix.

Proof: The first part of this theorem has been proved in Lemmas 4.1.3 - 4.1.5. Itonly remains to verify the claim about the inverses. Consider first the elementary matricescorresponding to row operation of type three.

E (−c× i+ j)E (c× i+ j) = I

This follows because the first matrix takes c times row i in the identity and adds it to row j.When multiplied on the left by E (−c× i+ j) it follows from the first part of this theoremthat you take the ith row of E (c× i+ j) which coincides with the ith row of I since thatrow was not changed, multiply it by −c and add to the jth row of E (c× i+ j) which wasthe jth row of I added to c times the ith row of I. Thus E (−c× i+ j) multiplied on theleft, undoes the row operation which resulted in E (c× i+ j). The same argument appliedto the product

E (c× i+ j)E (−c× i+ j)

replacing c with −c in the argument yields that this product is also equal to I. Therefore,E (c× i+ j)

−1= E (−c× i+ j) .

Similar reasoning shows that for E (c, i) the elementary matrix which comes from mul-tiplying the ith row by the nonzero constant, c,

E (c, i)−1

= E(c−1, i

).

Finally, consider P ij which involves switching the ith and the jth rows.

P ijP ij = I

because by the first part of this theorem, multiplying on the left by P ij switches the ith

and jth rows of P ij which was obtained from switching the ith and jth rows of the identity.First you switch them to get P ij and then you multiply on the left by P ij which switches

these rows again and restores the identity matrix. Thus(P ij)−1

= P ij . ■

4.2 The Rank of a Matrix

Recall the following definition of rank of a matrix.

Definition 4.2.1 A submatrix of a matrix A is the rectangular array of numbers obtainedby deleting some rows and columns of A. Let A be an m × n matrix. The determinantrank of the matrix equals r where r is the largest number such that some r × r submatrixof A has a non zero determinant. The row rank is defined to be the dimension of the spanof the rows. The column rank is defined to be the dimension of the span of the columns.The rank of A is denoted as rank (A).

The following theorem is proved in the section on the theory of the determinant and isrestated here for convenience.