MA1522: Linear Algebra for Computing

Chapter 4: Subspaces Associated to a Matrix

4.1 Column Space, Row Space, and Nullspace
Column and Row Space
Definition
Let A be an m × n matrix,  
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A= . ..  .
 
.. ..
 .. . . . 
am1 am2 ··· amn
n
The row space of A, is the subspace of R spanned by the rows of A,




Row(A) = span{ a11 a12 ··· a1n , a21 a22 ··· a2n , ..., am1 am2 ··· amn }

The column space of A, is the subspace of Rm spanned by the columns of A,

     

 a11 a12 a1n  
 a21   a22 
  a2n 
Col(A) = span  .  ,  .  , ...,  . 
     

  ..   ..   ..  
 
am1 am2 amn
 
Question

Let A be an m × n matrix,  
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A= . ..  .
 
.. ..
 .. . . . 
am1 am2 ··· amn
The row space is a subspace of
(a) Rn

(b) Rm

The column space is a subspace of

(a) Rn

(b) Rm
Example

 
1 0 2 0
Let A = 0 1 0 2.
1 1 2 2
Columns space of A:
           
 1 0 2 0   1 0 
Col(A) = span 0 , 1 , 0 , 2 = span 0 , 1
1 1 2 2 1 1
   

Row space of A:




Row(A) = span{ 1 0 2 0 , 0 1 0 2 , 1 1 2 2 }



= span{ 1 0 2 0 , 0 1 0 2 }.

Remark: Can use column vectors to represent vectors in row space.

Question

 
5 2 −1 −1
1 −1 4 −3
Let A = 
8 3 −1 −2. Which of the following statements are true?


9 3 0 −3
       

 5 2 −1 −1 
       
1 −1
 ,   ,   , −3 is a basis for the column space of A.
4

(i) 


 8  3  −1  −2 


9 3 0 −3
 
       

 5 1 8 9 
       
2 −1
 ,   ,   ,  3  is a basis for the row space of A.
3

(ii) −1  4  −1  0 

 
−1 −3 −2 −3
 
Example

Suppose        
a1 1 2 2 −1 1 2 2 −1 b1
R2 ↔R3
A = a2  = 1 −2 0 3  −− −−→ 0 1 3 0  = b2  = B.
a3 0 1 3 0 1 −2 0 3 b3

Then it is clear that Row(A) = span{a1 , a2 , a3 } = span{b1 , b2 , b3 } = Row(B) since b1 = a1 , b2 = a3 , and b3 = a2 .

Suppose        
a1 1 2 2 −1 1 2 2 −1 b1
−R3
A = a2  = 1 −2 0 3  −−→ 1 −2 0 3  = b2  = B.
a3 0 1 3 0 0 −1 −3 0 b3

Then it is clear that Row(A) = span{a1 , a2 , a3 } = span{b1 , b2 , b3 } = Row(B) since b1 = a1 , b2 = a2 , and b3 = −a3 .
Example

Suppose        
a1 1 2 2 −1 1 2 2 −1 b1
R −R1
A = a2  = 1 −2 0 3  −−2−−→ 0 −4 −2 4  = b2  = B.
a3 0 1 3 0 0 1 3 0 b3

Then b2 = a2 − a1 tells us that b2 ∈ span{a1 , a2 , a3 }. Since b1 = a1 and b3 = a3 , we can conclude that

Row(B) = span{b1 , b2 , b3 } ⊆ span{a1 , a2 , a3 } = Row(A).

But a2 = b2 + b1 also tells us that a2 ∈ span{b1 , b2 , b3 }. So,

Row(A) = span{a1 , a2 , a3 } ⊆ span{b1 , b2 , b3 } = Row(B).

Hence, we have equality Row(A) = Row(B).

This discussion shows that row operations do not change the row space.
Row Operations Preserves Row Space

Theorem (Row operations preserve row space)

Suppose A and B are row equivalent matrices. Then the row space of A is equal to the row space of B,
Row(A) = Row(B).

