APP. A] VECTORS AND MATRICES 419
Gaussian Elimination in Matrix Form
Consider any matrixA. Two algorithms, Algorithms A-1 and A-2, are given in Fig. A-5 and Fig. A-6,
respectively. The first algorithm transforms the matrixAinto an echelon form (using only elementary row
operations), and the second algorithm transforms the echelon matrix into a matrix in row canonical form. (The
two algorithms together are calledGaussian elimination.)
At the end of the Algorithm A-1, thepivot(leading nonzero) entries will bea 1 j 1 ,a 2 j 2 , ..., arjrwhererdenotes the number of nonzero rows in the matrix in echelon form.
Remark 1: The numberm=−
aij 1
a 1 j 1=−coefficient to be deleted
pivotis called themultiplier.Remark 2: One could replace the operation in Step 1 (b)by
“Add−aij 1 R 1 toa 1 j 1 Ri”This would avoid fractions if all the scalars were originally integers.EXAMPLE A.10 Find the row canonical form ofA=
⎡
⎣12 −31 2
24 − 4610
36 − 6913⎤
⎦.First reduceAto echelon form using Algorithm A-1. Specifically, usea 11 =1 as a pivot to obtains zeros
belowa 11 , that is, apply the row operations “Add− 2 R 1 toR 2 ” and “Add− 3 R 1 toR 3 .” Then usea 23 =2asa
pivot to obtain 0 belowa 23 , that is, apply the row operation “Add−^32 R 2 toR 3 .” This yields
A∼⎡
⎣12 − 312
00 246
00 367⎤
⎦∼⎡
⎣12 −31 2
00 24 6
00 00− 2⎤
⎦The matrixAis now in echelon form.
Now use Algorithm A-2 to further reduceAto row canonical form. Specifically, multiplyR 3 by− 1 /2sothe
pivot entrya 35 =1, and then usea 35 =1 as a pivot to obtain zeros above it by the operations “Add− 6 R 3 to
R 2 ” and “Add− 2 R 3 toR 1 .” This yields:
A∼⎡
⎣12 − 312
00 246
00 001⎤
⎦∼⎡
⎣12 − 310
00 240
00 001⎤
⎦MultiplyR 2 by^12 so the pivot entrya 23 =1, and then usea 23 =1 as a pivot to obtain 0 above it by the operation
“Add 3R 1 toR 1 ”. This yields:
A∼⎡
⎣12 − 310
00 120
00 001⎤
⎦∼⎡
⎣12070
00120
00001⎤
⎦The last matrix is the row canonical form ofA.