## Thursday, May 03, 2007

### Row Space

Today's blog is taken straight from Matrices and Linear Algebra by Hans Schneider and George Philip Barker.

Definition 1: Row Space

A row space of an m x n matrix A is the subspace of F1,n spanned by the rows of A. I will denote this row space as R(A).

[For review: see Definition 3 here for definition of subspace; see Definition 3 here for definition of spanning a vector space; see Definition 2 here for definition of a vector space.]

Lemma 1: For any matrix P for which PA is defined:
(1) R(PA) ⊆ R(A)
(2) R(PA) = R(A) if P is invertible.

Proof:

(1) Let B = PA

(2) The rows of B are linear combinations of the rows of A. [See Lemma 2, here]

(3) Since the rows of B are linear combinations of the rows of A:

R(B) ⊆ R(A) [See Corollary 1.1, here]

(4) Using step #1 above gives us:

R(PA) ⊆ R(A)

(5) If P is invertible, then there exists a value P-1 such that P-1P = 1.

[Review: see Definition 1 here for definition of invertible.]

(6) So that:

P-1B = P-1PA = (P-1P)A = 1*A = A

(7) From this, the rows of A are linear combinations of the rows of B. [See Lemma 2, here]

(8) So that:

R(A) ⊆ R(B) [See Corollary 1.1, here]

(9) Using step #1 above gives us:

R(A) ⊆ R(PA)

(10) Thus, if P is invertible, then:

R(A) ⊆ R(PA) (step #4) and R(PA) ⊆ R(A) (step #9) which gives us R(PA)=R(A)

QED

Corollary 1.1: If B is row equivalent to A, then R(B) = R(A)

Proof:

(1) If B is row equivalent to A, then B = PA and P is invertible. [See Theorem 5, here]

(2) Using Lemma 1 above, we can then conclude that R(PA) = R(A)

(3) But since B=PA, this gives us that R(B) = R(A)

QED

Definition 2: Row rank

The row rank of a matrix A is the dimension of the row space, that is, dim R(A).

[Review: see Definition 2 here for definition of the dimension of a vector space which is abbreviated as dim V.]

Corollary 1.2:

For any matrix P for which PA is defined:
(1) Row rank PA ≤ row rank A
(2) If P is invertible, then row rank PA = row rank A

Proof:

(1) Using Lemma 1 above, we have:
R(PA) ⊆ R(A)

(2) Then Row rank PA ≤ row rank A [See Lemma 4, here]

(3) If P is invertible, then R(PA) = R(A)

(4) This then gives us that Row rank PA = row rank A.

QED

Lemma 2:

Let C be any matrix in reduced echelon form with r nonzero rows. Then the row rank of C is r.

Proof:

(1) row rank of C ≤ r since c1*, ..., cr* span R(C).

(2) We shall show that c1*, ..., cr* form a basis for R(C).

[Review: See Definition 2 here for definition of basis].

(3) For suppose that

∑ (i=1,r) αici,* = [ 0 0 ... 0 ]

(4) Since C is in reduced echelon form, we know that in the leading nonzero column for each row, all other rows are 0 at that same column.

[Review: See Definition 2 here for definition of reduced echelon form].

(5) If we let l(k) be the column index of the leading nonzero column for the row k, we can be sure that:

if i ≠ k, ci,l(k) = 0 and if i = k, then ci,l(k) = 1. [From the Definition of Reduced Echelon Form, see Definition 2, here]

(6) This means that for each row, the sum of values at that column give us:

For each k, 1 ≤ k ≤ r,

∑ (i=1,r) αici,l(k) = αk

[This is true since this is the sum of all the columns across rows at l(k). All ci,l(k) are 0 except for where i = k.]

(7) Hence each αk = 0 after combining the results of step #3 with step #6.

(8) But then if step #3 implies step #6, we can conclude that ci,* is linearly independent. [See Definition 1 here for definition of linearly independent]

(9) Since ci,* spans C and is linearly independent, it is clear that it is a basis for C. [See Definition 2 here for definition of basis] and its rank is r.

QED

Lemma 3: Uniqueness of Reduced Echelon Form

If R(A) = R(B) and there are C and D such that C is row equivalent to A and D is row equivalent to B where C and D are in reduced echelon form, then C=D.

Proof:

(1) Since C is row equivalent to A, there exists P such that C = PA and P is invertible [See Theorem 5, here]

(2) Likewise, since D is row equivalent to B, there exists Q such that D = QB and Q is invertible.

(3) Using Corollary 1.2 above, we can conclude:

row rank C = row rank A

row rank D = row rank B

(4) Since R(A) = R(B), then row rank A = row rank B. [see Definition 2 above; see Theorem 1 here for proof that equal vector spaces have equal dimension.]

(5) Using Lemma 2 above, we can also conclude that C and D have the same number of nonzero rows since:

(a) C and D have the same row rank since row rank C = row rank A = row rank B = row rank D.

(b) Using Lemma 2 above, we know that the row rank of a matrix in row echelon form is the number of nonzero rows.

(c) Therefore, it follows that since C,D are in row echelon form and since C,D have the same row rank, then C,D must have the same number of nonzero rows.

(6) Let r = the number of nonzero rows in C,D.

(7) Our proof will consist of two stages:
(i) Show that the leading coefficients of C and D occur in the same place.
(ii) Show that the remaining coefficients are equal.

(8) Let l(i) be the column index of the leading entry of ci,* and let m(i) be the column index of the leading coefficient of di,*

(9) We prove the first part by induction.

(a) Since R(C) = R(D), we have dk,* ∈ R(C) for all k, 1 ≤ k ≤ r, with:

dk,* = ∑ (h=1,r) (αk,h)ch,* [see Definition 1 above for R(D); see Definition 3 here for definition of spanning a vector space.]

(b) First, consider:

d1,* = ∑ (h=1,r) α1,hch,* [This follows from step (a) above]

If j is less than l(1), then j is less than l(h) for h = 1, 2, ..., r. [see Definition 2 here, property (3)]

Hence ch,j = 0 when j is less than l(1).

Now, since d1,* = ∑ (h=1,r) α1,hch,*

We know that for each d1,j, we have:

d1,j = ∑ (h=1,r) α1,hch,j = 0

So, we have: j is less than l(1) implies that d1,j is 0. It follows that:

l(1) ≤ m(1)

Similarly, we consider c1* ∈ R(D) and by reversing the roles of C and D we obtain m(1) ≤ l(1).

Since we have m(1) ≤ l(1) and l(1) ≤ m(1).

It follows that:

m(1) = l(1).

(b) We next turn to the induction step.

Now assume that 1 is less than k ≤ r and assume that we have already proved that l(i) = m(i) for 1 ≤ i less than k.

For each leading nonzero, only one row has a nonzero value while the other rows have a zero value. In other words, in all columns associated with l(i), the value is either 1 if i=l(i) and 0 if i ≠ l(i).

This gives us:

if h = i, ch,l(i) = 1

if h ≠ i, ch,l(i) = 0 [See Definition 2 here]

Using the step in #9a, we can conclude:

dk,l(i) = ∑ (h=1,r) αk,hch,l(i) = αk,i

[Since in all but one case, ch,l(i) = 0 and in that one case ch,l(i)=1.]

Assume that h ≥ k and j is less than l(k)

Then j is less than l(h), and therefore, ch,j = 0 since all values preceding the first nonzero value in a row must be 0.

But then, if all for all j is less than l(k), ch,j = 0, it follows that using our equation in #9a above, we get:

dk,j = ∑ (h=k,r) αk,hch,j = 0

for all j is less than l(k).

Finally, if no nonzero value can be less than l(k), then it follows that the first nonzero value at row k, m(k), must be greater or equal to l(k). In other words:

l(k) ≤ m(k)

But all the arguments we have made with respect to D and C can be reversed since R(D)=R(C). We can then make the same arguments substituting D for C to prove that m(k) ≤ l(k).

Hence, l(k) = m(k) and the induction step is proved.

(c) It follows from (a) and (b) by induction that l(i) = m(i) for all i where 1 ≤ i ≤ r.

(10) We now turn to the second part of the proof that C = D.

(11) Suppose again that 1 ≤ k ≤ r, and that:

dk,* = ∑ (h=1,r) αk,hch,*.

As before, dk,l(i) = αk,i. [See #9b above]

But since m(i) = l(i), we now obtain dk,m(i) = αk,i. [This follows directly from dk,l(i) = αk,i]

Since dk,m(i) = αk,i, it follows that αk,k = dk,m(k)

Since dk,m(k) = 1, it follows that αk,k = 1.

Now, if i ≠ k, then it follows that αk,i = dk,m(i).

But in this case, dk,m(i) = 0 since all other values in this column = 0.

Thus, since we have shown that:

i = k → αk,i=1 and i ≠ k → αk,i=0, it follows that:

dk,* = ck,* since dk,* = ∑ (h=1,r) αk,hch,*.

It therefore follows that C = D.

QED

Corollary 3.1:

Let A be any matrix. Then there is just one matrix in reduced echelon form that is row equivalent to A.

Proof:

(1) We know that every matrix A can be reduced to a reduced echelon form C. [See Theorem 1, here]

(2) Suppose that D is also a reduced echelon form that is row equivalent to A.

(3) Let B = A.

(4) Then using Lemma 3 above, we obtain that C = D.

QED

References
• Hans Schneider, George Philip Barker, , 1989.