Sketch of proof.
Ri ↔Rj
(i) Suppose A −−−−→ B. Then the rows of B are the rows of A rearranged, which will not change the span.
1
cR
i Ri
(ii) Suppose A −−→ B, c ̸= 0. Then Row(B) ⊆ Row(A). But B −c−→ A shows that Row(A) ⊆ Row(B) too.
Ri +aRj Ri −aRj
(iii) Suppose A −−−−→ B. Then Row(B) ⊆ Row(A). But B −−−−→ A shows that Row(A) ⊆ Row(B) too.
Finding Basis for Row Space
Theorem
If a matrix R is in reduced row-echelon form, then the nonzero rows of R form a basis for its row space.

Sketch of proof. 
0 ··· 1 ··· ∗ 0 ··· ∗ 0 ···
0
 ··· 0 ··· 0 1 ··· ∗ 0 · · ·

Write R = 0
 ··· 0 ··· 0 0 ··· 0 1 · · ·
. By definition, the 1 in the leading entry in each nonzero row
0 ··· 0 ··· 0 0 ··· 0 0 · · ·
.. .. .. ..
 
. . . .
is only nonzero entry in that coordinate among the rows. This shows that each nonzero row cannot be a linear
combination of the other rows. Hence, the rows of R are linearly independent. It is clear that the nonzero rows spans
the row space of R.

Theorem
For any matrix A, the nonzero rows of the reduced row-echelon form of A form a basis for for the row space of A.

Proof.
Follows from the fact that A is row equivalent to its reduced row-echelon form R, and that the nonzero rows of R
form a basis for Row(R).
Examples
   
1 0 2 0 1 0 2 0
RREF
1. A = 0 1 0 2 −−−→ 0 1 0 2
1 1 2 2 0 0 0 0



So 1 0 2 0 , 0 1 0 2 is a basis for Row(A).

   
1 2 1 1 0 5
3 4 7  RREF 0
 −−−→  1 −3
2. A = 
−1
.
7 −19 0 0 0
1 9 −13 0 0 0



So 1 0 5 , 0 1 −3 is a basis for Row(A).
Challenge
   
1 1 2 −1 1 0 0 2
RREF
3. A = 0 1 1 0  −−−→ 0 1 0 −1
1 1 0 1 0 0 1 1




So 1 0 0 2 , 0 1 0 −1 , 0 0 1 1 is a basis for Row(A).

However, in this case, we could have taken the original rows of A





1 1 2 −1 , 0 1 1 0 , 1 1 0 1

as a basis for Row(A) too. Why?

Discussion  
1 1 2 −1
Consider the matrix A = 0 1 1 0 . Claim: the 4th column is a linear combination of the first 3 columns. (It
1 1 0 1
should be clear that the columnsare linearly dependent since there are 4 columns and these are vectors in R3 .)
   
1 1 2 −1 1 0 0 0
RREF
A = 0 1 1 0  −−−→ R = 0 1 0 1 
1 1 0 1 0 0 1 −1
We might add a bar between the 3rd and 4th columns to emphasize that we are solving a linear system, but that
would not affect the computation/reduction. From the reduced row-echelon form, we conclude that
       
−1 1 1 2
 0  = 0 0 + 1 − 1
1 1 1 0
But this is exactly the linear relations between the columns of R,
       
0 1 0 0
 1  = 0 0 + 1 − 0
−1 0 0 1
Discussion

In fact, the linear relations between A and its reduced row-echelon form are preserved for any columns. Consider

a1 a2 a3 a4 a5   r1 r2 r3 r4 r5 
2 8 2 4 2 RREF 1 0 3 −2 −3
A= −−−→  = R.
1 6 0 4 3 0 1 −1/2 1 1
−1 −4 −1 −2 −1 0 0 0 0 0

