CS 435 : Linear Optimization Fall 2008
Lecture 4: Nullspace. Column Space.
Lecturer: Sundar Vishwanathan
Computer Science & Engineering Indian Institute of Technology, Bombay
1 Solutions to Ax = 0
We now consider the set of all solutions to the system Ax = 0, where A is an m × n matrix and x is a
vector in Rn . From the rest of this lecture, let S = {x : Ax = 0}.
We are almost done understanding this set: S is a subspace of Rn . This is because if x ∈ S then
A(αx) = α(Ax) = 0, so αx ∈ S. Similarly, we can verify that x1 , x2 ∈ S ⇒ x1 + x2 ∈ S.
Having proved that S is a subspace, we ask the natural question: what is its dimension? We give an
answer to this problem in terms of the matrix A. We will, in fact, prove the following in the coming
lectures.
Theorem 1 Suppose k is the number of linearly independent columns in the matrix A. Then, dim(S) =
n − k.
We will then prove a row version of this theorem.
Theorem 3 1 Suppose k is the number of linearly independent rows in the matrix A. Then, dim(S) =
n − k.
This gives, as an interesting and non-trivial corollary, that the number of linearly independent rows in
a matrix is equal to the number of linearly independent columns. Take a moment to reflect on this
statement. Somehow grouping a set of numbers first as rows and then as columns, we get the same
number of linearly independent vectors! This number is defined to be the rank of the matrix A.
One observation
Pn which helps with the proof of the theorems is the fact that x = (x1 x2 . . . xn )T is in
S iff i=1 xi A = 0 where A(i) is the ith column of the matrix A. This is easy to see by writing out
(i)
the above summation.
Consider the subspace {x : Ax = 0}. This is called the nullspace of the matrix A. By the column space
of A, we mean the vector space spanned by the columns of A.
We wish to relate the dimension of the nullspace with the dimension of the space spanned by the vectors
which form the columns of A. How do we go about doing this?
The column perspective is best understood from the following equivalence.
Ax = b ⇔ A(1) x1 + A(2) x2 + . . . + A(n) xn = b
Note that this says that Ax = b has a solution iff b is in the column space of A.
Here, A(i) is the ith column of A and xi is the ith component of vector x.
We need to find all x such that
A(1) x1 + A(2) x2 + . . . + A(n) xn = 0
Our objective is to prove that the dimension of {x : Ax = 0} is n − k where k is the dimension of the
column space of A. How do we begin such a proof? What should the structure of such a proof look
like? It is essential to have a plan of the proof. The first titbit comes from the definition of dimension.
To prove a subspace has dimension n − k we need to exhibit a basis of size n − k.
1
2
Let us begin by noting down what we know, rigourously, as also the obvious inferences that can be made.
Assume that A(1) , A(2) , . . . , A(k) form a basis for the column space of A, that is the space spanned by
A(1) , A(2) , . . . , A(n) .
This implies that we can write the other columns as a linear combination of these columns.
What does this tell us? Let us consider the following equation again.
A(1) x1 + A(2) x2 + A(k) xk + A(k+1) xk+1 . . . + A(n) xn = 0
Now, you need to notice the following fact. Suppose that we set the values of xk+1 through xn arbitrarily.
Then, A(k+1) xk+1 . . . + A(n) xn is a vector in the column space of A and hence we can find x1 , . . . , xk
such that the above equality holds. This tells us that the last n − k variables are free-we can set their
values as we wish and then calculate the values of the others. And this is the reason for the dimension
being n − k.
Let us formally prove all this. First, we identify n − k linearly independent vectors.
We begin by writing the columns not in the basis as linear combinations of the basis.
Pk
A(k+1) = U1,j A(j)
Pj=1
k
A(k+2) = j=1 U2,j A(j)
...
(n)
Pk
A = j=1 Un−k,j A(j)
We claim that in a disguised way we have written down n−k linearly independent vectors in {x : Ax = 0}.
Where?
The equations above give us the vectors we need. The first vector is {−U1,1 , −U1,2 , . . . , −U1,k , 1, 0, . . . , 0}.
We need to refer to this later, so call it U1 . What are the others? The second is {−U2,1 , −U2,2 , . . . , −U2,k , 0, 1, . . . , 0}.
Call this U2 . And Un−k is {−Un−k,1 , −Un−k,2 , . . . , −Un−k,k , 0, 0, . . . , 1}.
Why are these n − k vectors in the space {x : Ax = 0}? And why are they linearly independent?
The equations written above prove that these are in the space {x : Ax = 0}.
The last n − k coordinates confirm the fact that they are indeed linearly independent.
Now, to prove that the dimension of {x : Ax = 0} is exactly n − k. What do we need to do? Again by
definition, we need to show that every other vector can be written as a linear combination of the Ui s.
The trick is to do a bit of reverse engineering. Take any vector in {x : Ax = 0}. If indeed it can be written
as a linear combination of these vectors then what should the coefficients of the linear combinations be?
I recommend that you write this out and see for yourself.
Let x be such that Ax = 0. Here is our thinking. If this x can be written as α1 U1 + · · · + αn−k Un−k
then note that αi must be xk+i . Why?
It is then natural to consider a x0 such that, x0 = {xk+1 Uk+1 + . . . + xn Un }. We need to show that x
and x0 are the same. We will prove that the difference is the zero vector. Note that Ax0 = 0. Why?
Hence A(x − x0 ) = 0
Note that the last n − k components of x − x0 are zero. Hence the above equation implies that the
combination of first k columns of A is zero. Since the first k columns are linearly independent, the linear
combination must be trivial. Hence, x and x0 must coincide on their first k coordinates too. Which
means they must be the same vector.
We have proved that the dimension of {x : Ax0 = 0} is exactly n − k.