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

Подпись: 2 4 2 A= 1 2 3 1 —1 1 —1 0 (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

Подпись: 1 0 0 '242 0.5 0 1 1 2 3 -0.5 1 0 v-1 1 -1 '2 4 2 1 0 3 0 1/2 = U, О О 2 1/2/ 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.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>