Then
r3 = 3r1 − 21 r2 ←→ a3 = 3a1 − 12 a2
r4 = −2r1 + r2 ←→ a4 = −2a1 + a2
r5 = −3r1 + r2 ←→ a5 = −3a1 + a2

Also, {r1 , r2 } is linearly independent, and so is {a1 , a2 }.

Row Operations Preserves Linear Relations Between Columns
Theorem (Row operations preserve linear relations between columns)



Let A = a1 a2 · · · an and B = b1 b2 · · · bn be row equivalent m × n matrices, where ai and bi is the
i-th column of A and B, respectively, for i = 1, ..., n. Then for any coefficients c1 , c2 , ..., cn ,

c1 a1 + c2 a2 + · · · + cn an = 0

if and only if
c1 b1 + c2 b2 + · · · + cn bn = 0.

Sketch of the proof.

Since A and B are row equivalent, A = PB for some invertible order m matrix P. By block multiplication,



a1 a2 · · · an = A = PB = Pb1 Pb2 · · · Pbn ⇒ ai = Pbi , i = 1, ..., n.

So, if c1 b1 + c2 b2 + · · · + cn bn = 0,

0 = P0 = P(c1 b1 + c2 b2 + · · · + cn bn ) = c1 Pb1 + c2 Pb2 + · · · + cn Pbn = c1 a1 + c2 a2 + · · · + cn an .

Use B = P−1 A to prove the converse.

Finding basis for Column space

Theorem
Suppose R is the reduced row-echelon form of a matrix A. Then the columns of A corresponding to the pivot
columns in R form a basis for the column space of A.

Proof.
First observe that the pivot columns in R are linearly independent since they are just the vectors in the standard basis.
Also, the non-pivot columns of R linearly dependent on the pivot columns. Hence, the columns of A that corresponds
to the pivot columns of R are linearly independent and are sufficient to span Col(A), and thus form a basis.
Question

   
2 1 4 1 2 1 1/2 0 5/6 1/3
4 2 2 3 2 RREF 0
 −−−→ R =  0 1 −1/6 1/3
A= 
2 1 −2 2 0 0 0 0 0 0 
6 3 6 4 4 0 0 0 0 0

Which columns of A form a basis for Col(A)?

Challenge
   
2 1 4 1 2 1 1/2 0 5/6 1/3
4 2 2 3 2 RREF 0 0 1 −1/6 1/3
A= − −−→ R =  
2 1 −2 2 0 0 0 0 0 0 
6 3 6 4 4 0 0 0 0 0
                
1/2 1 5/6 1 0 1/3 1 0
 0  1 0 −1/6 0 1 1/3 0
 1   1
 
1   
         
6 5 0 − 0 ,  0  = 3 0 + 0 ,
  =  ,
 0 =
    
 0  2 0
0 0 0 0 0 0 0 0
                
1 2 1 2 4 2 2 4
2 1 4
3 4  2 
2 4  2 
   
1   
   
1  
  
6 5 2 − −2 ,
 =
2 2 ,
 =  =
1 2 0 3 2 + −2 .

3 6 4 6 6 4 6 6
Since the first and third columns of R are the pivot columns, the first an third columns of A form a basis for Col(A).
However, in this case, we could take any 2 columns of A except columns 1 and 2, to be a basis for the column space
of A. Why?
Question

Which of the follow statements is/are true?

     
1 0 1  1 0 
1. Suppose A is a 3 × 3 matrix whose reduced row-echelon form is 0 1 0. Then the set 0 , 1 is
0 0 0 0 0
 
a basis for the column space of A.

 
1 0 1
0 1 −1
2. Suppose A is a 4 × 3 matrix whose reduced row-echelon form is 
0
. Then we can conclude that the
0 0
0 0 0
first 2 rows of A are linearly independent.
Remarks

1. Row operations do not preserve column space. Consider

   
1 1 R1 ↔R2 0 0
A= −−−−→ B = .
0 0 1 1
   
1 0
Col(A) = span ̸= span
0 1

