Math Refresher: 2007-06-24

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: Ent_u,v(A)

Ent_u,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: Row_r(A) Row_r(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_{(R_i ↔ R_j)}A = A_{(R_i ↔ R_j)}

Proof:

(1) For row r ≠ i and r ≠ j, Row_r(I_{(R_i ↔ R_j)}A = Row_r(A_{(R_i ↔ R_j)}) since:

(a) Row_r(A_{(R_i ↔ R_j)}) = Row_r(A) [Since the transformation only changes row i and row j]

(b) Row_r(I_{(R_i ↔ R_j)}A ) = Row_r(A) since:

Ent_r,v = ∑ (w=1, n) Ent_r,w(I_{(R_i ↔ R_j)})Ent_w,v(A)

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

Ent_r,w(I_{(R_i ↔ R_j)}) = 1 only when w=r. In this case, Ent_w,v(A) = Ent_r,v(A).

In all other cases, Ent_r,w(I_{(R_i ↔ R_j)}) = 0.

So, Ent_r,v(I_{(R_i ↔ R_j)}A ) = 1*Ent_r,v(A) = Ent_r,v(A).

(2) For row r = i or r=j, Row_rI_{(R_i ↔ R_j)}A) = Row_rA_{(R_i ↔ R_j)}) since:

(a) Row_i(A_{(R_i ↔ R_j)}) = Row_j(A)

(b) Row_i( I_{(R_i ↔ R_j)}A) = Row_j(A) since:

Ent_i,v(I_{(R_i ↔ R_j)}A) = ∑ (w=1, n) Ent_i,w(I_{(R_i ↔ R_j)})Ent_w,v(A)

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

Ent_i,w(I_{(R_i ↔ R_j)}) = 1 only when w=j and Ent_i,w(I_{(R_i ↔ R_j)}) = 0 in all other cases.

When w=j, Ent_w,v(A) = Ent_j,v(A)

So, Ent_i,v(I_{(R_i ↔ R_j)}A) = Ent_j,v(A).

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

