Outline of the week

1 Rank and solvabilty of homogeneous and inhomogeneous systems(lec

4)
2 Rn , Subspaces, Linear spans (lec 5)
3 Linear dependence/independence, basis and dimension (lec 5)
4 Row/Column ranks of a matrix, equality (lec 6)
5 Rank-nullity theorem (lec 6)

() January 16, 2017 1 / 28

Equality of row-rank and column-rank

Theorem 1
For any matrix A, its row rank equals its column rank.

Proof:
Consider the reduced REF Â. Let r = rank(A). The pivotal columns are
{e1 , e2 , ..., er } and they are clearly linearly independent. We conclude

rankc (A) ≥ r = rank(A).

Applying the above logic to AT , we get rankc (AT ) ≥ rank(AT ).

But obviously, rankc (AT ) = rank(A) and rank(AT ) = rankc (A).
Hence rank(A) ≥ rankc (A) and equality holds.

() January 16, 2017 2 / 28

Equality of row-rank and column-rank, summary
Let A be a matrix and B be obtained from A by performing EROs. Then

R(A) = R(B) C(A) 6=∗ C(B)

∴ rank(A) = rank(B) -
Positions of the sets of Positions of the sets of
L.I. rows of A L.I. columns of A
6=∗ =
Positions of the sets of Positions of the sets
L.I. rows of B. of L.I. columns of B.
- ∴ rankc (A) = rankc (B).

If we take B to be the reduced REF of A,the r columns with pivots will be

the subset {e1 , ..., er } of Rm . Therefore,

rankc (A) ≥ r = rank(A).

6=∗ above means ”may not be equal to”.

() January 16, 2017 3 / 28
Extracting l.i. subsets by ERO’s
The pivotal columns of any REF Â form a maximal linearly independent
set of columns. So do the corresponding columns of A.

This justifies the following method of extracting a linearly INdependent set

out of any finite set of column vectors of Rn .

If {v1 , v2 , ..., vk } is a set of vectors in Rn , then take the obvious n × k

matrix
V = [v1 v2 ... vk ].
Let in any REF of V there be r pivots. Then
If r = k the set is linearly INdependent.
If r < k the set is linearly DEPendent and if column numbers
k1 , k2 , ..., kr have pivots, then {vk1 , vk2 , ..., vkr } are linearly
INdependent such that
L{v1 , v2 , ..., vk } = L{vk1 , vk2 , ..., vkr }.

() January 16, 2017 4 / 28

An example

Example 2
   
 0 1 
For S = 0 , −2 ⊂ R3 .
 
1 0
 

     
0 1 1 0 1 0
V = 0 −2 7→ 0 −2 7→  0 -2  .
1 0 0 1 0 0

Conclusion: k = 2 = r . Linearly INdependent.

() January 16, 2017 5 / 28

Another eaxample

Example 3
        
 1 1 1 1 
S = v1 = 2 , v2 = 3 , v3 = 4 , v4 =  0  ⊂ R3 .
3 4 5 −1
 

   
1 1 1 1 1 1 1 1
V = 2 3 4 0  7→  0 1 2 −2 .
 
3 4 5 −1 0 0 0 1

Conclusions: (i) 3 = r < k = 4 =⇒ linear DEPendence.

(ii) Since there is no pivot in column 3, drop v3 . Therefore v1 , v2 , v4 form
a linearly INdependent subset s.t. the linear span is unchanged.

() January 16, 2017 6 / 28

Invertibility via rank

Theorem 4
An n × n matrix A is invertible if and only if its rank is n.

Proof: Gauss-Jordan method of finding A−1 shows that the inverse will
exist if and only if the reduced row echelon form of the n × n matrix A
becomes the identity matrix In which has n pivots. [3.0]?

() January 16, 2017 7 / 28

Nullity and the rank-nullity theorem

Definition 5 (Nullity)
If A is any m × n real matrix, the dimension of the null-space N (A) of A is
called the nullity of A and is denoted null(A).

() January 16, 2017 8 / 28

Nullity and the rank-nullity theorem

Definition 5 (Nullity)
If A is any m × n real matrix, the dimension of the null-space N (A) of A is
called the nullity of A and is denoted null(A).

Theorem 6 (Rank-nullity theorem)

Let A be any m × n real matrix. Let null(A) and rank(A) be respectively
the nullity and rank of A. Then

rank(A) + null(A) = n = no. of columns of A)

Caution: The title may suggest rank−nullity. It is rank+nullity

() January 16, 2017 8 / 28

Proof of the rank-nullity theorem

Proof of Theorem 20 : Let  be a row-echelon form of A. Then there will