2. Row operations do no preserve linear relations between the rows. Consider

   
1 1 R2 −2R1 1 1
A= −−−−−→ B = .
2 2 0 0

row 2 of A = 2 × row 1 of A, row 2 of B = 0 × row 1 of B

Question
   
6 2 8 2 4
Is the vector v =  7  in the column space of A =  1 6 0 4 ?
−3 −1 −4 −1 −2

v in the column space of A if and only if there exists coefficients c1 , c2 , c3 , c4 such that
         
2 8 2 4 6
c1  1  + c2  6  + c3  0  + c4  4  =  7  ,
−1 −4 −1 −2 −3

which is equivalent to solving the system

 
 c
4  1
  
2 8 2 6
1 c2   
6 0 4 
c3  = 7 .
−1 −4 −1 −2 −3
c4

This is equivalent to asking if the system Ax = v is consistent.

Column Space and Consistency of Linear System


Let A = u1 u2 ··· uk .
 
c1
 c2 
▶ Then a vector v is in the column space of A, v ∈ Col(A), if and only if we can find a u = 
 ..  such that

.
ck
 
c1

 c2 

Au = u1 u2 · · · uk  .  = c1 u1 + c2 u2 + · · · + ck uk = v.
 .. 
ck
▶ This is equivalent to the system Ax = v being consistent. This is also equivalent to v = Au for some u in Rk .
▶ Hence, the column space can be characterized either by the set of vectors v such that Ax = v is consistent, or
the set of vectors v such that v = Au for some u,

Col(A) = { v = Au u ∈ Rk } = { v Ax = v is consistent }.
Nullspace

Definition
The nullspace of a m × n matrix A is the solution space to the homogeneous system Ax = 0 with coefficient
matrix A. It is denoted as
Null(A) = { v ∈ Rn Av = 0 }.

The nullity of A is the dimension of the nullspace of A, denoted as

nullity(A) = dim(Null(A)).
Question

Let    
2 1 4 1 2 1 1/2 0 5/6 1/3
4 2 2 3 2 RREF 0
 −−−→ R =  0 1 −1/6 1/3
A= .
2 1 −2 2 0 0 0 0 0 0 
6 3 6 4 4 0 0 0 0 0

1. Find a basis for the nullspace of A.

2. What is the nullity of A?

4.2 Rank
Question

For any matrix A, the dimension of the column space of A is equal to the dimension of the row space of A. True or
false?
Rank

Let A be a m × n matrix and R its reduced row-echelon form.

dim(Col(A)) = # of pivot columns in RREF of A,

= # of leading entries in RREF of A,
= # of nonzero rows in RREF of A = dim(Row(A))

Definition
Define the rank of A to be the dimension of its column or row space

rank(A) = dim(Col(A)) = dim(Row(A)).

Exercise

Prove that the rank is invariant under transpose,

rank(A) = rank(AT ).
Examples

1. rank(A) = 0 if and only if A = 0.

   
1 1 2 −1 1 0 0 2
RREF
2. A = 0 1 1 0  −−−→ 0 1 0 −1. So rank(A) = 3.
1 1 0 1 0 0 1 1

   
1 2 3 1 0 0
3 4 2 RREF 0 1 0
3. A = 
 − −−→ 
 . So rank(A) = 3.
−1 7 5 0 0 1
1 9 2 0 0 0

   
1 2 1 1 0 5
3 4 7  RREF 0
 −−−→  1 −3
4. A = 
−1
. So rank(A) = 2.
7 −19 0 0 0
1 9 −13 0 0 0
Challenge: Rank and Consistency of Linear Systems

Prove the following theorem.

Theorem
The linear

system Ax = b is consistent if and only if the rank of A is equal to the rank of the augmented matrix
A|b ,
rank(A) = rank((A | b)).
Properties Rank

 
4 3 5  
3 −1
5 −1 5
 and B = 1
