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 F_1,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 c_1*, ..., c_r* span R(C).

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

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

(3) For suppose that

∑ (i=1,r) α_ic_i,* = [ 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, c_i,l(k) = 0 and if i = k, then c_i,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) α_ic_i,l(k) = α_k

[This is true since this is the sum of all the columns across rows at l(k). All c_i,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 c_i,* is linearly independent. [See Definition 1 here for definition of linearly independent]

(9) Since c_i,* 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 c_i,* and let m(i) be the column index of the leading coefficient of d_i,*

(9) We prove the first part by induction.

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

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

(b) First, consider:

d_1,* = ∑ (h=1,r) α_1,hc_h,* [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 c_h,j = 0 when j is less than l(1).

Now, since d_1,* = ∑ (h=1,r) α_1,hc_h,*

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

d_1,j = ∑ (h=1,r) α_1,hc_h,j = 0

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

l(1) ≤ m(1)

Similarly, we consider c_1* ∈ 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, c_h,l(i) = 1

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

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

d_k,l(i) = ∑ (h=1,r) α_k,hc_h,l(i) = α_k,i

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

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

Then j is less than l(h), and therefore, c_h,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), c_h,j = 0, it follows that using our equation in #9a above, we get:

d_k,j = ∑ (h=k,r) α_k,hc_h,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:

d_k,* = ∑ (h=1,r) α_k,hc_h,*.

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

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

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

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

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

But in this case, d_k,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:

d_k,* = c_k,* since d_k,* = ∑ (h=1,r) α_k,hc_h,*.

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, Matrices and Linear Algebra, 1989.