be r = rank(A) pivots and n − r pivot-free columns. The corresponding
n − r free variables xjt , t = 1, 2, ..., n − r describe the solutions of Ax = 0
i.e. the null-space of A. Setting successively xjt = 1 and rest to be 0, we
get a basis of N (A). Hence

null(A) = n − r = n − rank(A).

On ”solving” we get
rank(A) + null(A) = n.

() January 16, 2017 9 / 28

An example of the rank-nullity equation

Example 7
Consider
 the augmented matrix
 of a homogeneous system Ax = 0.
1 3 1 −2 −3 0
 1 3
 3 −1 −4 0  
 2 6 −4 −7 −3 0 
3 9 1 −7 −8 0
Performing
 ERO 0 s yields: 
1 3 1 −2 −3 0
 1 3
 3 −1 −4 0  
 2 6 −4 −7 −3 0 
3 9 1 −7 −8 0
 
1 3 1 −2 −3 0
E21 (−1),E31 (−2),E42 (−3)  0 2 1 −1 0 
7−→ 
 0 0 −6

−3 3 0 
0 0 −2 −1 10 0

() January 16, 2017 10 / 28

Example contd.

 
1 3 1 −2 −3
E32 (3),E42 (1)
 0
 02 1 −1 
7−→  0
 (REF )
0 0 0 0 
0 0 0 0 0
 

 −6x 2 + 5x 4 + 5x5 

2x
 

 2 

 ⊂ R5 . Here x2 , x4 , x5

The solution set is N (A) =   −x4 + x5 
2x4

 

 

2x5
 
take arbitrary values and we note that the second, fourth and fifth
columns are pivot-free.
Finally, null(A) = 3, rank(A) = 2 and null(A) + rank(A) = 5 which is the
no. of variables or the number of columns of A.

() January 16, 2017 11 / 28

Example extended

 
1 3 1 −2 −3
1 3 3 −1 −4
Given A =  2 6 −4 −7 −3, find a basis of the null space N (A) of


3 9 1 −7 −8
A. The null space is described in the previous slide. Since the real triple
(x2 , x4 , x5 ) can take any value (in R3 ),We 
assign values
  (1, 0, 0), (0,
  1, 0)
−6 5 5
2 0 0
     
and (0, 0, 1) successively, to find v1 =  0  , v2 = −1 , v3 = 
   
1 as

0 2 0
0 0 2
three linearly independent elements of N (A) which form a basis.
We have parametrized N (A) by R3 and also used its standard basis to find
a basis of N (A).

() January 16, 2017 12 / 28

A geometric viewpoint

Rank-Nullity theorem: Let A be an m × n matrix. As a map A : Rn −→ Rm , A

’transmits’ Rn linearly into Rm . Then null(A) is the number of dimensions which
vanish (transmission losses) and rank(A) = dim ARn is the number of dimensions
received. Naturally the sum rank(A) + null(A) = n = dim Rn is the total number
of dimensions transmitted. (A conservation law?)
Solvabilty of Ax = b: Given the linear map A : Rn −→ Rm and b ∈ Rm , we can
solve Ax = b for the unknown x ∈ Rn if and only if b ∈ ARn = C(A).
This geometrically obvious statement is equivalent to rank(A) = rank(A+ ) for the
solvability of the linear systems.
Adjoining b to the columns of A does not increase the linear span viz
LS{A1 , A2 , ..., An } = LS{A1 , A2 , ..., An ; b} ⇐⇒ b ∈ C(A).
Solution set: If p ∈ V is any particular solution i.e. Ap = b, then the set

S = p + N (A) = {p + vv ∈ N (A)}

is the full set of solutions of Ax = p.

The solution set is a parallelly displaced null space N (A). [3.0]

() January 16, 2017 13 / 28

Example 2

 
1 a b 2 −11
0 0 −1 α β 
Let A = 0 0 0 2π
 . Mark the pivots. Show that the first 3
0 
0 0 0 0 0
rows are l.i. in Rn for a suitable n.
Solution:
 
1 a b 2 −11
 0 0 −1 α β 
 
A=  with the pivots highlighted. The rows
0 0 0 2π 0 
0 0 0 0 0
5
are in R so that n = 5. If c1 A1 + c2 A2 + c3 A3 = [0 0 0 0 0], then must
have c1 = 0, bc1 − c2 = 0 =⇒ c2 = 0, 2c1 + αc2 + 2πc3 = 0 =⇒ c3 = 0.
Hence l.i. Any other set of 3 rows must have the 0-row and hence l.d.

() January 16, 2017 14 / 28