Let A = 
−1 1 . Then rank(A) = 3 and rank(B) = 2. Now,
0 0
3 3
5 2 5
 
30 14
 29 9
AB = 
−3
,
1
32 12

and rank(AB) = 2.

Here rank(AB) ≤ rank(A) and rank(AB) ≤ rank(B).

Properties of Rank

 
  −1 0 −1
1 −1 3
Let A = and B =  0 1 2 . Check that rank(A) = rank(B) = 2. Next,
−1 0 0
3 0 3
 
8 −1 6
AB =
1 0 1

and rank(AB) ≤ rank(A) and rank(AB) ≤ rank(B).

Properties of Rank

 
  −2 −3 −1
1 0 3 −1 −3 −4 −1
Let A = 3 −2 1 −1 and B = 
1
. Check that rank(A) = rank(B) = 2. Now
1 0
3 −2 1 −1
1 0 −1
 
0 0 0
AB = 0 0 0 ⇒ rank(AB) = 0.
0 0 0

Here rank(AB) < rank(A), rank(B).

Properties of Rank

Lemma
Let A be a m × n matrix and B a n × p matrix. The column space of the product AB is a subspace of the column
space of A,
Col(AB) ⊆ Col(A).

Sketch of proof.


Write B = b1 b2 · · · bp . Then



AB = A b1 b2 · · · bp = Ab1 Ab2 · · · Abp .

Recall that Au ∈ Col(A) for all u, and hence, Abi ∈ Col(A) for all i = 1, .., p. Therefore

Col(AB) = span{Ab1 , Ab2 , ..., Abp } ⊆ Col(A).

Properties of Rank

Theorem
Let A be a m × n matrix and B a n × p matrix. Then

rank(AB) ≤ min{rank(A), rank(B)}.

Proof.
By the previous lemma,
rank(AB) = dim(Col(AB)) ≤ dim(Col(A)) = rank(A).
T
Next, using the previous lemma and the above derivation on (AB) = BT AT , we have

rank(AB) = rank((AB)T ) = rank(BT AT ) ≤ rank(BT ) = rank(B).

Hence,
rank(AB) ≤ min{rank(A), rank(B)}.
Question

Show that if A and B are row equivalent matrices, then rank(A) = rank(B).
Rank-Nullity Theorem

Theorem (Rank-Nullity Theorem)

Let A be a m × n matrix. The sum of its rank and nullity is equal to the number of columns,

rank(A) + nullity(A) = n.

Sketch of Proof.
This follows from the fact that the nullity of A is equal to the number of non-pivot columns in its reduced
row-echelon form, and that the rank of A is equal to the number of pivot columns of its reduced row-echelon
form.
Examples

   
1 2 2 −1 1 2 0 5
RREF
A = 3 6 5 0  −−−→ 0 0 1 −3
1 2 1 2 0 0 0 0

   
 1 2 
rank(A) + nullity(A) = 2 + 2 = 4 = number of columns of A. Indeed, 3 , 5 is a basis of the column
1 1
 
   

 −2 −5 
   
1  ,  0  is a basis for the nullspace.

space, and 
 0
    3 

0 1
 

Observe that the column space is a subspace of R3 but the subspace is a subspace of R4 .
Summary of the Subspaces Associated to a Matrix
Let A be a m × n matrix.

Subspace Subspace of Basis Dimension

Columns of A corresponding to rank(A) = no. of pivot columns in

Col(A) Rm
pivot columns in RREF RREF

rank(A) = no. of nonzero rows in

Row(A) Rn Nonzero rows of RREF
RREF

Vectors in general solution to nullity(A) = no. of nonpivot

Null(A) Rn
Ax = 0 columns in RREF
Challenge

Let A and B be matrices of the same size. Prove that

rank(A + B) ≤ rank(A) + rank(B).

Full rank
Let A be a m × n matrix.

rank(A) = # of pivot columns in RREF ≤ no. of columns = n

rank(A) = # of nonzero rows in RREF ≤ no. of rows = m

