Mathematics Prelims

June 11, 2009

The Rank-Nullity Theorem

Filed under: Algebra,Linear Algebra — cjohnson @ 10:02 pm
Tags: , ,

In the last post we defined the column and row space of a matrix as the span of the columns (in the case of the column space) or rows (for the row space) of the matrix.  There’s a third important subspace of a matrix, called the null space, which is the set of all vectors which A maps to zero.  That is, if we think of an m \times n matrix A as a function from \mathcal{F}_{n \times 1} to \mathcal{F}_{m \times 1}, then the null space of A, \text{NS}(A), is simply the kernel of the map.

\displaystyle \text{NS}(A) := \{ X \in \mathcal{F}_{n \times 1} : AX = 0 \}

The dimension of the null space is sometimes called the nullity of the matrix.  There’s an important relationship between the column space, row space, and null space which we’ll now state and prove: if A is an m \times n matrix, then \dim(\text{CS}(A)) + \dim(\text{NS}(A)) = n.

We begin by assuming \{ v_1, ..., v_t \} is a basis for \text{NS}(A).  Since \text{NS}(A) is a subspace of \mathcal{F}_{n \times 1}, we may extend \{ v_1, ..., v_t \} to a basis for all of \mathcal{F}_{n \times 1} by adding r := n - t properly chosen vectors.  Call these vectors u_1, ..., u_r so that \{ v_1, ..., v_t, u_1, ..., u_r \} is a basis for \mathcal{F}_{n \times 1}.  Since this is a basis, let w \in \mathcal{F}_{n \times 1} and suppose

\displaystyle w = \alpha_1 v_1 + ... \alpha_t v_t + \beta_1 u_1 + ... + \beta_r u_r

Now we multiply w on the left by A.  Since Aw \in \text{CS}(A) we have

\displaystyle Aw = A( \alpha_1 v_1 + ... + \alpha_t v_t + \beta_1 u_1 + ... + \beta_r u_r)

\displaystyle = \alpha_1 A v_1 + ... \alpha_t A v_t + \beta_1 A u_1 + ... + \beta_r A u_r

\displaystyle = \beta_1 A u_1 + ... + \beta_r A u_r

where the last step follows from the fact each of v_1, ..., v_t are mapped to zero by A.

Since our choice of w was arbitrary, \{ Au_1, ..., Au_r \} spans \text{CS}(A).  If we can now show that \{ Au_1, ..., Au_r \} are linearly independent we’ll have that \dim(\text{CS}(A)) = r and have proven our theorem.

So now we want to find the \gamma_1, ..., \gamma_r such that

\displaystyle \gamma_1 A u_1 + ... + \gamma_r A u_r = 0

\displaystyle \implies A ( \gamma_1 u_1 + ... + \gamma_r u_r) = 0

\displaystyle \implies \gamma_1 u_1 + ... + \gamma_r u_r \in \text{NS}(A)

\displaystyle \implies \gamma_1 u_1 + ... + \gamma_r u_r = \delta_1 v_1 + ... + \delta_t v_t

\displaystyle \implies \gamma_1 u_1 + ... + \gamma_r u_r - \delta_1 v_1 - ... - \delta_t v_t = 0

Now since \{ v_1, ..., v_t, u_1, ..., u_r \} is a basis for \mathcal{F}_{n \times 1}, we have that \gamma_i = \delta_j = 0, so \{ Au_1, ..., Au_r \} is a linearly independent set which spans \text{CS}(A), so \dim(\text{CS}(A)) = r where r = t - n.  Since t = \dim(\text{NS}(A)), we have our result.

Notice that if Ax = 0, clearly PAx = 0, so that \text{NS}(A) \subseteq \text{NS}(PA).  If P is non-singular, however, it has a trivial null space and so \text{NS}(A) = \text{NS}(PA).  Combining this with the above theorem we have that if P is non-singular,

\displaystyle \dim(\text{CS}(A)) = n - \dim(\text{NS}(A))

\displaystyle = n - \dim(\text{NS}(PA))

\displaystyle = \dim(\text{CS}(PA))

Likewise, \displaystyle \dim(\text{RS}(A)) = \dim(\text{RS}(AQ)) if Q is non-singular.  (Apply the previous argument with \text{CS}(Q^T A^T).)

Picking up from last time, we have if P and Q are the non-singular matrices such that \displaystyle PAQ = \left[ \begin{array}{cc} I_r & 0 \\ 0 & 0 \end{array} \right], then

\displaystyle \dim(\text{CS}(A)) = \dim(\text{CS}(AQ))

\displaystyle = \dim(\text{CS}(PAQ))

\displaystyle = r

\displaystyle = \dim(\text{RS}(PAQ))

\displaystyle = \dim(\text{RS}(PA))

\displaystyle = \dim(\text{RS}(A))

So the dimension of the column space equals the dimension of the row space.  This common value is called the rank of A, and is denoted \text{rank}(A).  For this reason the theorem we proved above is known as the rank-nullity theorem.

Advertisements

1 Comment »

  1. My query relates to the last part of your blog where you prove that the dim of the col space = the dim of the row space.
    I cannot see from what you have done before why the following are immediate:
    dim(CS(A))=dim(CS(AQ))
    and
    dim(RS(PA))=dim(RS(A))

    Comment by Eugene Kernan — August 4, 2009 @ 2:44 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: