## Tuesday, June 26, 2007

### Properties of Elementary Matrices

In today's blog, I will show proofs for multiplication by the elementary matrices.

Today's content is taken from Matrices and Linear Transformations by Charles G. Cullen. For purposes of today's blog, I will use two notations:

Definition 1: Entu,v(A)

Entu,v(A) refers to the entry at row u and column v of the m x n matrix A (where m is the number of rows and n is the number of columns).

Definition 2: Rowr(A) Rowr(A) refers to the 1 x n matrix which equals row r of the matrix A (where n is the number of columns).

Here are the properties:

Lemma 1: I(Ri ↔ Rj)A = A(Ri ↔ Rj)

Proof:

(1) For row r ≠ i and r ≠ j, Rowr(I(Ri ↔ Rj)A = Rowr(A(Ri ↔ Rj)) since:

(a) Rowr(A(Ri ↔ Rj)) = Rowr(A) [Since the transformation only changes row i and row j]

(b) Rowr(I(Ri ↔ Rj)A ) = Rowr(A) since:

Entr,v = ∑ (w=1, n) Entr,w(I(Ri ↔ Rj))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Entr,w(I(Ri ↔ Rj)) = 1 only when w=r. In this case, Entw,v(A) = Entr,v(A).

In all other cases, Entr,w(I(Ri ↔ Rj)) = 0.

So, Entr,v(I(Ri ↔ Rj)A ) = 1*Entr,v(A) = Entr,v(A).

(2) For row r = i or r=j, RowrI(Ri ↔ Rj)A) = RowrA(Ri ↔ Rj)) since:

(a) Rowi(A(Ri ↔ Rj)) = Rowj(A)

(b) Rowi( I(Ri ↔ Rj)A) = Rowj(A) since:

Enti,v(I(Ri ↔ Rj)A) = ∑ (w=1, n) Enti,w(I(Ri ↔ Rj))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Enti,w(I(Ri ↔ Rj)) = 1 only when w=j and Enti,w(I(Ri ↔ Rj)) = 0 in all other cases.

When w=j, Entw,v(A) = Entj,v(A)

So, Enti,v(I(Ri ↔ Rj)A) = Entj,v(A).

(c) We can make the same argument for when r=j by swapping i,j.