So, the rank of A is no greater than the number of rows or columns, whichever is smaller,

rank(A) ≤ min{m, n}.

The maximum rank a matrix can attain is when it is equal to either the number of rows or columns, whichever is
smaller.

Definition
A m × n matrix A is said to be of full rank if its rank is equal to either the number of rows or columns,

rank(A) = min{m, n}.

Example
   
1 1 2 −1 1 0 0 2
RREF
1. A = 0 1 1 0  −−−→ 0 1 0 −1 rank(A) = 3 = number of rows, so A is full rank.
1 1 0 1 0 0 1 1
   
1 2 3 1 0 0
 3 4 2 RREF 0 1 0
2. A= −1 7 5 −−−→ 0 0 1 rank(A) = 3 = number of columns, so A is full rank.
  

1 9 2 0 0 0
   
1 1 0 1 1 0 −1 1
RREF
3. A = 0 1 1 0 −−−→ 0 1 1 0 rank(A) = 2 which is strictly smaller than the number rows and
1 2 1 1 0 0 0 0
number of columns. So A is not of full rank.
   
1 0 1 1 0 1
1 1 2 RREF 0 1 1
4. A= 0 1 1 −−−→ 0 0 0 rank(A) = 2 which is strictly smaller than the number rows and number
  

1 0 1 0 0 0
of columns. So A is not of full rank.
Discussion

What happens when a m × n matrix A is full rank? Let us consider cases.

Consider the case when A is a square matrix m = n. Then A is full rank if and only if its is invertible. The proof is
left as an exercise. We will include this in the list of equivalent statements for invertibility.
Equivalent Statements for Invertibility
Theorem
Let A be a square matrix of order n. The following statements are equivalent.
(i) A is invertible.
(ii) AT is invertible.
(iii) (left inverse) There is a matrix B such that BA = I.
(iv) (right inverse) There is a matrix B such that AB = I.
(v) The reduced row-echelon form of A is the identity matrix.
(vi) A can be expressed as a product of elementary matrices.
(vii) The homogeneous system Ax = 0 has only the trivial solution.
(viii) For any b, the system Ax = b has a unique solution.
(ix) The determinant of A is nonzero, det(A) ̸= 0.
(x) The columns/rows of A are linearly independent.
(xi) The columns/rows of A spans Rn .
(xii) rank(A) = n (A has full rank).
(xiii) nullity(A) = 0.
Discussion
Let A be a m × n matrix. Suppose A is not a square matrix m ̸= n, and A is full rank.
Then either rank(A) = n < m, rank(A) = m < n. In either cases, some of the equivalent statements of invertibility
will still be true of A.

Lemma
Let A be a m × n matrix. Then the nullspace of A is equal to the nullspace of AT A,

Null(A) = Null(AT A).

Proof.
Suppose u is in the nullspace of A, Au = 0. Then premultiplying by AT , AT Au = 0 too. This shows that u is in the
nullspace of AT A. This proves Null(A) ⊆ Null(AT A).

Conversely, suppose u is in the nullspace of AT A, AT Au = 0. Premultiplying both sides by uT , and noting that
uT AT Au = (Au) · (Au),
(Au) · (Au) = uT AT Au = uT (0) = 0.
Hence, Au = 0 too, that is, u is in the nullspace of A. This proves that Null(AT A) ⊆ Null(A) too.
Full Rank Equals Number of Columns
Theorem
Suppose A is a m × n matrix. The following statements are equivalent.
(i) A is full rank, where the rank is equal to the number of columns, rank(A) = n.

(ii) The rows of A spans Rn , Row(A) = Rn .

(iii) The columns of A are linearly independent.

(iv) The homogeneous system Ax = 0 has only the trivial solution, that is, Null(A) = {0}.

(v) AT A is an invertible matrix of order n.

(vi) A has a left inverse.

Proof.
We will only prove the equivalence of the last 3 statements, the rest are left as an exercise. Hint: One might try to
prove (i) ⇒ (ii) ⇒ (iii) ⇒ (iv). Observe that if rank(A) = n, then the reduced row-echelon form is of the form
 
In
R= .
0(m−n)×n
Full Rank Equals Number of Columns

Continue of Proof.
(iv) ⇒ (v): Suppose the homogeneous system Ax = 0 has only the trivial solution. By the lemma, the homogeneous
system AT Ax = 0 has only the trivial solution too. But since AT A is a square matrix, by the equivalent statements
of invertibility, AT A is invertible.
(v) ⇒ (vi): Suppose AT A is invertible. Then

I = (AT A)−1 (AT A) = ((AT A)−1 AT )A,

which shows that ((AT A)−1 AT ) is a left inverse of A.

(vi) ⇒ (i): Let B be a left inverse of A, BA = In , where In is the n × n identity matrix. Then by the properties of
rank,
n = rank(I) = rank(BA) ≤ rank(A).
But since rank(A) ≤ n, equality holds.
Example

   
1 01 1 0 0
1 10
. Its reduce row-echelon form is 0 1 0.
 
Let A = 
0 11 0 0 1
1 11 0 0 0
▶ So, A is full
rank, where the rank is equal to the number of columns.
   
3 2 2 5 −2 −2
▶ Check that AT A = 2 3 2 is invertbile, with inverse (AT A)−1 = 17 −2 5 −2.
2 2 3 −2 −2 5
▶ Check that  
3 3 −4 1
1
(AT A)−1 AT = −4 3 3 1
7
3 −4 3 1
is a left inverse of A.
Full Rank Equals Number of Rows

Theorem
Suppose A is a m × n matrix. The following statements are equivalent.
(i) A is full rank, where the rank is equal to the number of rows, rank(A) = m.

(ii) The columns of A spans Rm , Col(A) = Rm .

(iii) The rows of A are linearly independent.

(iv) The linear system Ax = b is consistent for every b ∈ Rm .

(v) AAT is an invertible matrix of order m.

(vi) A has a right inverse.

Full Rank Equals Number of Rows

If rank(A) = m, then the reduced row-echelon form is of the form

 
0 ··· 1 ··· 0 ··· 0 ··· 0 ···
0
 ··· 0 ··· 1 ··· 0 ··· 0 ···


0
 ··· 0 ··· 0 ··· 1 ··· 0 ··· .

 .. .. .. .. ..
··· ··· ··· ···

. . . . . 
0 ··· 0 ··· 0 ··· 0 ··· 1 ···

The proof follows from the previous theorem by replacing A with AT . For statement (iv), use rank-nullity theorem.
The details are left to the readers.
Example

   
1 12 −1 1 0 0 2
Let A = 0 11 0 . The reduced row-echelon form of A is 0 1 0 −1.
1 10 1 0 0 1 1
▶ So, A is full
rank, where the rank is equal to the number of rows.
   
7 3 1 5 −8 1
▶ Check that AAT = 3 2 1 is invertbile, with inverse AAT )−1 1 
= 12 −8 20 −4.
1 1 3 1 −4 5
▶ Check that  
3 −6 3
1 −1 4 1
AT (AAT )−1 = 


6  1 2 −1
−2 2 2
is a right inverse of A.
Challenge

Let A be a m × n matrix such that rank(A) = m. Suppose m > n. By the equivalent statements of full rank equals
number of columns, (AT A) invertible and (AT A)−1 AT . is a left inverse of A.

Now consider the system Ax = b for some vector b in Rm . Premultiplying the left inverse above on both sides of the
equation, we get
x = ((AT A)−1 AT )Ax =((AT A)−1 AT )b,
that is, (AT A)−1 AT )b is a solution to Ax = b. But this is true for every b, which by the equivalent statements of
full rank equals number or rows, means that the rank of A is equal to m, the number of row. This is a contradiction
to m > n.

What is the mistake in the argument above?