LAC Rank and Nullity

Section 4.2 Rank and Nullity

Subsection 4.2.1 Some fundamental subspaces

Let

T : V \to W

be a linear map between vector spaces over a field

F .

We have defined the kernel of

T

\ker (T) = Null (T),

(also called the nullspace) and noted that it is a subspace of the domain

V .

The image of

T

Im (T),

is a subspace of the codomain

W .

🔗

Subsection 4.2.2 The rank-nullity theorem

Given a linear map

T : V \to W,

with

V

finite dimensional, there is a fundamental theorem relating the dimension of

V

to the dimensions of

\ker (T)

and

Im (T) .

🔗

Theorem 4.2.1. The Rank-Nullity Theorem (aka the dimension theorem).

Let

T : V \to W

be a linear map, with

V

a finite-dimensional vector space. Then

🔗

\dim V = rank (T) + nullity (T) = \dim Im (T) + \dim \ker (T) .

🔗

Proof.

Let

n = \dim V,

and recall that if

{v_{1}, \dots, v_{n}}

is any basis for

V,

then

Im (T) = Span ({T (v_{1}), \dots, T (v_{n})}) .

First consider the case that

T

is injective. This means that

\ker (T) = {0},

so that

nullity (T) = 0 .

By Proposition 4.1.3, the set

{T (v_{1}), \dots, T (v_{n})}

is linearly independent, and since this set spans

Im (T),

it is a basis for

Im (T),

so its cardinality equals the dimension of the image, i.e.,

rank (T) .

Thus

rank (T) = n,

and we see that

n = \dim V = n + 0 = rank (T) + nullity (T) .

Now consider the case where

\ker (T) \neq {0} .

Let

{u_{1}, \dots, u_{k}}

be a basis for

\ker (T),

hence

nullity (T) = k .

Since

{u_{1}, \dots, u_{k}}

is a linearly independent set, by [provisional cross-reference: prop-extend-independent-set-to-basis], it can be extended to a basis for

V :

{u_{1}, \dots, u_{k}, u_{k + 1}, \dots, u_{n}}

To establish the theorem, we need only show that

rank (T) = n - k .

Since

{u_{1}, \dots, u_{k}, u_{k + 1}, \dots, u_{n}}

is a basis for

V,

Im (T) = Span ({T (u_{1}), \dots, T (u_{n})}),

but we recall that

u_{1}, \dots, u_{k} \in \ker (T),

so that

Im (T) = Span ({T (u_{k + 1}), \dots, T (u_{n})}) .

Thus we know

rank T \leq n - k .

To obtain an equality, we need only show that the set

{T (u_{k + 1}), \dots, T (u_{n})}

is linearly independent.

Suppose to the contrary, that the set is linearly independent. Then there exists scalars

a_{i} \in F,

not all zero, so that

\sum_{i = k + 1}^{n} a_{i} T (u_{i}) = 0.

By linearity, this says

T (\sum_{i = k + 1}^{r} a_{i} u_{i}) = 0,

which means

\sum_{i = k + 1}^{r} a_{i} u_{i} \in \ker (T) .

But this in turn says that

\sum_{i = k + 1}^{r} a_{i} u_{i} \in Span ({u_{1}, \dots, u_{k}})

implying the full set

{u_{1}, \dots, u_{n}}

is linearly dependent, contradicting that it is a basis for

V .

This completes the proof.

Let’s do a simple example.

🔗

Example 4.2.2.

Consider the linear map

T : P_{3} (R) \to P_{3} (R)

given by