(3) Since Rowr(I(Ri ↔ Rj)A = Rowr(A(Ri ↔ Rj)) is true for all rows, we have proven the lemma.

QED

Lemma 2: I(kRi)A = A(kRi)

Proof:

(1) For row r ≠ i, Rowr(I(kRi)A) = Rowr(A(kRi)) since:

(a) Rowr(A(kRi)) = Rowr(A)

(b) Row(I(kRi)A) = Rowr(A) since:

Entr,v(I(kRi)A) = ∑ (w=1,n) Entr,w(I(kRi))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Entr,w(I(kRi)) = 1 only when w=r. In all other cases, Entr,w(I(kRi)) = 0.

When w=r, Entw,v(A) = Entr,v(A).

So, Entr,v(I(kRi)A) = 1*Entr,v(A) = Entr,v(A).

(2) For row r = i, Rowr(I(kRi)A) = Rowr(A(kRi)) since:

(a) Rowi(A(kRi)) = k*Rowi(A)
(b) Rowi(I(kRi)A) = k*Rowi(A) since:

Enti,v(I(kRi)A) = ∑ (w=1,n) Enti,w(I(kRi))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Enti,k(I(kRi)) = k only when w=i. Otherwise, Enti,w(I(kRi)) = 0.

At w=i, Entw,v(A) = Enti,v(A).

So, we have:

Enti,v(I(kRi)A) = k*Enti,v(A)

(3) Since Rowr(I(kRi)A) = Rowr(A(kRi)) for all rows, we have proven the lemma.

QED

Lemma 3: I(kRi + Rj)A = A(kRi + Rj)

Proof:

(1) For row r ≠ j, Rowr(I(kRi + Rj)A) = Rowr(A(kRi + Rj)) since:

(a) Rowr(A(kRi + Rj)) = Rowr(A) [Since in this case, the row remains unchanged.]

(b) Rowr(I(kRi + Rj)A) = Rowr(A) since:

Entr,v(I(kRi + Rj)A) = ∑ (w=1,n) Entr,w(I(kRi + Rj))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Entr,w(I(kRi + Rj)) = 1 only when w=r . In all other cases, Entr,w(I(kRi + Rj)) = 0.

When w=r, Entw,v(A) = Entr,v(A).

So, we have:

Entr,v(I(kRi + Rj)A) = 1*Entr,v(A) = Entr,v(A).

(2) For row r = j, Rowr(I(kRi + Rj)A) = Rowr(A(kRi + Rj)) since:

(a) Rowj(A(kRi + Rj)) = k*Rowi(A) + Rowj(A).

(b) Rowj(I(kRi + Rj)A) = k*Rowi(A) + Rowj(A) since:

Entj,v(I(kRi + Rj)A) = ∑ (w=1,n) Entj,w(I(kRi + Rj))Entw,v(A)

[See Definition 1, here for review of Matrix Multiplication if needed]

Entj,w(I(kRi+Rj)) = k when w=i and Entj,w(I(kRi+Rj)) = 1 when w=j. Otherwise, Enti,w(I(kRi+ Rj)) = 0.

So, we have:

Entj,v(I(kRi + Rj)A) = k*Enti,v(A) + Entj,v(A)

(3) Since Rowr(I(kRi + Rj)A) = Rowr(A(kRi + Rj)) for all rows, we have proven the lemma.

QED

The following lemma refers to the transpose of a matrix. If you are not familiar with AT, then review here for details on the transpose of a matrix.

Lemma 4: The following elementary matrices are equivalent:

I(Ci ↔ Cj) = I(Ri ↔ Rj) = [ I(Ri ↔ Rj) ]T

I
(kCi) = I(kRi) = [I(kRi) ]T

I(kCi + Cj) = I(kRj + Ri) = [ I(kRi + Rj) ]T

Proof:

(1) Now, I(Ci ↔ Cj) = I(Ri ↔ Rj) since:

(a) For any row where r ≠ i and r ≠ j:

Only Entr,r(I(Ci ↔ Cj)) = 1

[since Entr,c(I(Ci ↔ Cj)) = 1 only when c=r. Otherwise, Entr,c(I(Ci ↔ Cj)) = 0.]

(b) For any row where r = i or r = j:

Only Enti,j(I(Ci ↔ Cj))=1 and Entj,i(I(Ci ↔ Cj)) = 1

[since in this case, Entr,c(I(Ci ↔ Cj)) = 1 only when c=i and r=j or when c=j and r=i. Otherwise, Entr,c(I(Ci ↔ Cj)) = 0.]

(2) Now, I(kCi) = I(kRi) since:

(a) For any row where r ≠ i:

Only Entr,r(I(kCi)) = 1

[since Entr,c(I(kCi)) = 1 only when c=r. Otherwise, Entr,c(I(kCi)) = 0.]

(b) For any row where r = i:

Only Enti,i(I(kCi)) = k while all other Enti,c(I(kCi))=0.

[since in this case, Entr,c(I(kCi)) = 0 whenever c ≠ r. Only when c=r do we have: Entr,c(I(kCi)) = k*1.]

(3) Now, I(kCi + Cj) = I(kRj + Ri) since:

(a) For any row where r ≠ j:

Only Entr,r( I(kCi + Cj) ) = 1

[since Entr,c( I(kCi + Cj) ) = 1 only when c=r. Otherwise, Entr,c( I(kCi + Cj) ) = 0.]

(b) For any row where r = i:

Enti,i( I(kCi + Cj) ) = 1, Enti,j( I(kCi + Cj) )=k, and for all other columns c, Entj,c( I(kCi + Cj) )=0.

[since in this case, Entr,c( I(kCi + Cj) ) = 0 whenever c ≠ i and c ≠ j. When c=j, Entj,j( I(kCi + Cj) ) = 1. When r=i, Enti,j( I(kCi + Cj) ) = k*Enti,i( I(kCi + Cj) ) + Enti,j( I(kCi + Cj) ) = k*1 + 0=k.]

(4) Based on the definition of the transpose of the matrix (see here), it is clear that:

[ I(Ri ↔ Rj) ]T = I(Ci ↔ Cj)

[I(kRi) ]T = I(kCi)

[ I(kRi + Rj) ]T = I(kCi + Cj)

QED

Corollary 4.1: A(Ci ↔ Cj) = AI(Ci ↔ Cj)

Proof:

(1) A(Ci ↔ Cj) = [AT(Ri ↔ Rj) ]T [See Definition 2 here for definition of the transpose of a matrix]

(2) [ AT(Ri ↔ Rj) ]T = [ I(Ri ↔ Rj)AT]T [See Lemma 3 above]

(3) [ I(Ri ↔ Rj)AT]T= (AT)T [I(Ri ↔ Rj)]T [See Lemma 3, here]

(4) (AT)T = A [See Lemma 1, here]

(5) (I(Ri ↔ Rj))T = I(Ci ↔ Cj) [See Lemma 4 above]

(6) So:

(AT)T(I(Ri ↔ Rj))T = AI(Ci ↔ Cj)

QED

Corollary 4.2: A(kCi) = AI(kCi)

Proof:

(1) A(kCi) = ([ AT(kRi) ])T [See Definition 2 here for definition of the transpose of a matrix]

(2) ([ AT(kRi) ])T = [ I(kRi)AT]T [See Lemma 3 above]

(3) [ I(kRi)AT]T = (AT)T(I(kRi))T [See Lemma 3, here]

(4) (AT)T = A [See Lemma 1, here]

(5) (I(kRi))T = I(kCi) [See Lemma 4 above]

(6) So:

(AT)T(I(kRi))T = AI(kCi)

QED

Corollary 4.3: A(kCi + Cj) = AI(kCi + Cj)

Proof:

(1) A(kCi + Cj) = [ AT(kRi + Rj) ]T [See Definition 2 here for definition of the transpose of a matrix]

(2) [ AT(kRi + Rj) ]T = [ I(kRi + Rj)AT]T [See Lemma 3 above]

(3) [ I(kRi + Rj)AT]T = (AT)T(I(kRi + Rj))T [See Lemma 3, here]

(4) (AT)T = A [See Lemma 1, here]

(5) (I(kRi + Rj))T = I(kCi + Cj) [See Lemma 4 above]

(6) So:

(AT)T(I(kRi + Rj))T = AI(kCi + Cj)

QED

Lemma 5: I(Ri ↔ Rj)-1 = I(Ri ↔ Rj)

Proof:

(1) Entu,v(( I(Ri ↔ Rj) )( I(Ri ↔ Rj) )) = ∑ (w=1,n) Entu,w( I(Ri ↔ Rj) )Entw,v( I(Ri ↔ Rj) )

[See Definition 1, here for review of Matrix Multiplication if needed]

(2) If u=v, then Entu,v(( I(Ri ↔ Rj) )Entv,w(( I(Ri ↔ Rj) )= 1 since:

Case I: u=v but u ≠ i and u ≠ j

In this case, Entu,w( I(Ri ↔ Rj) ) = 1 only when u=v=w. Otherwise, Entu,w( I(Ri ↔ Rj) ) = 0.

When u=v=w, Entw,v(( I(Ri ↔ Rj) )= 1 so we have:

Entu,v( I(Ri ↔ Rj) I(Ri ↔ Rj) ) = 1*1 = 1

Case II: u=v with u = i (we can also make the same argument for u=j)

In this case, Entu,w( I(Ri ↔ Rj) ) = 1 only when w=j. Otherwise, Entu,w( I(Ri ↔ Rj) ) = 0.

When u=v and w=j, Entw,v(( I(Ri ↔ Rj) )= 1 so we have:

So, Entu,v( I(Ri ↔ Rj) I(Ri ↔ Rj) ) = 1*1 = 1

(3) If u ≠ v, then Entu,v(( I(Ri ↔ Rj) )( I(Ri ↔ Rj) )) = 0 since:

Case I: u ≠ v and u ≠ i and u ≠ j

In this case, Entu,w(I(Ri ↔ Rj) ) = 1 only when w=u but since u ≠ v, at this point, Entw,v(I(Ri ↔ Rj) )=0 so in all cases:

Entu,v( I(Ri ↔ Rj) I(Ri ↔ Rj) ) = 0

Case II: u ≠ v with u = i (we can also make the same argument for u=j)

In this case, Entu,w(I(Ri ↔ Rj) ) = 1 only when w=j but since u ≠ v, at this point, v ≠ j and Entw,v(I(Ri ↔ Rj) )=0.

So, in all cases:

Entu,v( I(Ri ↔ Rj) I(Ri ↔ Rj) ) = 0

QED

Lemma 6: If k ≠ 0, then (I(kRi))-1 = I([1/k]Ri)

Proof:

(1) To prove this, we need to show that:

I(kRi)I([1/k]Ri) = I

and

I([1/k]Ri)I(kRi) = I

(2) Entu,v(I(kRi)I([1/k]Ri)) = ∑ (w=1,n) Entu,w(I(kRi))Entw,v(I([1/k]Ri))

[See Definition 1, here for review of Matrix Multiplication if needed]

(3) If u = v, then Entu,v(I(kRi)I([1/k]Ri)) = 1 since:

Case I: u=v and u ≠ i

In this case, Entu,w(I(kRi)) = 1 only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

When w=u, Entw,v(I([1/k]Ri)) = 1 since u=v.

So we have:

Entu,v(I(kRi)I([1/k]Ri)) = 1*1 = 1

Case II: u=v and u = i

In this case, Entu,w(I(kRi)) = k only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

When w=u, Entw,v(I([1/k]Ri)) = (1/k) since u=v=i.

So we have:

Entu,v(I(kRi)I([1/k]Ri)) = k*(1/k) = 1

(4) If u ≠ v, then Entu,v(I(kRi)I([1/k]Ri)) = 0 since:

Case I: u ≠ v and u ≠ i

In this case, Entu,w(I(kRi)) = 1 only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

But, when w=u, Entw,v(I([1/k]Ri)) = 0 since u ≠ v.

So we have:

Entu,v(I(kRi)I([1/k]Ri)) = 0

Case II: u ≠ v and u = i

In this case, Entu,w(I(kRi)) = k only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

When w=u, Entw,v(I([1/k]Ri)) = 0 since u ≠ v

So we have:

Entu,v(I(kRi)I([1/k]Ri)) = 0

(5) Thus, we have shown that I(kRi)I([1/k]Ri) = I

(6) Entu,v(I([1/k]Ri)I(kRi)) = ∑ (w=1,n) Entu,w(I([1/k]Ri))Entw,v(I(kRi))

[See Definition 1, here for review of Matrix Multiplication if needed]

(7) If u = v, then Entu,v(I([1/k]Ri)I(kRi)) = 1 since:

Case I: u=v and u ≠ i

In this case, Entu,w(I([1/k]Ri)) = 1 only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

When w=u, Entw,v(I(kRi)) = 1 since u=v.

So we have:

Entu,v(I([1/k]Ri)I(kRi)) = 1*1 = 1

Case II: u=v and u = i

In this case, Entu,w(I([1/k]Ri)) = (1/k) only when w = u and Entu,w(I(kRi)) = 0 in all other cases.

When w=u, Entw,v(I(kRi)) = k since u=v=i.

So we have:

Entu,v(I([1/k]Ri)I(kRi)) = (1/k)*k = 1

(8) If u ≠ v, then Entu,v(I([1/k]Ri)I(kRi)) = 0 since:

Case I: u ≠ v and u ≠ i

In this case, Entu,w(I([1/k]Ri)) = 1 only when w = u and Entu,w(I([1/k]Ri)) = 0 in all other cases.

But, when w=u, Entw,v(I(kRi)) = 0 since u ≠ v.

So we have:

Entu,v(I([1/k]Ri)I(kRi)) = 0

Case II: u ≠ v and u = i

In this case, Entu,w(I([1/k]Ri)) = 1/k only when w = u and Entu,w(I([1/k]Ri)) = 0 in all other cases.

When w=u, Entw,v(I(kRi)) = 0 since u ≠ v

So we have:

Entu,v(I([1/k]Ri)I(kRi)) = 0

(9) Thus, we have shown that I([1/k]Ri)I(kRi) = I

QED

Lemma 7: (I(kRi + Rj))-1 = I(-kRi + Rj)

Proof:

(1) To prove this, we need to show that:

I(kRi+Rj)I([-k]Ri + Rj) = I

and

I([-k]Ri + Rj)I(kRi + Rj) = I

(2) Entu,v(I(kRi+Rj)I(-kRi+Rj)) = ∑ (w=1,n) Entu,w(I(kRi+Rj))Entw,v(I(-kRi+Rj))

[See Definition 1, here for review of Matrix Multiplication if needed]

(3) If u = v, then Entu,v(I(kRi+Rj)I(-kRi+Rj)) = 1 since:

Case I: u=v and u ≠ j

In this case, Entu,w(I(kRi+Rj)) = 1 only when w = u and Entu,w(I(kRi+Rj)) = 0 in all other cases.

When w=u, Entw,v(I(-kRi+Rj)) = 1 since u=v.

So we have:

Entu,v(I(kRi+Rj)I(-kRi+Rj)) = 1*1 = 1

Case II: u=v and u = j

In this case, Entu,w(I(kRi+Rj)) = k when w = i, Entu,w(I(kRi+Rj)) = 1 when w = j, and Entu,w(I(kRi+Rj)) = 0 in all other cases.

When w=j, Entw,v(I(-kRi+Rj)) = 1 since u=v=j. Otherwise, Entw,v(I(-kRi+Rj)) = Entw,j(I(-kRi+Rj)) = 0

So we have:

Entu,v(I(kRi+Rj)I(-kRi+Rj)) = k*0 + 1*1 = 1

(4) If u ≠ v, then Entu,v(I(kRi+Rj)I(-kRi+Rj)) = 0 since:

Case I: u ≠ v and u ≠ j

In this case, Entu,w(I(kRi+Rj)) = 1 only when w = u and Entu,w(I(kRi+Rj)) = 0 in all other cases.

But, when w=u, Entw,v(I(-kRi+Rj)) = 0 since u ≠ v.

So we have:

Entu,v(I(kRi+Rj)I(-kRi+Rj)) = 0

Case II: u ≠ v and u = j and v ≠ i

In this case, Entu,w(I(kRi+Rj)) = k when w = i, Entu,w(I(kRi+Rj)) = 1 when w=j, and Entu,w(I(kRi+Rj)) = 0 in all other cases.

When w=i, Entw,v(I(-kRi+Rj)) = 0 since v ≠ i. When w=j, Entw,v(I(-kRi+Rj)) = 0 since v ≠ j.

So we have:

Entu,v(I(kRi+Rj)I(-kRi+Rj)) = 0

Case III: u ≠ v and u =j and v=i

In this case, Entu,w(I(kRi+Rj)) = k when w = i, Entu,w(I(kRi+Rj)) = 1 when w=j, and Entu,w(I(kRi+Rj)) = 0 in all other cases.

When w=i, Entw,v(I(-kRi+Rj)) = 1 since v ≠ i. When w=j, Entw,v(I(-kRi+Rj)) = -k since v = i.

So we have:

Entu,v(I(kRi+Rj)I(-kRi+Rj)) = k*1 + 1*(-k) = 0

(5) Thus, we have shown that I(kRi+Rj)I(-kRi+Rj) = I

(6) Entu,v(I(-kRi+Rj)I(kRi+Rj)) = ∑ (w=1,n) Entu,w(I(-kRi+Rj))Entw,v(I(kRi+Rj))

[See Definition 1, here for review of Matrix Multiplication if needed]

(7) If u = v, then Entu,v(I(-kRi+Rj)I(kRi+Rj)) = 1 since:

Case I: u=v and u ≠ j

In this case, Entu,w(I(-kRi+Rj)) = 1 only when w = u and Entu,w(I(-kRi+Rj)) = 0 in all other cases.

When w=u, Entw,v(I(kRi+Rj)) = 1 since u=v.

So we have:

Entu,v(I(-kRi+Rj)I(kRi+Rj)) = 1*1 = 1

Case II: u=v and u = j

In this case, Entu,w(I(-kRi+Rj)) = -k when w = i, Entu,w(I(-kRi+Rj)) = 1 when w = j, and Entu,w(I(-kRi+Rj)) = 0 in all other cases.

When w=j, Entw,v(I(kRi+Rj)) = 1 since u=v=j. Otherwise, Entw,v(I(kRi+Rj)) = Entw,j(I(kRi+Rj)) = 0

So we have:

Entu,v(I(-kRi+Rj)I(kRi+Rj)) = (-k)*0 + 1*1 = 1

(8) If u ≠ v, then Entu,v(I(-kRi+Rj)I(kRi+Rj)) = 0 since:

Case I: u ≠ v and u ≠ j

In this case, Entu,w(I(-kRi+Rj)) = 1 only when w = u and Entu,w(I(-kRi+Rj)) = 0 in all other cases.

But, when w=u, Entw,v(I(kRi+Rj)) = 0 since u ≠ v.

So we have:

Entu,v(I(-kRi+Rj)I(kRi+Rj)) = 0

Case II: u ≠ v and u = j and v ≠ i

In this case, Entu,w(I(-kRi+Rj)) = -k when w = i, Entu,w(I(-kRi+Rj)) = 1 when w=j, and Entu,w(I(-kRi+Rj)) = 0 in all other cases.

When w=i, Entw,v(I(kRi+Rj)) = 0 since v ≠ i. When w=j, Entw,v(I(kRi+Rj)) = 0 since v ≠ j.

So we have:

Entu,v(I(-kRi+Rj)I(kRi+Rj)) = 0

Case III: u ≠ v and u =j and v=i

In this case, Entu,w(I(-kRi+Rj)) = -k when w = i, Entu,w(I(-kRi+Rj)) = 1 when w=j, and Entu,w(I(-kRi+Rj)) = 0 in all other cases.

When w=i, Entw,v(I(kRi+Rj)) = 1 since v ≠ i. When w=j, Entw,v(I(kRi+Rj)) = k since v = i.

So we have:

Entu,v(I(-kRi+Rj)I(kRi+Rj)) = (-k)*1 + 1*k = 0

(9) Thus, we have shown that I(-kRi+Rj)I(kRi+Rj) = I

QED

Lemma 8: All Elementary Matrices are invertible

(i) I(Ri ↔ Rj)-1 = I(Ri ↔ Rj)

(ii) If k ≠ 0, then (I(kRi))-1 = I((1/k)Ri)

(iii)
(I(kRi + Rj))-1 = I(-kRi + Rj)

Proof:

This follows from Lemma 5, Lemma 6, and Lemma 7 above.

QED

Theorem 9: det(A) = det(AT)

Proof:

(1) There exists E1*...*En = A where all Ei are elementary matrices. [See Theorem 6, here]

(2) Now, I will show that det(E1*...*En) = det([E1*...*En]T)

(3) This is true if n=1 since:

From Lemma 4, we have:

I(Ci ↔ Cj) = I(Ri ↔ Rj) = [ I(Ri ↔ Rj) ]T

I(kCi) = I(kRi) = [I(kRi) ]T

I(kCi + Cj) = I(kRj + Ri) = [ I(kRi + Rj) ]T

det(I(kRj + Ri)) = det(I(kRi + Rj)) = 1 [See Lemma 7, here]

(4) Assume that the theorem is true up to n. To complete the proof, I will show that it is true for n+1.

(5) Let F = E1*...*En so that det(F) = det(FT)

(6) Now, I will show that det(FEi) = det[(FEi)T]

(7) (FEi)T = (Ei)TFT [See Lemma 3, here]

(8) det(EiT) = det(Ei) since 1 ≤ n.

(9) So,

det[(FE)T] = det[(Ei)TFT ]

det[(Ei)TFT ] = det((Ei)T)det(FT)

det((Ei)T)det(FT) = det(Ei)det(F)

det(Ei)det(F) = det(F)det(Ei)

det(F)det(Ei) = det(FEi) =

QED

References