Today, I will extend this result and show that if a matrix A is invertible (see Definition 1, here), then it is equal to product of elementary matrices.

The content in today's blog is taken from Matrices and Linear Algebra by Hans Schneider and George Phillip Barker.

Lemma 1: Only square matrices are invertible.

Proof:

(1) Let A be an n x m matix where n ≠ m.

(2) To be invertible, there must exist a matrix B such that AB = BA = I (see Definition 1, here)

(3) Let's assume that B is a p x q matrix.

(4) In order for A to multiply with B, then p = m and the result AB is an n x q matrix. (See here for review of matrix multiplication)

(5) In order for B to multiply with A, q must = n and BA is then a p x m matrix.

(6) Since p must = m and q must = n, AB is an n x n matrix and BA is an m x m matrix.

(7) But AB ≠ BA since m ≠ n so there is no such B that satisfies the conditions in step #2.

(8) So, we reject our assumption in step #1 and conclude that n = m and A is therefore a square matrix.

QED

From a previous result, we know that each m x n matrix has a unique reduced echelon form (see Corollary 3.1, here).

Definition 1: A

_{r}

I will denote the unique reduced echelon form of a given m x n matrix A as A

_{r}.

[For review of reduced echelon form, see Definition 2, here]

Definition 2: Rank

The rank r of an m x n matrix A is the number of nonzero rows in its reduced echelon form A

_{r}

Lemma 2: If A is invertible, then A

_{r}is invertible.

Proof:

(1) A

_{r}= E

_{1}E

_{2}...E

_{n}A where E

_{i}is an elementary matrix [See Theorem 5, here]

(2) Since each elementary matrix is invertible [see Lemma 4, here], we know that E

_{1}E

_{2}....E

_{n}is invertible. [See Lemma 3, here]

(3) So, we can multiply the inverse of E

_{1}*...*E

_{n}to both sides to get:

(E

_{1}*...*E

_{n})

^{-1}A = I*A

_{r}=A

_{r}

(4) But since (E

_{1}*...*E

_{n})

^{-1}

^{}is invertible and A is invertible, then A

_{r}must also be invertible [See Lemma 3, here].

QED

Lemma 3: If a matrix A is invertible, then its rank is equal to its number of rows.

Proof:

(1) Assume that A is invertible.

(2) Since A is invertible, we know that A

_{r}is invertible. [See Lemma 2 above]

(3) Let X = A

_{r}

^{-1}, B = A

_{r}

(4) From Lemma 1 above, we know that A,A

_{r}is an n x n matrix.

(5) Let e

_{*,n}= B*x

_{*,n}[NOTE: By e

_{*,n}, I mean the vector of values including e

_{1,n}... e

_{n,n}]

(6) Since BX = I

_{n}, we know that e

_{n,n}= 1 [See here for review of I

_{n}]

(7) But we also know that e

_{n,n}= ∑ (i=1,n) b

_{n,i}*x

_{i,n}[See here for review of matrix multiplication]

(8) So, therefore, it follows that the last row of A

_{r}is nonzero.

(9) Since A

_{r}is in reduced echelon form, it follows that all rows must be nonzero. [see Definition 2, here]

(10) Therefore, it follows that rank of A

_{r}is n. [See Definition 2 above]

QED

Corollary 3.1: If a matrix A is invertible and has n rows, then A is row equivalent to I

_{n}

Proof:

(1) Assume that A is invertible.

(2) Let n = the number of rows of A.

(3) By Lemma 3 above, its rank = n.

(4) Since its rank is n, we know that each row of A

_{r}is nonzero and therefore contains a leading coefficient.

(5) But since A,A

_{r}are square matricies (see Lemma 1 above), we know that they have n columns each since they have n rows each.

(6) Let l(i) = the column of leading nonzero element for A

_{r}.

(7) l(i) = i for each row i since 1 ≤ l(1) ≤ l(2) is less than l(3) is less than ... is less than l(n) ≤ n.

(8) Thus a

_{i,i}= 1 for i = 1 .. n

(9) Hence, every column of A

_{r}contains a leading coefficient, and all other entries of A are 0.

(10) It therefore follows that A

_{r}= I

_{n}(See here for review of I

_{n}, see Definition 2, here for review of reduced echelon form.)

QED

Lemma 4: If a matrix A is row equivalent to I

_{n}, then it is equal to a product of elementary matrices.

Proof:

(1) Assume that A is row equivalent to I

_{n}.

(2) Then there exists P such that A = PI

_{n}where P is a product of elementary matrices. [See Theorem 5, here]

(3) But I

_{n}= the elementary matrix = I

_{(1R1)}[See Defintion 1, here]

(4) So A is a product of elementary matrices.

QED

Theorem 5: A matrix M is invertible if and only if it is a product of elementary matrices

Proof:

(1) Assume that a matrix M is invertible.

(2) Let n = the number of rows of M.

(3) Using Corollary 3.1 above, it follows that M is row equivalent to I

_{n}.

(4) Using Lemma 4 above, this means that M is a product of elementary matrices.

(5) Assume that M is the product of elementary matrices so that A = E

_{1}*E

_{2}*...*E

_{n}

(6) Since each elementary matrix is invertible [see Lemma 4, here], it follows that their product is also invertible [see Lemma 3, here].

QED

References

- Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.

## No comments :

Post a Comment