In [1]:
#
import numpy as np
import scipy as sp
import pandas as pd
import matplotlib as mp
import matplotlib.pyplot as plt
import seaborn as sns
import sklearn
import laUtilities as ut
import slideUtilities as sl
import demoUtilities as dm
from matplotlib import animation
from importlib import reload
from datetime import datetime
from IPython.display import Image, display_html, display, Math, HTML;
qr_setting = None

mp.rcParams['animation.html'] = 'jshtml';

Announcements¶

  • Homework 5 due today at 8pm

  • Homework 6 is out, due next Friday 3/24 at 8pm

  • Office hours

    • Today: Peer tutor Daniel Cho from 12:30-3:30pm in CCDS 16th floor
    • Today: Abhishek Tiwari from 4-5pm on CCDS 13th floor

  • Weekly reading and viewing assignments

    • Aggarwal sections 2.6-2.7
    • 3Blue1Brown video 7 and video 8

Lecture 21: Vector Subspace and Basis¶

In [2]:
#
fig = ut.three_d_figure((0,0), fig_desc = 'H = Span{a1, a2, a3}',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf a_1$', 'a_1', size=18)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf a_3$', 'a_3', size=18)
fig.text(a2[0]+.5, a2[1]+.5, a2[2]+.5, r'$\bf a_2$', 'a_2', size=18)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.plotPoint(a2[0], a2[1], a2[2],'r')
fig.plotLine([[0, 0, 0], a3], 'r', '--')
fig.plotLine([[0, 0, 0], a1], 'r', '--')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
# fig.set_title(r'$H$ = Span$\{{\bf a}_1, {\bf a}_2, {\bf a}_3\}$')
fig.text(9, -9, -7, r'H', 'H', size = 16)
img = fig.dont_save()

