# 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.