T (f) = f^{″} + f^{'},

where

f^{'}

and

f^{″}

are the first and second derivatives of

f .

🔗

The domain has dimension 4 with standard basis

{1, x, x^{2}, x^{3}},

🔗

Im (T) = Span {T (1), T (x), T (x^{2}), T (x^{3})}

One easily checks that

Im (T) = Span {0, 1, 2 + 2 x, 6 x + 3 x^{2}} = Span {1, x, x^{2}} .

At the very least we know that

rank (T) \leq 3,

and since

T (1) = 0,

we must have

nullity (T) \geq 1 .

Now since

{1, x, x^{2}}

is a linearly independent set, we know that

rank (T) = 3

which means that

nullity (T) = 1

by Theorem 4.2.1. It follows that

{1}

is a basis for the nullspace.

🔗

Subsection 4.2.3 Computing rank and nullity

Let

A \in M_{m \times n} (F)

be a matrix. Then

T (x) = A x

defines a linear map

T : F^{n} \to F^{m} .

Indeed in Subsection 4.3.2, we shall see how to translate the action of an arbitrary linear map between finite-dimensional vectors spaces into an action of a matrix on column vectors.

🔗

Let’s recall how to extract the image and kernel of the linear map

x \mapsto A x .

We know that the image of any linear map is obtained by taking the span of

T (e_{1}), \dots, T (e_{n})

where

{e_{1}, \dots, e_{n}}

is any basis for

F^{n},

the domain. Indeed if we choose the

e_{i}

to be the standard basis vectors (with a 1 in the

i

th coordinate and zeroes elsewhere), then

T (e_{j})

is simply the

j

th column of the matrix

A .

Thus

Im (T)

is the column space of

A .

However to determine the rank of

A,

we would need to know which columns form a basis. We’ll get to that in a moment.

🔗

The nullspace of

T,

is the set of solutions to the homogeneous linear system

A x = 0.

You may recall that a standard method to deduce the solutions is to put the matrix

A

in reduced row-echelon form. That means that all rows of zeros are at the bottom, the leading nonzero entry of each row is a one, and in every column containing a leading 1, all other entries are zero. These leading ones play several roles.

🔗

Proposition 4.2.3.

Given the variables $x_{1}, \dots, x_{n}$ in the system $A x = 0,$ a 1 in the $j$ th column of the reduced row-echelon form of $A,$ called a pivot, means that the variable $x_{j}$ is a constrained variable while the remaining variables are free variables. Thus if there are $r$ pivots, there are $n - r$ free variables, and $n - r = nullity (T);$ it follows that $r = rank (T) .$
The pivot columns of $A$ (the columns of $A$ in which there is a pivot in the reduced row-echelon form of $A$ ) can be taken as a basis of the column space of $A .$
The row rank of $A$ (number of linearly independent rows) equals the column rank of $A$ (number of linearly independent columns).

🔗

Subsection 4.2.4 Elementary Row and Column operations

The following are a series of facts about elementary row and column operations on an

m \times n

matrix

A .

🔗

The matrix $A$ is put in reduced row echelon form by a sequence of elementary row operations.
Each elementary row operation can be achieved by left multiplication of $A$ ( $A \mapsto E A$ ) by an $m \times m$ elementary matrix.
Each elementary column operation can be achieved by right multiplication of $A$ ( $A \mapsto A E$ ) by an $n \times n$ elementary matrix.
Every elementary matrix is invertible and its inverse in again an elementary matrix of the same type.
The rank of an $m \times n$ matrix is unchanged by elementary row or column operations, that is $rank (E A) = rank (A)$ and $rank (A E) = rank (A)$ for appropriately sized elementary matrices $E .$

🔗

Every invertible matrix is a product of elementary matrices, and this leads to the

🔗

Algorithm 4.2.4.

To determine whether an

n \times n

matrix

A

is invertible and if so find its inverse, reduce to row-echelon form the "augmented"

n \times 2 n

matrix

🔗

[A | I_{n}] \mapsto [R | A^{'}] .

🔗

The matrix

A

is invertible if and only if

R = I_{n},

and in that case

A^{'}

is the inverse

A^{- 1} .

🔗

Exercises Exercises

1.

Let

A

be an

m \times n

matrix and

E

an elementary matrix of the appropriate size.

🔗

Are the row spaces of $A$ and $E A$ the same?
Are the column spaces of $A$ and $A E$ the same?
If $R$ is the reduced row-echelon form of $A,$ are the nonzero rows of $R$ a basis for the row space of $A ?$
If $R$ is the reduced row-echelon form of $A,$ is the column space of $R$ the same as the column space of $A ?$

🔗

Answer.

yes; yes; yes (why?); no; If

A = [\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}],

then

R = [\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}],

and

Span ([\begin{matrix} 1 \\ 1 \end{matrix}]) \neq Span ([\begin{matrix} 1 \\ 0 \end{matrix}])

🔗

2.

Given an

m \times n

matrix

A,

show that there exist (appropriately sized) elementary matrices

U, V

so that

U A V

has the form

🔗

U A V = [\begin{matrix} I_{r} & 0 \\ 0 & 0 \end{matrix}] .

where

I_{r}

is an

r \times r

identity matrix with

r = rank (A),

and the other entries are all zeros.

🔗

Prev Top Next