Rank of a matrix

Associate Professor Pham Huu Anh Ngoc

International University

November 7, 2016

Return
1. Linear dependence and independence
Let    

 a1 

   
a2
Rm := v : =  
:
 a1 , a2 , ..., am ∈ R

 | 

 
am
be the set of all m-vectors.
Definition:
A finite set S = {v1 , v2 , ..., vn } of vectors in Rm is said to be linearly
dependent if there exist real numbers c1 , c2 , ..., cn , not all of which are 0,
such that

c1 v1 + c2 v2 + ... + cn vn = 0.
Example: The following vectors are linearly dependent
     
1 1 3
v1 : = 1  , v2 : = −1  , v3 : = 1  ∈ R3
1 2 4
because of
2v1 + v2 − v3 = 0.
1. Linear dependence and independence
Remark:
If a set of vectors is linearly dependent, then one of them can be written
as a linear combination of the others.
Assume that {v1 , v2 , ..., vn } is linearly dependent. Then by definition,
there exist real numbers c1 , c2 , ..., cn , not all of which are 0, such that

c1 v1 + c2 v2 + ... + cn vn = 0.

If c1 �= 0 then,
−c2 −cn
v1 = v2 + ... + vn .
c1 c1
Example: The following vectors are linearly dependent
     
1 1 3
v1 : = 1  , v2 : = −1  , v3 : = 1  ∈ R3
1 2 4

because of
v3 = 2v1 + v2 .
1. Linear dependence and independence
Remark:
If a set of vectors is linearly dependent, then one of them can be written
as a linear combination of the others.
Assume that {v1 , v2 , ..., vn } is linearly dependent. Then by definition,
there exist real numbers c1 , c2 , ..., cn , not all of which are 0, such that

c1 v1 + c2 v2 + ... + cn vn = 0.

If c1 �= 0 then,
−c2 −cn
v1 = v2 + ... + vn .
c1 c1
Example: The following vectors are linearly dependent
     
1 1 3
v1 : = 1  , v2 : = −1  , v3 : = 1  ∈ R3
1 2 4

because of
v3 = 2v1 + v2 .
1. Linear dependence and independence
Remark:
If a set of vectors is linearly dependent, then one of them can be written
as a linear combination of the others.
Assume that {v1 , v2 , ..., vn } is linearly dependent. Then by definition,
there exist real numbers c1 , c2 , ..., cn , not all of which are 0, such that

c1 v1 + c2 v2 + ... + cn vn = 0.

If c1 �= 0 then,
−c2 −cn
v1 = v2 + ... + vn .
c1 c1
Example: The following vectors are linearly dependent
     
1 1 3
v1 : = 1  , v2 : = −1  , v3 : = 1  ∈ R3
1 2 4

because of
v3 = 2v1 + v2 .
1. Linear dependence and independence

Definition: The set S = {v1 , v2 , ..., vn } of vectors in Rm is said to be

linearly independent if it is not linearly dependent.
Thus, S = {v1 , v2 , ..., vn } is linearly independent if

c1 v1 + c2 v2 + ... + cn vn = 0 ⇒ c1 = c2 = ... = cn = 0.

Example: The following vectors are linearly independent

     
1 1 1
v1 : = 0  , v2 : = 1  , v3 : = 1  ∈ R3
0 0 1

because of

c1 v1 + c2 v2 + c3 v3 = 0 ⇒ c1 = c2 = c3 = 0.
1. Linear dependence and independence

Definition: The set S = {v1 , v2 , ..., vn } of vectors in Rm is said to be

linearly independent if it is not linearly dependent.
Thus, S = {v1 , v2 , ..., vn } is linearly independent if

c1 v1 + c2 v2 + ... + cn vn = 0 ⇒ c1 = c2 = ... = cn = 0.

Example: The following vectors are linearly independent

     
1 1 1
v1 : = 0  , v2 : = 1  , v3 : = 1  ∈ R3
0 0 1

because of

c1 v1 + c2 v2 + c3 v3 = 0 ⇒ c1 = c2 = c3 = 0.
Linearly independent vectors
2. Rank of a matrix
Let A be a m × n matrix. Then A has n column vectors v1 , v1 , ..., vn ,
which are m-vectors.
Definition:
The rank of A is the maximal number of linearly independent column
vectors in A, i.e. the maximal number of linearly independent vectors
among v1 , v1 , ..., vn .

If A = 0, then the rank of A is 0.

We write rk(A) for the rank of A.

Example: Let
   
1 1 1 1 1 0
 0 1 1   0 1 1 
A := 
 0
; B :=  
0 1   0 0 0 
0 0 0 0 0 0

Then, rk(A)= 3 and rk(B)= 2.

2. Rank of a matrix
Let A be a m × n matrix. Then A has n column vectors v1 , v1 , ..., vn ,
which are m-vectors.
Definition:
The rank of A is the maximal number of linearly independent column
vectors in A, i.e. the maximal number of linearly independent vectors
among v1 , v1 , ..., vn .

If A = 0, then the rank of A is 0.

We write rk(A) for the rank of A.

Example: Let
   
1 1 1 1 1 0
 0 1 1   0 1 1 
A := 
 0
; B :=  
0 1   0 0 0 
0 0 0 0 0 0

Then, rk(A)= 3 and rk(B)= 2.