[This lecture is based on Prof. Crovella's CS 132 lecture notes.]

Recap: The Invertible Matrix Theorem¶

Invertible Matrix Theorem. Let AA by a square n×nn×n matrix.

Then the following statements are equivalent; that is, they are either all true or all false.

  1. AA is an invertible matrix.
  2. ATAT is an invertible matrix.
  3. The equation Ax=bAx=b has a unique solution for each bb in Rn.Rn.
  4. A is row equivalent to the identity matrix.
  5. A has nn pivot positions.
  6. The homogeneous equation Ax=0Ax=0 has only the trivial solution.
  7. The columns of AA form a linearly independent set.
  8. The columns of AA span Rn.Rn.
  9. The linear transformation x↦Axx↦Ax maps RnRn onto Rn.Rn.
  10. The linear transformation x↦Axx↦Ax is one-to-one.

21.1 Subspaces¶

So far have been working with vector spaces like R2,R3,R4R2,R3,R4, and so on. But there are more vector spaces!

Today we'll define a subspace and show how the concept helps us understand the nature of matrices and their linear transformations.

Definition. A subspace is any set HH in RnRn that has three properties:

  1. The zero vector is in HH.
  2. For each uu and vv in HH, the sum u+vu+v is in HH.
  3. For each uu in HH and each scalar c,c, the vector cucu is in HH.

Another way of stating properties 2 and 3 is that HH is closed under addition and scalar multiplication.

The first thing to note is that there is a close connection between Span and Subspace:

Every Span is a Subspace.

To see this, let's take a specific example.

For example, take v1v1 and v2v2 in RnRn, and let HH = Span{v1,v2}.{v1,v2}.

Then HH is a subspace of RnRn.

In [12]:
#
fig = ut.three_d_figure((20, 1), fig_desc = 'Span{v1, v2}, a subspace.',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf v_1$', 'v_1', size=20)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf v_2$', 'v_2', size=20)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
#fig.text(a1[0], a1[1], a1[2], r'$\bf v_1$', 'a_1', size=20)
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
fig.set_title(r'Span{$v_1, v_2$}, a subspace.')
fig.text(9, -9, -7, r'$\bf H$', 'H', size = 20)
img = fig.save()

Let's check this:

  1. The zero vector is in HH.

    0=0v1+0v20=0v1+0v2 is in Span{v1,v2}.{v1,v2}.

  1. The sum of any two vectors in HH is in HH.

    If u=s1v1+s2v2,u=s1v1+s2v2, and v=t1v1+t2v2,v=t1v1+t2v2, then their sum u+v=(s1+t1)v1+(s2+t2)v2∈H.u+v=(s1+t1)v1+(s2+t2)v2∈H.

  1. For any scalar cc, cucu is in HH.

    cu=c(s1v1+s2v2)=(cs1v1+cs2v2)∈H.cu=c(s1v1+s2v2)=(cs1v1+cs2v2)∈H.

Because of this, we refer to Span{v1,…,vp}{v1,…,vp} as the subspace spanned by v1,…,vp.v1,…,vp.

OK, here is another subspace -- a line:

In [13]:
#
fig = ut.three_d_figure((20, 2), fig_desc = 'Span{v1}, another subspace.',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
v = [ 4.0, 4.0, 2.0]
fig.text(v[0]+.5, v[1]+.5, v[2]+.5, r'$\bf v_1$', 'v1', size=20)
fig.text(-9, -7, -9, r'Span{$\bf v_1$}', 'Span{v1}', size=16)
fig.text(0.2, 0.2, -4, r'$\bf 0$', '0', size=12)
# plotting the span of v
# this is based on the reduced echelon matrix that expresses the system whose solution is v
fig.plotIntersection([1, 0, -v[0]/v[2], 0], [0, 1, -v[1]/v[2], 0], '-', 'Red')
fig.plotPoint(v[0], v[1], v[2], 'r')
fig.plotPoint(0, 0, 0, 'b')
# plotting the axes
fig.plotIntersection([0, 0, 1, 0], [0, 1, 0, 0])
fig.plotIntersection([0, 0, 1, 0], [1, 0, 0, 0])
fig.plotIntersection([0, 1, 0, 0], [1, 0, 0, 0])
fig.set_title(r'Span {$v_1$}, another subspace.')
img = fig.save()

Next question: is any line a subspace?

What about a line that is not through the origin?

How about this line:

In [5]:
#
ax = ut.plotSetup()
ut.centerAxes(ax)
ax.plot([-6,6],[4.33,0.33],'b-')
ax.text(-4,3,'$L$',size=20);

In fact, a line LL not through the origin fails all three requirements for a subspace:

  1. LL does not contain the zero vector.

  2. LL is not closed under addition.

In [6]:
#
ax = ut.plotSetup()
ut.centerAxes(ax)
ax.arrow(0,0,1,2,head_width=0.2, head_length=0.2,length_includes_head = True)
ax.arrow(0,0,4,1,head_width=0.2, head_length=0.2,length_includes_head = True)
ax.plot([4,5],[1,3],'--')
ax.plot([1,5],[2,3],'--')
ax.plot([-6,6],[4.33,0.33],'b-')
ax.text(5.25,3.25,r'${\bf u}$+${\bf v}$',size=16)
ax.text(1.5,2.5,r'${\bf u}$',size=16)
ax.text(4.75,1,r'${\bf v}$',size=16)
ax.text(-4,3,'$L$',size=20)
ut.plotPoint(ax,5,3)
ax.plot(0,0,'');
  1. LL is not closed under scalar multiplication.
In [7]:
#
ax = ut.plotSetup()
ut.centerAxes(ax)
line = np.array([[-6,6],[4.33,0.33]])
w = .3 * line[:,0] + .7 * line[:,1]
ut.plotPoint(ax,w[0],w[1],'k')
ax.arrow(0,0,w[0],w[1],head_width=0.2, head_length=0.2,length_includes_head = True)
w_ext = np.array([w, 1.75*w]).T
ax.plot(w_ext[0], w_ext[1], '--')
ax.plot(line[0], line[1],'b-')
ax.text(w[0],w[1]-0.5,r'${\bf w}$',size=16)
ax.text(w_ext[0,1], w_ext[1,1]-0.5, r'$\alpha{\bf w}$', size=16)
ut.plotPoint(ax,w_ext[0,1],w_ext[1,1],'r')
ax.text(-4,3,'$L$',size=20);

On the other hand, any line, plane, or hyperplane through the origin is a subspace.

Make sure you can see why (or prove it to yourself).

21.2 Two Important Subspaces¶

Now let's start to use the subspace concept to characterize matrices.

We are thinking of these matrices as linear operators.

Every matrix has associated with it two subspaces:

  • column space and
  • null space.

Column Space¶

Definition. The column space of a matrix AA is the set Col ACol A of all linear combinations of the columns of AA.

If AA = [a1⋯an][a1⋯an], with columns in Rm,Rm, then Col ACol A is the same as Span{a1,…,an}{a1,…,an}, and hence it is a subspace.

The column space of an m×nm×n matrix is a subspace of Rm.Rm.

In particular, note that Col ACol A equals RmRm only when the columns of AA span Rm.Rm. Otherwise, Col ACol A is only part of Rm.Rm.

How to interpret Col ACol A

  • When a system of linear equations is written in the form Ax=b,Ax=b, the column space of AA is the set of all bb for which the system has a solution.

  • Equivalently, when we consider the linear operator T:Rn→RmT:Rn→Rm that is implemented by the matrix AA, the column space of AA is the range of T.T.

In [14]:
#
fig = ut.three_d_figure((20, 3), fig_desc = 'Column Space of A = [a1, a2, a3].',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf a_1$', 'a_1', size=18)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf a_3$', 'a_3', size=18)
fig.text(a2[0]+.5, a2[1]+.5, a2[2]+.5, r'$\bf a_2$', 'a_2', size=18)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.plotPoint(a2[0], a2[1], a2[2],'r')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
fig.set_title(r'Column Space of $A = [{\bf a}_1, {\bf a}_2, {\bf a}_3]$')
fig.text(9, -9, -7, r'Col $A$', 'H', size = 16)
img = fig.save()

Null Space¶

Definition. The null space of a matrix AA is the set Nul ANul A of all solutions of the homogeneous equation Ax=0.Ax=0.

In other words: the null space of AA is the set of all vectors that are mapped to the zero vector by AA. It is sometimes called the kernel of AA.

When AA has nn columns, a solution of Ax=0Ax=0 is a vector in Rn.Rn. So the null space of AA is a subset of Rn.Rn.

In fact, Nul ANul A is a subspace of Rn.Rn.

Theorem. The null space of an m×nm×n matrix AA is a subspace of Rn.Rn.

Equivalently, the set of all solutions of a system Ax=0Ax=0 of mm homogeneous linear equations in nn unknowns is a subspace of Rn.Rn.

Proof.

  1. The zero vector is in Nul ANul A because A0=0.A0=0.

  1. The sum of two vectors in Nul ANul A is in Nul A.Nul A.

    Take two vectors uu and vv that are in Nul A.Nul A. By definition Au=0Au=0 and Av=0.Av=0.

    Then u+vu+v is in Nul ANul A because A(u+v)=Au+Av=0+0=0.A(u+v)=Au+Av=0+0=0.

  1. Any scalar multiple of a vector in Nul ANul A is in Nul A.Nul A.

    Take a vector vv that is in Nul A.Nul A. Then A(cv)=cAv=c0=0.A(cv)=cAv=c0=0.

Testing whether a vector vv is in Nul ANul A is easy: simply compute AvAv and see if the result is zero.

Remark. Note that the two subspaces Col ACol A and Nul ANul A live in different "universes."

For an m×nm×n matrix,

  • the column space is a subset of RmRm (all its vectors have mm components),
  • while the null space is a subset of RnRn (all its vectors have nn components).

21.3 A Basis for a Subspace¶

Let's say you have a subspace.

For example, perhaps it is Span{a1,a2,a3}{a1,a2,a3}.

We would like to find the simplest way of describing this space.

For example, consider this subspace with:

a1=⎡⎢⎣−885⎤⎥⎦,a2=⎡⎢⎣32−2⎤⎥⎦,a3=⎡⎢⎣7.55−5⎤⎥⎦=2.5a2a1=[−885],a2=[32−2],a3=[7.55−5]=2.5a2
In [15]:
#
fig = ut.three_d_figure((20, 4), fig_desc = 'H = Span{a1, a2, a3}',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf a_1$', 'a_1', size=18)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf a_3$', 'a_3', size=18)
fig.text(a2[0]+.5, a2[1]+.5, a2[2]+.5, r'$\bf a_2$', 'a_2', size=18)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.plotPoint(a2[0], a2[1], a2[2],'r')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
fig.set_title(r'$H$ = Span$\{{\bf a}_1, {\bf a}_2, {\bf a}_3\}$')
fig.text(9, -9, -7, r'H', 'H', size = 16)
img = fig.save()

Note that a3a3 is a scalar multiple of a2a2. Thus:

Span{a1,a2,a3}{a1,a2,a3}

is the same subspace as

Span{a1,a2}{a1,a2}.

Making this idea more general:

  • we would like to describe a subspace as the span of a set of vectors, and
  • that set of vectors should have the fewest members as possible!

So in our example above, we would prefer to say that the subspace is:

HH = Span{a1,a2}{a1,a2}

rather than

HH = Span{a1,a2,a3}{a1,a2,a3}.

In other words, the more "concisely" we can describe the subspace, the better.

Now, given some subspace, how small a spanning set can we find?

Here is the key idea we will use to answer that question:

It can be shown that the smallest possible spanning set must be linearly independent.

We will call such minimally-small sets of vectors a basis for the space.

Definition. A basis for a subspace HH of RnRn is a linearly independent set in HH that spans H.H.

In [16]:
#
fig = ut.three_d_figure((20, 5), fig_desc = 'Bases of H are {a1, a2} or {a1, a3}.',
                        xmin = -10, xmax = 10, ymin = -10, ymax = 10, zmin = -10, zmax = 10, qr = qr_setting)
a1 = [-8.0, 8.0, 5.0]
a2 = [3.0,  2.0, -2.0]
a3 = 2.5 * np.array(a2)
fig.text(a1[0]+.5, a1[1]+.5, a1[2]+.5, r'$\bf a_1$', 'a_1', size=18)
fig.text(a3[0]+.5, a3[1]+.5, a3[2]+.5, r'$\bf a_3$', 'a_3', size=18)
fig.text(a2[0]+.5, a2[1]+.5, a2[2]+.5, r'$\bf a_2$', 'a_2', size=18)
fig.plotSpan(a1, a2,'Green')
fig.plotPoint(a1[0], a1[1], a1[2],'r')
fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.plotPoint(a2[0], a2[1], a2[2],'r')
fig.plotLine([[0, 0, 0], a3], 'r', '--')
fig.plotLine([[0, 0, 0], a1], 'r', '--')
# fig.plotPoint(a3[0], a3[1], a3[2],'r')
fig.text(0.1, 0.1, -3, r'$\bf 0$', '0', size=12)
fig.plotPoint(0, 0, 0, 'b')
fig.set_title(r'Bases of $H$ are $\{{\bf a}_1, {\bf a}_2\}$ or $\{{\bf a}_1, {\bf a}_3\}$')
fig.text(9, -9, -7, r'H', 'H', size = 16)
img = fig.save()

So in the example above, a basis for HH could be:

{a1,a2}{a1,a2}

or

{a1,a3}.{a1,a3}.

However,

{a1,a2,a3}{a1,a2,a3}

is not a basis for HH.

That is because {a1,a2,a3}{a1,a2,a3} are not linearly independent.

(Conceptually, there are "too many vectors" in this set).

And furthermore,

{a1}{a1}

is not a basis for HH.

That is because {a1}{a1} does not span HH.

(Conceptually, there are "not enough vectors" in this set).

Example. The columns of any invertible n×nn×n matrix form a basis for Rn.Rn.

This is because, by the Invertible Matrix Theorem, they are linearly independent, and they span Rn.Rn.

So, for example, we could use the identity matrix, I.I. It columns are e1,…,en.e1,…,en.

The set {e1,…,en}{e1,…,en} is called the standard basis for Rn.Rn.

(We have already used the term "standard basis vector" to refer to any of the eiei vectors. Now we know where the term comes from!)

In [17]:
#
fig = ut.three_d_figure((20, 6), fig_desc = 'The Standard Basis for R3',
                        xmin = -1.2, xmax = 1.2, ymin = -1.2, ymax = 1.2, zmin = -1.2, zmax = 1.2, qr = qr_setting)
e1 = [1, 0, 0]
e2 = [0, 1, 0]
e3 = [0, 0, 1]
origin = [0, 0, 0]
fig.ax.quiver(e1, e2, e3, e1, e2, e3, length=1.0, color='Red')
fig.plotLine([[0, 0, 0], [0, 1, 0]], color='Red')
fig.plotLine([[0, 0, 0], [0, 0, 1]], color='Red')
fig.plotLine([[0, 0, 0], [1, 0, 0]], color='Red')
fig.text(1, 0, -0.5, r'${\bf e_1}$', 'e1', size=16)
fig.text(0.2, 1, 0, r'${\bf e_2}$', 'e2', size=16)
fig.text(0, 0.2, 1, r'${\bf e_3}$', 'e3', size=16)
# plotting the axes
fig.plotIntersection([0, 0, 1, 0], [0, 1, 0, 0])
fig.plotIntersection([0, 0, 1, 0], [1, 0, 0, 0])
fig.plotIntersection([0, 1, 0, 0], [1, 0, 0, 0])
fig.set_title(r'The Standard Basis for $\mathbb{R}^3$',size=14);
fig.save();

21.4 Basis for Null Space¶

Being able to express a subspace in terms of a basis is very powerful.

  • It gives us a concise way of describing the subspace.
  • It will allow us (in future lectures) to introduce ideas of coordinate systems and dimension.

Hence, we will often want to be able to describe subspaces like ColACol⁡A or NulANul⁡A using their bases.

We'll start with finding a basis for the null space of a matrix.

Example. Find a basis for the null space of the matrix

A=⎡⎢⎣−36−11−71−223−12−458−4⎤⎥⎦.A=[−36−11−71−223−12−458−4].

Solution. We would like to describe the set of all solutions of Ax=0.Ax=0.

We start by writing the solution of Ax=0Ax=0 in parametric form:

[A0]∼⎡⎢ ⎢⎣1−20−1300012−20000000⎤⎥ ⎥⎦,x1−2x2−x4+3x5=0x3+2x4−2x5=00=0[A0]∼[1−20−1300012−20000000],x1−2x2−x4+3x5=0x3+2x4−2x5=00=0

So x1x1 and x3x3 are basic, and x2,x4,x2,x4, and x5x5 are free.

So the general solution is:

x1=2x2+x4−3x5,x3=−2x4+2x5.x1=2x2+x4−3x5,x3=−2x4+2x5.

Now, what we want to do is write the solution set as a weighted combination of vectors.

This is a neat trick -- we are creating a vector equation.

The key idea is that the free variables will become the weights.

⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣x1x2x3x4x5⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦=⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣2x2+x4−3x5x2−2x4+2x5x4x5⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦[x1x2x3x4x5]=[2x2+x4−3x5x2−2x4+2x5x4x5]
=x2⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣21000⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦+x4⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣10−210⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦+x5⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣−30201⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦=x2[21000]+x4[10−210]+x5[−30201]
=x2u+x4v+x5w.=x2u+x4v+x5w.

Now what we have is an expression that describes the entire solution set of Ax=0.Ax=0. So Nul ANul A is the set of all linear combinations of u,v,u,v, and ww. That is, Nul ANul A is the subspace spanned by {u,v,w}.{u,v,w}.

Furthermore, this construction automatically makes u,v,u,v, and ww linearly independent. Since each weight appears by itself in one position, the only way for the whole weighted sum to be zero is if every weight is zero -- which is the definition of linear independence.

So {u,v,w}{u,v,w} is a basis for Nul A.Nul A.

Conclusion: by finding a parametric description of the solution of the equation Ax=0,Ax=0, we can construct a basis for the nullspace of AA.

21.5 The Dimension of a Subspace¶

It can be shown that if a subspace HH has a basis of pp vectors, then every basis of HH must consist of exactly pp vectors.

That is, for a given HH, the number pp is a special number.

Definition. The dimension of a nonzero subspace H,H, denoted by dimH,dim⁡H, is the number of vectors in any basis for H.H.

The dimension of the zero subspace {0}{0} is defined to be zero.

So now we can say with precision things we've previously said informally.

For example, a plane through 00 is two-dimensional, and a line through 00 is one-dimensional.

Remark: What is the dimension of a line not through the origin? It is undefined, because a line not through the the origin is not a subspace, so cannot have a basis, so does not have a dimension.

Remember that associated to any matrix AA are two special subspaces: the null space and column space of a matrix AA. Let's determine the dimension of each subspace.

Dimension of the Null Space¶

Earlier we showed the following: one can construct a basis for Nul ANul⁡ A using the columns corresponding to free variables in the solution of Ax=0Ax=0.

We looked at the following example:

A=⎡⎢⎣−36−11−71−223−12−458−4⎤⎥⎦A=[−36−11−71−223−12−458−4]

We constructed an explicit description of the null space of this matrix, as x=x2u+x4v+x5wx=x2u+x4v+x5w where uu, vv, and ww are linearly independent.

Each basis vector corresponds to a free variable in the equation Ax=0.Ax=0. Since this basis contains 3 vectors, the dimension of AA's null space (ie, dimNulAdim⁡Nul⁡A) is 3.

In general, to find the dimension of Nul A,Nul⁡ A, simply identify and count the number of free variables in Ax=0.Ax=0.

21.6 Basis and Dimension for Column Space¶

To find a basis for the column space, we have an easier starting point.

We know that the column space is the span of the matrix columns.

So, we can choose matrix columns to make up the basis.

The question is: which columns should we choose?

Warmup.

We start with a warmup example.

Suppose we have a matrix BB that happens to be in reduced echelon form:

B=⎡⎢ ⎢ ⎢⎣10−350012−100000100000⎤⎥ ⎥ ⎥⎦.B=[10−350012−100000100000].

Denote the columns of BB by b1,…,b5b1,…,b5.

Note that b3=−3b1+2b2b3=−3b1+2b2 and b4=5b1−b2.b4=5b1−b2.

So any combination of b1,…,b5b1,…,b5 is actually just a combination of b1,b2,b1,b2, and b5.b5.

So {b1,b2,b5}{b1,b2,b5} spans Col BCol B.

Also, b1,b2,b1,b2, and b5b5 are linearly independent, because they are columns from an identity matrix.

So: the pivot columns of BB form a basis for Col B.Col B.

Note that this means: there is no combination of columns 1, 2, and 5 that yields the zero vector. (Other than the trivial combination of course.)

So, for matrices in reduced row echelon form, we have a simple rule for the basis of the column space:

Choose the columns that hold the pivots.

The general case.

Now I'll show that the pivot columns of AA form a basis for Col ACol A for any AA.

Consider the case where Ax=0Ax=0 for some nonzero x.x.

This says that there is a linear dependence relation between some of the columns of AA.

If any of the entries in xx are zero, then those columns do not participate in the linear dependence relation.

When we row-reduce AA to its reduced echelon form BB, the columns are changed, but the equations Ax=0Ax=0 and Bx=0Bx=0 have the same solution set.

So this means that the columns of AA and the columns of BB have exactly the same dependence relationships as the columns of BB. Specifically:

  1. If some column of BB can be written as a combination of other columns of BB, then the same is true of the corresponding columns of AA.

  2. If no combination of certain columns of BB yields the zero vector, then no combination of corresponding columns of AA yields the zero vector.

In other words:

  1. If some set of columns of BB spans the column space of BB, then the same columns of AA span the column space of AA.

  2. If some set of columns of BB are linearly independent, then the same columns of AA are linearly independent.

So, if some columns of BB are a basis for Col BCol B, then the corresponding columns of AA are a basis for Col ACol A.

Example. Consider the matrix AA:

A=⎡⎢ ⎢ ⎢⎣1332−9−2−22−822307134−111−8⎤⎥ ⎥ ⎥⎦A=[1332−9−2−22−822307134−111−8]

To find its basis, we simply need to look at the basis for its reduced row echelon form.

It turns out that AA is row equivalent to the matrix BB that we considered above. For matrix BB, recall that:

  • b3=−3b1+2b2b3=−3b1+2b2 and b4=5b1−b2b4=5b1−b2.
  • A basis for Col BCol B was columns 1, 2, and 5.

Therefore we can immediately conclude that a basis for Col ACol A is AA's columns 1, 2, and 5.

So a basis for Col ACol A is:

⎧⎪ ⎪ ⎪⎨⎪ ⎪ ⎪⎩⎡⎢ ⎢ ⎢⎣1−223⎤⎥ ⎥ ⎥⎦,⎡⎢ ⎢ ⎢⎣3−234⎤⎥ ⎥ ⎥⎦,⎡⎢ ⎢ ⎢⎣−921−8⎤⎥ ⎥ ⎥⎦⎫⎪ ⎪ ⎪⎬⎪ ⎪ ⎪⎭{[1−223],[3−234],[−921−8]}

Theorem. The pivot columns of a matrix AA form a basis for the column space of AA.

Be careful here -- note that

  • we compute the reduced row echelon form of AA to find which columns are pivot columns, but...
  • we use the columns of AA itself as the basis for Col ACol A!

Matrix Rank¶

Definition. The rank of a matrix, denoted by RankA,Rank⁡A, is the dimension of the column space of AA.

Since the pivot columns of AA form a basis for ColA,Col⁡A, the rank of AA is just the number of pivot columns in AA. This is also equal to the number of basic variables in Ax=0Ax=0 (hopefully now the term makes sense!)

Example. Determine the rank of the matrix

A=⎡⎢ ⎢ ⎢⎣25−3−4847−4−3969−5240−965−6⎤⎥ ⎥ ⎥⎦.A=[25−3−4847−4−3969−5240−965−6].

Solution Reduce AA to an echelon form:

A=⎡⎢ ⎢ ⎢⎣25−3−480−325−70−6414−200−965−6⎤⎥ ⎥ ⎥⎦∼⋯∼⎡⎢ ⎢ ⎢⎣25−3−480−325−70004−600000⎤⎥ ⎥ ⎥⎦.A=[25−3−480−325−70−6414−200−965−6]∼⋯∼[25−3−480−325−70004−600000].

The matrix AA has 3 pivot columns, so RankA=3.Rank⁡A=3.

21.7 The Rank Theorem¶

Consider a matrix A.A. We know that:

  • dimNul Adim⁡Nul⁡ A = the number of free variables in Ax=0Ax=0, which is the number of non-pivot columns in AA.

  • dimCol Adim⁡Col⁡ A = the number of basis variables in Ax=0Ax=0, which is the number of pivot columns.

So we can now make this important connection:

dimNul A+dimCol A=number of non-pivot columns of A + number of pivot columns of A=number of columns of A.dim⁡Nul⁡ A+dim⁡Col⁡ A=number of non-pivot columns of A + number of pivot columns of A=number of columns of A.

This relationship involving dimension is true even though the two subspaces themselves live in different spaces: Nul A⊂RnNul⁡ A⊂Rn and Col A⊂RmCol⁡ A⊂Rm.

This leads to the following theorem:

Theorem. If a matrix AA has nn columns, then RankA+dimNul A=nRank⁡A+dim⁡Nul⁡ A=n.

This is a terrifically important fact! Here is an intuitive way to understand it. Let's think about a matrix AA and the associated linear transformation T(x)=AxT(x)=Ax.

  • If the matrix AA has nn columns, then AA's column space could have dimension as high as nn. In other words, TT's range could have dimension as high as nn.

  • However, if AA "throws away" a nullspace of dimension pp, then that reduces the column space of AA to n−pn−p. Meaning, the dimension of TT's range is reduced to n−pn−p.

Extending the Invertible Matrix Theorem¶

The above arguments show that when AA has nn columns, then the "larger" that the column space is, the "smaller" that the null space is.

(Where "larger" means "has more dimensions.")

Let's consider what this means when AA is square (n×n)(n×n). On one "extreme," the column space of AA could have maximum dimension -- i.e., dimCol A=n.dim⁡Col⁡ A=n.

Recall that the IMT said that an n×nn×n matrix is invertible if and only if its columns are linearly independent, and if and only if its columns span Rn.Rn.

Hence we now can see that an n×nn×n matrix is invertible if and only if the columns of AA form a basis for Rn.Rn.

This leads to the following facts, which further extend the IMT:

Theorem. Let AA be a square n×nn×n matrix. Then the following statements are each equivalent to the statement that AA is an invertible matrix:

  1. The columns of AA form a basis for Rn.Rn.
  2. ColA=Rn.Col⁡A=Rn.
  3. dimColA=n.dim⁡Col⁡A=n.
  4. RankA=n.Rank⁡A=n.
  5. NulA={0}.Nul⁡A={0}.
  6. dimNulA=0.dim⁡Nul⁡A=0.
In [ ]: