Lecture Notes: Rank of a Matrix

Yufei Tao
Department of Computer Science and Engineering
Chinese University of Hong Kong
[email protected]

1 Linear Independence
Definition 1. Let r1 , r2 , ..., rm be vectors of the same dimensionality. Given real values c1 , ..., cn ,
n
X
ci ri
i=1

is called a linear combination of r1 , r2 , ..., rm .

Definition 2. Let r1 , r2 , ..., rm be vectors of the same dimensionality. If we can find real values
c1 , ..., cn such that

• c1 , ..., cn are not all zero;

Pn
• i=1 ci ri = 0

then we say that r1 , ..., rm are linearly dependent. Otherwise, r1 , ..., rm are linearly inde-
pendent.

Example 1. Consider vectors

r1 = [1, 2]
r2 = [0, 1]
r3 = [3, 4].

Note that commas were added between the numbers so that you can see more easily that they are
different numbers. r1 , r2 , and r3 are linearly dependent because

3r1 − 2r2 − r3 = 0.

On the other hand, r1 and r2 are linearly independent because the following equation has a unique
solution c1 = c2 = 0:

c1 r1 + c2 r2 = 0. (1)

1
2 Rank of a Matrix
Definition 3. The rank of a matrix A—denoted as rank A—is the maximum number of linearly
independent row vectors of A.

Example 2. Consider matrix

 
1 2
A =  0 1 .
3 4

Let ri (i ∈ [1, 3]) be the i-th row of A. The rank of A cannot be 3 because we have seen from
Example 1 that r1 , r2 , and r3 are linearly dependent. On the other hand, we already know that
r1 and r2 are linearly independent. It follows that 2 is the maximum number of row vectors that
are linearly independent. Therefore, rank A = 2.

The above example shows a method for calculating the rank of a matrix. However, the method
is not easy to apply when the matrix is large in dimensions. Next, we will give an alternative
method for rank computation which is much easier to use.

Let A and B both be m × n matrices. Recall that A and B are said to be row-equivalent if we
can convert A to B by applying the following elementary row operations:

1. Switch two rows of A.

2. Multiply all numbers of a row of A by the same non-zero value.

3. Let r i and r j be two row vectors of A. Update row r i to r i + r j .

Next, we refer to the above as Operation 1, 2, and 3, respectively.

Lemma 1. If A and B are row-equivalent, then they have the same rank.

Proof. See appendix.

Example 3. We already know from Example 2 that the following matrix has rank 2.
 
1 2
 0 1 .
3 4

By Lemma 1, we know that all the following matrices also have rank 2:
     
1 2 1 5 1 5
 0 3 , 0 3  , and  0 3 
3 4 3 4 3 1

We say that a row of a matrix is a non-zero row if the row contains at least one non-zero value.
Then, we have the following fact:

Lemma 2. If matrix A is in row echelon form, then rank A is the number non-zero rows of A.

2
 The proof is simple and left to you as an exercise.

Example 4. The ranks of the following matrices are 2 and 3, respectively.

 
  1 2 3 4
1 2 3  0
 0 1 3  , and  1 3 0  
 0 0 0 3 
0 0 0
0 0 0 0

Lemmas 1 and 3 suggest the following approach to compute the rank of a matrix A. First,
convert A to a matrix A0 of row echelon form, and then, count the number of non-zero rows of A0 .

Example 5. Next, we use the approach to calculate the rank of the matrix in Example 2 (in the
derivation below, ⇒ indicates applying row elementary operations):
     
1 2 1 2 1 2
 0 1  ⇒  0 1  ⇒  0 1 .
3 4 0 −2 0 0

Example 6. Compute the rank of the following matrix:

 
1 2 3 4
 5 6 7 8 
3 2 1 0

Solution.
     
1 2 3 4 1 2 3 4 1 2 3 4
 5 6 7 8  ⇒  0 −4 −8 −12  ⇒  0 −4 −8 −12 
3 2 1 0 0 −4 −8 −12 0 0 0 0
Hence, the original matrix has rank 2.
Lemma 3. Suppose that r1 , r2 , ..., rk are linearly independent, but r1 , r2 , ..., rk+1 are linearly
dependent. Then, rk+1 must be a linear combination of r1 , r2 , ..., rk .
Proof. Since r1 , r2 , ..., rk+1 are linearly dependent, there exist c1 , ..., ck+1 such that (i) they are
not all zero, and (ii)

c1 r1 + c2 r2 + ... + ck rk + ck+1 rk+1 = 0.

Note that ck+1 cannot be 0. Otherwise, it will follow that c1 r1 +c2 r2 +...+ck rk = 0. Since c1 , ..., ck
cannot be all zero, this means that r1 , ..., rk were linearly dependent, which is a contradiction.

Now that ck+1 6= 0, we have:

c1 c2 ck
rk+1 = r1 + r2 + ... + rk .
ck+1 ck+1 ck+1
Therefore, rk+1 is a linear combination of r1 , r2 , ..., rk .

3
 This implies that, if a matrix has rank k, then there are only k “effective” rows, in the sense
that every other row can be derived as a linear combination of those k rows. For instance, consider
the matrix in Example 6; we know that its rank is 2, and that the first two rows are linearly
independent. Thus, we must be able to represent the 3rd row as a linear combination of the first
two. Indeed, this is true:

[3, 2, 1, 0] = (−2) · [1, 2, 3, 4] + [5, 6, 7, 8].

3 An Important Property of Ranks

In this section, we will prove a non-trivial lemma about ranks.

Lemma 4. The rank of a matrix A is the same as the rank of AT .

Proof. (Sketch) Define the column-rank of A to be the maximum number of independent column
vectors of A. Note that the column-rank of A is exactly the same as the rank of AT . Hence, to
prove the lemma, it suffices to show that the rank of A is the same as the column-rank of A.

We first show:

• Fact 1: If A is in row echelon form, then the rank of A cannot be less than its column-rank.

• Fact 2: Elementary row operations on A do not change its column rank.

The proofs of the above facts are left to you as an exercise. But here are the hints:

• For Fact 1: assume that A has rank k; take k columns appropriately and prove that they
must be linearly independent.

• For Fact 2: it can proved in the same “style” as the proof of Lemma 1.

Since elementary row operations on A do not change its rank, combining both facts shows that the
rank of A is at most its column-rank.

On the other hand, reversing the above argument shows that the column-rank of A is at most
its rank. With this, we complete the lemma.

Example 7. Let
 
1 2 3 4
A =  5 6 7 8 
3 2 1 0

Compute the rank of AT .

Solution. From Example 6, we know that the rank of A is 2. Lemma 4 tells us that the rank of AT
must also be 2.

4
Appendix

Proof of Lemma 1
Let us assume that B is obtained from A after applying one elementary row operation. To prove
the lemma, it suffices to show that A and B have the same rank. Let r1 , r2 , ..., rm be the row
vectors of A.

• Case 1: Operation 1 was applied. In this case, B has exactly the same row vectors as A.
Hence, they have the same rank.

• Case 2: Operation 2 was applied. Let R be an arbitrary non-empty subset of {r1 , r2 , ..., rm }.
Define R0 be the set of corresponding1 rows in B. We will prove:

Claim: R0 is linearly dependent if and only if R0 is linearly dependent.

The claim implies that A and B have the same rank.

Without loss of generality, assume that the row operation multiplies the first row r1 of A
with a value c. In other words, the row vectors of B are cr1 , r2 , ..., rm . If r1 ∈
/ R, then
R0 = R, in which case our claim obviously holds.

It remains to consider that r1 ∈ R. Define k = |R|. Without loss of generality, assume that
R = {r1 , r2 , ..., rk }. The set of corresponding rows in B is R0 = {cr1 , r2 , ..., rk }. If there
exist α1 , ..., αk such that (i) they are not all zero, and (ii)

α1 r1 + α2 r2 + ... + αk rk = 0

it holds that
α1
(cr1 ) + α2 r2 + ... + αk rk = 0
c
In other words, we can find β1 , ..., βk such that (i) they are not all zero, and (ii)

β1 r1 + β2 r2 + ... + βk rk = 0.

Hence, that R being linearly dependent implies R0 being linearly dependent. The reverse of the
above argument shows that R0 being linearly dependent implies R being linearly dependent.

• Case 3: Operation 3 was applied. The proof of this case is similar to the proof of Case 2, and
is left to you as an exercise.

1
The correspondence here means: R0 includes the i-th row of B if and only if R includes the i-th row of A.