2. Rank of a matrix
Theorem:
The rank of a matrix A is the number of non-zero rows in an echelon
matrix obtained from A by elementary row operations.
Computing rank using Gauss elimination:
- Use elementary row operations to reduce A to echelon form.

- The rank of A is the number of non-zero rows in the echelon form.

Example:

The rank of A is 3.
2. Rank of a matrix
Theorem:
The rank of a matrix A is the number of non-zero rows in an echelon
matrix obtained from A by elementary row operations.
Computing rank using Gauss elimination:
- Use elementary row operations to reduce A to echelon form.

- The rank of A is the number of non-zero rows in the echelon form.

Example:

The rank of A is 3.
2. Rank of a matrix
Theorem:
The rank of a matrix A is the number of non-zero rows in an echelon
matrix obtained from A by elementary row operations.
Computing rank using Gauss elimination:
- Use elementary row operations to reduce A to echelon form.

- The rank of A is the number of non-zero rows in the echelon form.

Example:

The rank of A is 3.
Computing rank using determinants
Definition: Let A be an m × n matrix. A minor of A of order k is a
determinant of a k × k sub-matrix of A.

We obtain the minors of order k from A by first deleting m − k rows and

n − k columns, and then computing the determinant.
Computing rank using determinants

Theorem: Let A be an m × n matrix. The rank of A is the maximal order

of a non-zero minor of A.
Computing the rank:

1. Start with the minors of maximal order k. If there is one that is

non-zero, then rk(A) = k.
2. If all maximal minors are zero, then rk(A) < k, and we continue with
the minors of order k − 1 and so on, until we find a minor that is
non-zero.
3. If all minors of order 1 (i.e. all entries in A) are zero, then rk(A) = 0.
Computing rank using determinants

Theorem: Let A be an m × n matrix. The rank of A is the maximal order

of a non-zero minor of A.
Computing the rank:

1. Start with the minors of maximal order k. If there is one that is

non-zero, then rk(A) = k.
2. If all maximal minors are zero, then rk(A) < k, and we continue with
the minors of order k − 1 and so on, until we find a minor that is
non-zero.
3. If all minors of order 1 (i.e. all entries in A) are zero, then rk(A) = 0.
Computing rank using determinants

Theorem: Let A be an m × n matrix. The rank of A is the maximal order

of a non-zero minor of A.
Computing the rank:

1. Start with the minors of maximal order k. If there is one that is

non-zero, then rk(A) = k.
2. If all maximal minors are zero, then rk(A) < k, and we continue with
the minors of order k − 1 and so on, until we find a minor that is
non-zero.
3. If all minors of order 1 (i.e. all entries in A) are zero, then rk(A) = 0.
Computing rank using determinants

Theorem: Let A be an m × n matrix. The rank of A is the maximal order

of a non-zero minor of A.
Computing the rank:

1. Start with the minors of maximal order k. If there is one that is

non-zero, then rk(A) = k.
2. If all maximal minors are zero, then rk(A) < k, and we continue with
the minors of order k − 1 and so on, until we find a minor that is
non-zero.
3. If all minors of order 1 (i.e. all entries in A) are zero, then rk(A) = 0.
Rank of a matrix
Rank of a matrix
Rank of a matrix

Theorem:

Then rk A equals n.
Rank of a matrix

Theorem:

Then rk A equals n.
Rank and linear systems
Consider the linear system of m equations in n unknowns x1 , x2 , ..., xn

(1)
Rank and linear systems
Consider the linear system of m equations in n unknowns x1 , x2 , ..., xn

(1)
Rank and linear systems
Consider the linear system of m equations in n unknowns x1 , x2 , ..., xn

(1)
Theorem:
The linear system (1) is consistent (has solutions) if and only if

rk à = rk A.

If the linear system (1) is consistent, then it has a unique solution if and
only if rkA = n . Moreover, if rk A < n, then the system has n − rk(A)
free variables.
Theorem:
The linear system (1) is consistent (has solutions) if and only if

rk à = rk A.

If the linear system (1) is consistent, then it has a unique solution if and
only if rkA = n . Moreover, if rk A < n, then the system has n − rk(A)
free variables.
Theorem:
The linear system (1) is consistent (has solutions) if and only if

rk à = rk A.

If the linear system (1) is consistent, then it has a unique solution if and
only if rkA = n . Moreover, if rk A < n, then the system has n − rk(A)
free variables.
Rank and linear systems

Solution: Let
   
2 2 −1 2 2 −1 1
A :=  4 0 2 ; Ã :=  4 0 2 2 .
0 6 −3 0 6 −3 4

From rk A= rk à = 3, the system has a unique solution.

Rank and linear systems

Solution: Let
   
2 2 −1 2 2 −1 1
A :=  4 0 2 ; Ã :=  4 0 2 2 .
0 6 −3 0 6 −3 4

From rk A= rk à = 3, the system has a unique solution.

Rank and linear systems
Example: Solve the linear system

x1 + x2 − x3 = 1
2x1 + 2x2 − 2x3 = 2
3x1 + 3x2 − 3x3 = 3

Solution: Let
   
1 1 −1 1 1 −1 1
A :=  2 2 −2  ; Ã :=  2 2 −2 2 .
3 3 −3 3 3 −3 3

From rk A= rk à = 1, the system has infinitely many solutions. More

precisely,
x1 = 1 − a + b, x2 = a, x3 = b,
(x2 , x3 are free variables).