(3) Since Row_r(I_{(R_i ↔ R_j)}A = Row_r(A_{(R_i ↔ R_j)}) is true for all rows, we have proven the lemma.

QED

Lemma 2: I_{(kR_i)}A = A_{(kR_i)}

Proof:

(1) For row r ≠ i, Row_r(I_{(kR_i)}A) = Row_r(A_{(kR_i)}) since:

(a) Row_r(A_{(kR_i)}) = Row_r(A)

(b) Row(I_{(kR_i)}A) = Row_r(A) since:

Ent_r,v(I_{(kR_i)}A) = ∑ (w=1,n) Ent_r,w(I_{(kR_i)})Ent_w,v(A)

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

Ent_r,w(I_{(kR_i)}) = 1 only when w=r. In all other cases, Ent_r,w(I_{(kR_i)}) = 0.

When w=r, Ent_w,v(A) = Ent_r,v(A).

So, Ent_r,v(I_{(kR_i)}A) = 1*Ent_r,v(A) = Ent_r,v(A).

(2) For row r = i, Row_r(I_{(kR_i)}A) = Row_r(A_{(kR_i)}) since:

(a) Row_i(A_{(kR_i)}) = k*Row_i(A)
(b) Row_i(I_{(kR_i)}A) = k*Row_i(A) since:

Ent_i,v(I_{(kR_i)}A) = ∑ (w=1,n) Ent_i,w(I_{(kR_i)})Ent_w,v(A)

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

Ent_i,k(I_{(kR_i)}) = k only when w=i. Otherwise, Ent_i,w(I_{(kR_i)}) = 0.

At w=i, Ent_w,v(A) = Ent_i,v(A).

So, we have:

Ent_i,v(I_{(kR_i)}A) = k*Ent_i,v(A)

(3) Since Row_r(I_{(kR_i)}A) = Row_r(A_{(kR_i)}) for all rows, we have proven the lemma.

QED

Lemma 3: I_{(kR_i + R_j)}A = A_{(kR_i + R_j)}

Proof:

(1) For row r ≠ j, Row_r(I_{(kR_i + R_j)}A) = Row_r(A_{(kR_i + R_j)}) since:

(a) Row_r(A_{(kR_i + R_j)}) = Row_r(A) [Since in this case, the row remains unchanged.]

(b) Row_r(I_{(kR_i + R_j)}A) = Row_r(A) since:

Ent_r,v(I_{(kR_i + R_j)}A) = ∑ (w=1,n) Ent_r,w(I_{(kR_i + R_j)})Ent_w,v(A)

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

Ent_r,w(I_{(kR_i + R_j)}) = 1 only when w=r . In all other cases, Ent_r,w(I_{(kR_i + R_j)}) = 0.

When w=r, Ent_w,v(A) = Ent_r,v(A).

So, we have:

Ent_r,v(I_{(kR_i + R_j)}A) = 1*Ent_r,v(A) = Ent_r,v(A).

(2) For row r = j, Row_r(I_{(kR_i + R_j)}A) = Row_r(A_{(kR_i + R_j)}) since:

(a) Row_j(A_{(kR_i + R_j)}) = k*Row_i(A) + Row_j(A).

(b) Row_j(I_{(kR_i + R_j)}A) = k*Row_i(A) + Row_j(A) since:

Ent_j,v(I_{(kR_i + R_j)}A) = ∑ (w=1,n) Ent_j,w(I_{(kR_i + R_j)})Ent_w,v(A)

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

Ent_j,w(I_{(kR_i+R_j)}) = k when w=i and Ent_j,w(I_{(kR_i+R_j)}) = 1 when w=j. Otherwise, Ent_i,w(I_{(kR_i+ R_j)}) = 0.

So, we have:

Ent_j,v(I_{(kR_i + R_j)}A) = k*Ent_i,v(A) + Ent_j,v(A)

(3) Since Row_r(I_{(kR_i + R_j)}A) = Row_r(A_{(kR_i + R_j)}) 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 A^T, then review here for details on the transpose of a matrix.

Lemma 4: The following elementary matrices are equivalent:

I_{(C_i ↔ C_j)} = I_{(R_i ↔ R_j)}= [ I_{(R_i ↔ R_j)}]^T

I_{(kC_i)} = I_{(kR_i)} = [I_{(kR_i)} ]^T

I_{(kC_i + C_j)} = I_{(kR_j + R_i)} = [ I_{(kR_i + R_j)}]^TProof:

(1) Now, I_{(C_i ↔ C_j)} = I_{(R_i ↔ R_j)} since:

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

Only Ent_r,r(I_{(C_i ↔ C_j)}) = 1

[since Ent_r,c(I_{(C_i ↔ C_j)}) = 1 only when c=r. Otherwise, Ent_r,c(I_{(C_i ↔ C_j)}) = 0.]

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

Only Ent_i,j(I_{(C_i ↔ C_j)})=1 and Ent_j,i(I_{(C_i ↔ C_j)}) = 1

[since in this case, Ent_r,c(I_{(C_i ↔ C_j)}) = 1 only when c=i and r=j or when c=j and r=i. Otherwise, Ent_r,c(I_{(C_i ↔ C_j)}) = 0.]

(2) Now, I_{(kC_i)} = I_{(kR_i)} since:

(a) For any row where r ≠ i:

Only Ent_r,r(I_{(kC_i)}) = 1

[since Ent_r,c(I_{(kC_i)}) = 1 only when c=r. Otherwise, Ent_r,c(I_{(kC_i)}) = 0.]

(b) For any row where r = i:

Only Ent_i,i(I_{(kC_i)}) = k while all other Ent_i,c(I_{(kC_i)})=0.

[since in this case, Ent_r,c(I_{(kC_i)}) = 0 whenever c ≠ r. Only when c=r do we have: Ent_r,c(I_{(kC_i)}) = k*1.]

(3) Now, I_{(kC_i + C_j)} = I_{(kR_j + R_i)} since:

(a) For any row where r ≠ j:

Only Ent_r,r( I_{(kC_i + C_j)} ) = 1

[since Ent_r,c( I_{(kC_i + C_j)} ) = 1 only when c=r. Otherwise, Ent_r,c( I_{(kC_i + C_j)} ) = 0.]

(b) For any row where r = i:

Ent_i,i( I_{(kC_i + C_j)} ) = 1, Ent_i,j( I_{(kC_i + C_j)} )=k, and for all other columns c, Ent_j,c( I_{(kC_i + C_j)} )=0.

[since in this case, Ent_r,c( I_{(kC_i + C_j)} ) = 0 whenever c ≠ i and c ≠ j. When c=j, Ent_j,j( I_{(kC_i + C_j)} ) = 1. When r=i, Ent_i,j( I_{(kC_i + C_j)} ) = k*Ent_i,i( I_{(kC_i + C_j)} ) + Ent_i,j( I_{(kC_i + C_j)} ) = k*1 + 0=k.]

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

[ I_{(R_i ↔ R_j)}]^T = I_{(C_i ↔ C_j)}
[I_{(kR_i)} ]^T = I_{(kC_i)}

[ I_{(kR_i + R_j)}]^T = I_{(kC_i + C_j)}

QED

Corollary 4.1: A_{(C_i ↔ C_j)} = AI_{(C_i ↔ C_j)}

Proof:

(1) A_{(C_i ↔ C_j)}= [A^T_{(R_i ↔ R_j)}]^T [See Definition 2 here for definition of the transpose of a matrix]

(2) [ A^T_{(R_i ↔ R_j)}]^T = [ I_{(R_i ↔ R_j)}A^T]^T [See Lemma 3 above]

(3) [ I_{(R_i ↔ R_j)}A^T]^T= (A^T)^T [I_{(R_i ↔ R_j)}]^T [See Lemma 3, here]

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

(5) (I_{(R_i ↔ R_j)})^T = I_{(C_i ↔ C_j)} [See Lemma 4 above]

(6) So:

(A^T)^T(I_{(R_i ↔ R_j)})^T = AI_{(C_i ↔ C_j)}

QED

Corollary 4.2: A_{(kC_i)} = AI_{(kC_i)}

Proof:

(1) A_{(kC_i)}= ([ A^T_{(kR_i)}])^T [See Definition 2 here for definition of the transpose of a matrix]

(2) ([ A^T_{(kR_i)}])^T = [ I_{(kR_i)}A^T]^T [See Lemma 3 above]

(3) [ I_{(kR_i)}A^T]^T = (A^T)^T(I_{(kR_i)})^T [See Lemma 3, here]

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

(5) (I_{(kR_i)})^T = I_{(kC_i)} [See Lemma 4 above]

(6) So:

(A^T)^T(I_{(kR_i)})^T = AI_{(kC_i)}

QED

Corollary 4.3: A_{(kC_i + C_j)}= AI_{(kC_i + C_j)}

Proof:

(1) A_{(kC_i + C_j)}= [ A^T_{(kR_i + R_j)}]^T [See Definition 2 here for definition of the transpose of a matrix]

(2) [ A^T_{(kR_i + R_j)}]^T = [ I_{(kR_i + R_j)}A^T]^T [See Lemma 3 above]

(3) [ I_{(kR_i + R_j)}A^T]^T = (A^T)^T(I_{(kR_i + R_j)})^T [See Lemma 3, here]

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

(5) (I_{(kR_i + R_j)})^T = I_{(kC_i + C_j)} [See Lemma 4 above]

(6) So:

(A^T)^T(I_{(kR_i + R_j)})^T = AI_{(kC_i + C_j)}

QED

Lemma 5: I_{(R_i ↔ R_j)}^-1 = I_{(R_i ↔ R_j)}

Proof:

(1) Ent_u,v(( I_{(R_i ↔ R_j)})( I_{(R_i ↔ R_j)})) = ∑ (w=1,n) Ent_u,w( I_{(R_i ↔ R_j)})Ent_w,v( I_{(R_i ↔ R_j)})

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

(2) If u=v, then Ent_u,v(( I_{(R_i ↔ R_j)})Ent_v,w(( I_{(R_i ↔ R_j)})= 1 since:

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

In this case, Ent_u,w( I_{(R_i ↔ R_j)}) = 1 only when u=v=w. Otherwise, Ent_u,w( I_{(R_i ↔ R_j)}) = 0.

When u=v=w, Ent_w,v(( I_{(R_i ↔ R_j)})= 1 so we have:

Ent_u,v( I_{(R_i ↔ R_j)} I_{(R_i ↔ R_j)}) = 1*1 = 1

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

In this case, Ent_u,w( I_{(R_i ↔ R_j)}) = 1 only when w=j. Otherwise, Ent_u,w( I_{(R_i ↔ R_j)}) = 0.

When u=v and w=j, Ent_w,v(( I_{(R_i ↔ R_j)})= 1 so we have:

So, Ent_u,v( I_{(R_i ↔ R_j)}I_{(R_i ↔ R_j)}) = 1*1 = 1

(3) If u ≠ v, then Ent_u,v(( I_{(R_i ↔ R_j)})( I_{(R_i ↔ R_j)})) = 0 since:

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

In this case, Ent_u,w(I_{(R_i ↔ R_j)}) = 1 only when w=u but since u ≠ v, at this point, Ent_w,v(I_{(R_i ↔ R_j)})=0 so in all cases:

Ent_u,v( I_{(R_i ↔ R_j)}I_{(R_i ↔ R_j)}) = 0

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

In this case, Ent_u,w(I_{(R_i ↔ R_j)}) = 1 only when w=j but since u ≠ v, at this point, v ≠ j and Ent_w,v(I_{(R_i ↔ R_j)})=0.

So, in all cases:

Ent_u,v( I_{(R_i ↔ R_j)}I_{(R_i ↔ R_j)}) = 0

QED

Lemma 6: If k ≠ 0, then (I_{(kR_i)})^-1 = I_{([1/k]R_i)}

Proof:

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

I_{(kR_i)}I_{([1/k]R_i)} = I

and

I_{([1/k]R_i)}I_{(kR_i)}= I

(2) Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = ∑ (w=1,n) Ent_u,w(I_{(kR_i)})Ent_w,v(I_{([1/k]R_i)})

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

(3) If u = v, then Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = 1 since:

Case I: u=v and u ≠ i

In this case, Ent_u,w(I_{(kR_i)}) = 1 only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{([1/k]R_i)}) = 1 since u=v.

So we have:

Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = 1*1 = 1

Case II: u=v and u = i

In this case, Ent_u,w(I_{(kR_i)}) = k only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{([1/k]R_i)}) = (1/k) since u=v=i.

So we have:

Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = k*(1/k) = 1

(4) If u ≠ v, then Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = 0 since:

Case I: u ≠ v and u ≠ i

In this case, Ent_u,w(I_{(kR_i)}) = 1 only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

But, when w=u, Ent_w,v(I_{([1/k]R_i)}) = 0 since u ≠ v.

So we have:

Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = 0

Case II: u ≠ v and u = i

In this case, Ent_u,w(I_{(kR_i)}) = k only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{([1/k]R_i)}) = 0 since u ≠ v

So we have:

Ent_u,v(I_{(kR_i)}I_{([1/k]R_i)}) = 0

(5) Thus, we have shown that I_{(kR_i)}I_{([1/k]R_i)} = I

(6) Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = ∑ (w=1,n) Ent_u,w(I_{([1/k]R_i)})Ent_w,v(I_{(kR_i)})

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

(7) If u = v, then Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = 1 since:

Case I: u=v and u ≠ i

In this case, Ent_u,w(I_{([1/k]R_i)}) = 1 only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{(kR_i)}) = 1 since u=v.

So we have:

Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = 1*1 = 1

Case II: u=v and u = i

In this case, Ent_u,w(I_{([1/k]R_i)}) = (1/k) only when w = u and Ent_u,w(I_{(kR_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{(kR_i)}) = k since u=v=i.

So we have:

Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = (1/k)*k = 1

(8) If u ≠ v, then Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = 0 since:

Case I: u ≠ v and u ≠ i

In this case, Ent_u,w(I_{([1/k]R_i)}) = 1 only when w = u and Ent_u,w(I_{([1/k]R_i)}) = 0 in all other cases.

But, when w=u, Ent_w,v(I_{(kR_i)}) = 0 since u ≠ v.

So we have:

Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = 0

Case II: u ≠ v and u = i

In this case, Ent_u,w(I_{([1/k]R_i)}) = 1/k only when w = u and Ent_u,w(I_{([1/k]R_i)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{(kR_i)}) = 0 since u ≠ v

So we have:

Ent_u,v(I_{([1/k]R_i)}I_{(kR_i)}) = 0

(9) Thus, we have shown that I_{([1/k]R_i)}I_{(kR_i)} = I

QED

Lemma 7: (I_{(kR_i + R_j)})^-1 = I_{(-kR_i + R_j)}

Proof:

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

I_{(kR_i+R_j)}I_{([-k]R_i + R_j)} = I

and

I_{([-k]R_i + R_j)}I_{(kR_i + R_j)}= I

(2) Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = ∑ (w=1,n) Ent_u,w(I_{(kR_i+R_j)})Ent_w,v(I_{(-kR_i+R_j)})

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

(3) If u = v, then Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = 1 since:

Case I: u=v and u ≠ j

In this case, Ent_u,w(I_{(kR_i+R_j)}) = 1 only when w = u and Ent_u,w(I_{(kR_i+R_j)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{(-kR_i+R_j)}) = 1 since u=v.

So we have:

Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = 1*1 = 1

Case II: u=v and u = j

In this case, Ent_u,w(I_{(kR_i+R_j)}) = k when w = i, Ent_u,w(I_{(kR_i+R_j)}) = 1 when w = j, and Ent_u,w(I_{(kR_i+R_j)}) = 0 in all other cases.

When w=j, Ent_w,v(I_{(-kR_i+R_j)}) = 1 since u=v=j. Otherwise, Ent_w,v(I_{(-kR_i+R_j)}) = Ent_w,j(I_{(-kR_i+R_j)}) = 0

So we have:

Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = k*0 + 1*1 = 1

(4) If u ≠ v, then Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = 0 since:

Case I: u ≠ v and u ≠ j

In this case, Ent_u,w(I_{(kR_i+R_j)}) = 1 only when w = u and Ent_u,w(I_{(kR_i+R_j)}) = 0 in all other cases.

But, when w=u, Ent_w,v(I_{(-kR_i+R_j)}) = 0 since u ≠ v.

So we have:

Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = 0

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

In this case, Ent_u,w(I_{(kR_i+R_j)}) = k when w = i, Ent_u,w(I_{(kR_i+R_j)}) = 1 when w=j, and Ent_u,w(I_{(kR_i+R_j)}) = 0 in all other cases.

When w=i, Ent_w,v(I_{(-kR_i+R_j)}) = 0 since v ≠ i. When w=j, Ent_w,v(I_{(-kR_i+R_j)}) = 0 since v ≠ j.

So we have:

Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = 0

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

In this case, Ent_u,w(I_{(kR_i+R_j)}) = k when w = i, Ent_u,w(I_{(kR_i+R_j)}) = 1 when w=j, and Ent_u,w(I_{(kR_i+R_j)}) = 0 in all other cases.

When w=i, Ent_w,v(I_{(-kR_i+R_j)}) = 1 since v ≠ i. When w=j, Ent_w,v(I_{(-kR_i+R_j)}) = -k since v = i.

So we have:

Ent_u,v(I_{(kR_i+R_j)}I_{(-kR_i+R_j)}) = k*1 + 1*(-k) = 0

(5) Thus, we have shown that I_{(kR_i+R_j)}I_{(-kR_i+R_j)} = I

(6) Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = ∑ (w=1,n) Ent_u,w(I_{(-kR_i+R_j)})Ent_w,v(I_{(kR_i+R_j)})

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

(7) If u = v, then Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = 1 since:

Case I: u=v and u ≠ j

In this case, Ent_u,w(I_{(-kR_i+R_j)}) = 1 only when w = u and Ent_u,w(I_{(-kR_i+R_j)}) = 0 in all other cases.

When w=u, Ent_w,v(I_{(kR_i+R_j)}) = 1 since u=v.

So we have:

Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = 1*1 = 1

Case II: u=v and u = j

In this case, Ent_u,w(I_{(-kR_i+R_j)}) = -k when w = i, Ent_u,w(I_{(-kR_i+R_j)}) = 1 when w = j, and Ent_u,w(I_{(-kR_i+R_j)}) = 0 in all other cases.

When w=j, Ent_w,v(I_{(kR_i+R_j)}) = 1 since u=v=j. Otherwise, Ent_w,v(I_{(kR_i+R_j)}) = Ent_w,j(I_{(kR_i+R_j)}) = 0

So we have:

Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = (-k)*0 + 1*1 = 1

(8) If u ≠ v, then Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = 0 since:

Case I: u ≠ v and u ≠ j

In this case, Ent_u,w(I_{(-kR_i+R_j)}) = 1 only when w = u and Ent_u,w(I_{(-kR_i+R_j)}) = 0 in all other cases.

But, when w=u, Ent_w,v(I_{(kR_i+R_j)}) = 0 since u ≠ v.

So we have:

Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = 0

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

In this case, Ent_u,w(I_{(-kR_i+R_j)}) = -k when w = i, Ent_u,w(I_{(-kR_i+R_j)}) = 1 when w=j, and Ent_u,w(I_{(-kR_i+R_j)}) = 0 in all other cases.

When w=i, Ent_w,v(I_{(kR_i+R_j)}) = 0 since v ≠ i. When w=j, Ent_w,v(I_{(kR_i+R_j)}) = 0 since v ≠ j.

So we have:

Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = 0

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

In this case, Ent_u,w(I_{(-kR_i+R_j)}) = -k when w = i, Ent_u,w(I_{(-kR_i+R_j)}) = 1 when w=j, and Ent_u,w(I_{(-kR_i+R_j)}) = 0 in all other cases.

When w=i, Ent_w,v(I_{(kR_i+R_j)}) = 1 since v ≠ i. When w=j, Ent_w,v(I_{(kR_i+R_j)}) = k since v = i.

So we have:

Ent_u,v(I_{(-kR_i+R_j)}I_{(kR_i+R_j)}) = (-k)*1 + 1*k = 0

(9) Thus, we have shown that I_{(-kR_i+R_j)}I_{(kR_i+R_j)} = I

QED

Lemma 8: All Elementary Matrices are invertible

(i) I_{(R_i ↔ R_j)}^-1 = I_{(R_i ↔ R_j)}

(ii) If k ≠ 0, then (I_{(kR_i)})^-1 = I_{((1/k)R_i)

(iii)} (I_{(kR_i + R_j)})^-1 = I_{(-kR_i + R_j)}

Proof:

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

QED

Theorem 9: det(A) = det(A^T)

Proof:

(1) There exists E₁*...*E_n = A where all E_i are elementary matrices. [See Theorem 6, here]

(2) Now, I will show that det(E₁*...*E_n) = det([E₁*...*E_n]^T)

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

From Lemma 4, we have:

I_{(C_i ↔ C_j)} = I_{(R_i ↔ R_j)}= [ I_{(R_i ↔ R_j)}]^T

I_{(kC_i)} = I_{(kR_i)} = [I_{(kR_i)} ]^T

I_{(kC_i + C_j)} = I_{(kR_j + R_i)} = [ I_{(kR_i + R_j)}]^T

det(I_{(kR_j + R_i)}) = det(I_{(kR_i + R_j)}) = 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 = E₁*...*E_n so that det(F) = det(F^T)

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

(7) (FE_i)^T = (E_i)^TF^T [See Lemma 3, here]

(8) det(E_i^T) = det(E_i) since 1 ≤ n.

(9) So,

det[(FE)^T] = det[(E_i)^TF^T ]

det[(E_i)^TF^T ] = det((E_i)^T)det(F^T)

det((E_i)^T)det(F^T) = det(E_i)det(F)

det(E_i)det(F) = det(F)det(E_i)

det(F)det(E_i) = det(FE_i) =

QED

References

Charles G. Cullen, Matrices and Linear Transformations, Dover Publications, Inc., 1972.

Math Refresher

Tuesday, June 26, 2007

Properties of Elementary Matrices

Transpose of a matrix

About Me

Blog Archive