# Gaussian Elimination of a Nonsquare Matrix

The Gaussian elimination of a nonsquare matrix is similar to the square case ex­cept that in the final result the upper-triangular matrix now becomes an echelon matrix:

Definition I.10: Anm x n matrix Uis an echelon matrix if, for i = 2,…, m, the first nonzero element of row i is farther to the right than the first nonzero element of the previous row i — 1.

For example, the matrix

 2 0 1 0 0 3 0 0 0

is an echelon matrix, and so is

 2 0 1 0 0 0 0 1 0 0 0 0
 U=

Theorem I.8 can now be generalized to

Theorem I.11: For each matrix A there exists a permutation matrix P, possibly equal to the unit matrix I, a lower-triangular matrix L with diagonal elements all equal to 1, and an echelon matrix U such that PA = LU. If A is a square matrix, then U is an upper-triangular matrix. Moreover, in that case PA = LDU, where now U is an upper-triangular matrix with diagonal elements all equal to 1 and D is a diagonal matrix.8

Again, I will only prove the general part of this theorem by examples. The parts for square matrices follow trivially from the general case.

First, let

(I.35)

Note that the diagonal elements of D are the diagonal elements of the former upper – triangular matrix U.

which is the matrix (I.22) augmented with an additional column. Then it follows from (I.31) that

P23 E3,1(1/2)E2,1(-1/2) A

where U is now an echelon matrix.

As another example, take the transpose of the matrix A in (I.35):

/2 1 -1

at_ 4 2 1

A = 2 3 -1

V1 1 ч

Then

P2,3 E4,2(-1/6) E4,3(1/4) E2,1(-2) E3,1(-1) E4,1(-1/2) At

 2 1 -1 0 2 0 0 0 3 0 0 0

where again U is an echelon matrix.