4 Linear algebra 4.15 The rank-nullity theorem 4.17 Column space basis

4.16 Matrix nullspace basis

We are ready to prove that the fundamental solutions of $A\mathbf{x}=\mathbf{0}$ are a basis for $N(A)$ . To set up the notation, suppose $A$ is a $m\times n$ matrix, $R$ is a RREF matrix obtained by doing row operations to $A$ , the number of columns of $R$ with a leading entry is $r$ and the number of columns with no leading entry is $k$ , so $r+k=n$ . Let the numbers of the columns with no leading entry be

j_{1}<j_{2}<\cdots<j_{k}

and the numbers of the columns that do have a leading entry be

i_{1}<i_{2}<\cdots i_{r}

so that the numbers $j_{1},\ldots,j_{k},i_{1},\ldots,i_{r}$ contain all of the numbers $1,\ldots,n$ exactly once. The variable corresponding to a column with no leading entry is called a free parameter because its value can be chosen freely. There are $k$ fundamental solutions to $A\mathbf{x}=\mathbf{0}$ , with the $j$ th fundamental solution defined to be the one where the $j$ th free parameter is 1 and all the other free parameters are 0.

Theorem 4.16.1.

The fundamental solutions to $A\mathbf{x}=\mathbf{0}$ are a basis of the nullspace $N(A)$ .

Before we do the proof, let’s work an example to illustrate how it will go. Free parameters and their coefficients will be coloured red. Take

R=\begin{pmatrix}{\color[rgb]{1,0,0}0}&1&{\color[rgb]{1,0,0}2}&0&{\color[rgb]{% 1,0,0}3}\\ {\color[rgb]{1,0,0}0}&0&{\color[rgb]{1,0,0}0}&1&{\color[rgb]{1,0,0}4}\\ {\color[rgb]{1,0,0}0}&0&{\color[rgb]{1,0,0}0}&0&{\color[rgb]{1,0,0}0}\end{pmatrix}

so that we have $m=3$ and $n=5$ . The columns with no leading entry are 1, 3, and 5 so $k=3$ , ${\color[rgb]{1,0,0}j_{1}}=1,{\color[rgb]{1,0,0}j_{2}}=3,{\color[rgb]{1,0,0}j_{% 3}}=5$ , and variables ${\color[rgb]{1,0,0}x_{1}}$ , ${\color[rgb]{1,0,0}x_{3}}$ , and ${\color[rgb]{1,0,0}x_{5}}$ are the free parameters. The columns with leading entries are 2 and 4, so $r=2$ and $i_{1}=2,i_{2}=4$ . The equations corresponding to $R\mathbf{x}=\mathbf{0}$ are

	$\displaystyle x_{2}+{\color[rgb]{1,0,0}2x_{3}}+{\color[rgb]{1,0,0}3x_{5}}$	$\displaystyle=0$
	$\displaystyle x_{4}+{\color[rgb]{1,0,0}4x_{5}}$	$\displaystyle=0$

(missing off the final one, since it just says $0=0$ ). These equations show that once values for the free parameters are known, the other variables $x_{2}$ and $x_{4}$ are completely determined by those values — we have $x_{2}={\color[rgb]{1,0,0}-2x_{3}-3x_{5}}$ and $x_{4}={\color[rgb]{1,0,0}-4x_{5}}$ .

The three fundamental solutions are

\mathbf{s}_{1}=\begin{pmatrix}{\color[rgb]{1,0,0}1}\\ 0\\ {\color[rgb]{1,0,0}0}\\ 0\\ {\color[rgb]{1,0,0}0}\end{pmatrix},\mathbf{s}_{2}=\begin{pmatrix}{\color[rgb]{% 1,0,0}0}\\ -2\\ {\color[rgb]{1,0,0}1}\\ 0\\ {\color[rgb]{1,0,0}0}\end{pmatrix},\mathbf{s}_{3}=\begin{pmatrix}{\color[rgb]{% 1,0,0}0}\\ -3\\ {\color[rgb]{1,0,0}0}\\ -4\\ {\color[rgb]{1,0,0}1}\end{pmatrix}.

These are linearly independent, because if

a_{1}\mathbf{s}_{1}+a_{2}\mathbf{s}_{2}+a_{3}\mathbf{s}_{3}=\mathbf{0}

then row 1 of this equation shows that $a_{1}=0$ , row 3 shows that $a_{2}=0$ , and row 5 shows that $a_{3}=0$ . To show that the fundamental solutions span, suppose $\mathbf{s}=\begin{pmatrix}s_{1}\\ \vdots\\ s_{5}\end{pmatrix}$ is any vector such that $R\mathbf{s}=\mathbf{0}$ . We claim that $\mathbf{s}$ is equal to $s_{1}\mathbf{s}_{1}+s_{3}\mathbf{s}_{2}+s_{5}\mathbf{s}_{3}$ . Certainly these two vectors have the same entries in rows 1, 3, and 5, since the entries in these rows are $s_{1},s_{3}$ , and $s_{5}$ . What about the entries in rows 2 and 4, that is, the values of $x_{2}$ and $x_{4}$ ? As above, these entries are completely determined by the values of the free parameters. The free parameters are the same for both vectors, so the values of $x_{2}$ and $x_{4}$ are the same as well. We have shown that any solution $\mathbf{s}$ is in the span of the fundamental solutions, so we are done.

Proof.

Theorem 3.9.1 shows that $N(A)=N(R)$ , so we will show that the fundamental solutions are a basis of $N(R)$ .

First we show that the fundamental solutions $\mathbf{s}_{1},\ldots,\mathbf{s}_{k}$ are linearly independent. Suppose that

\sum_{j}a_{j}\mathbf{s}_{j}=\mathbf{0}.

(4.6)

The first fundamental solution corresponds to the variable for column $j_{1}$ , so $\mathbf{s}_{1}$ has a 1 in row $j_{1}$ and all the other fundamental solutions have a 0 there. Thus the entry in row $j_{1}$ on the left hand side of (4.6) is $a_{1}$ , so $a_{1}=0$ . Similarly all the other coefficients are zero.

Now let $\mathbf{s}$ be any solution of $A\mathbf{x}=\mathbf{0}$ and let the entry of $\mathbf{s}$ in row $i$ be $s_{i}$ . We are going to show that

\mathbf{s}=\sum^{k}_{i=1}s_{j_{i}}\mathbf{s}_{i}.

The left hand side and right hand side of this claimed equation are solutions to $R\mathbf{x}=\mathbf{0}$ with the same free parameter values $s_{j_{1}},\ldots,s_{j_{k}}$ . We just have to show that the values of the other variables are the same. But the values of the variables that aren’t free parameters are uniquely determined by the values of the free parameters, because by the RREF property, for $1\leqslant a\leqslant r$ the only equation containing $x_{i_{a}}$ is the one coming from row $a$ of $R$ which has the form

x_{i_{1}}+\cdots=0

where the only other variables occurring with nonzero coefficient are free parameters. Since $\mathbf{s}$ and $\sum^{k}_{i=1}s_{j_{i}}\mathbf{s}_{i}$ are solutions to $R\mathbf{x}=\mathbf{0}$ with the same free parameter values $s_{j_{1}},\ldots,s_{j_{k}}$ , they are equal.

∎