Editing Rank–nullity theorem (section)

===Second proof===

Let <math>\mathbf{A}</math> be an <math>m\times n</math> matrix with <math>r</math> [[linearly independent]] columns (i.e. <math>\operatorname{Rank}(\mathbf{A}) = r</math>). We will show that:
{{ordered list|type=lower-roman
  |1= There exists a set of <math>n - r</math> linearly independent solutions to the homogeneous system <math>\mathbf{Ax} = \mathbf{0}</math>.
  |2= That every other solution is a linear combination of these <math>n-r</math> solutions.
}}

To do this, we will produce an <math>n \times (n-r)</math> matrix <math>\mathbf{X}</math> whose columns form a [[basis (linear algebra)|basis]] of the null space of <math>\mathbf{A}</math>.

Without loss of generality, assume that the first <math>r</math> columns of <math>\mathbf{A}</math> are linearly independent. So, we can write
<math display="block">\mathbf{A} = \begin{pmatrix} \mathbf{A}_1 & \mathbf{A}_2\end{pmatrix} ,</math>
where
*<math>\mathbf{A}_1</math> is an <math>m \times r</math> matrix with <math>r</math> linearly independent column vectors, and
*<math>\mathbf{A}_2</math> is an <math>m\times (n-r)</math> matrix such that each of its <math>n-r</math> columns is linear combinations of the columns of <math>\mathbf{A}_1</math>.

This means that <math>\mathbf{A}_2 = \mathbf{A}_1\mathbf{B}</math> for some <math>r \times (n-r)</math> matrix <math>\mathbf{B}</math> (see [[rank factorization]]) and, hence,
<math display="block">\mathbf{A} = \begin{pmatrix} \mathbf{A}_1 & \mathbf{A}_1\mathbf{B}\end{pmatrix} .</math>

Let
<math display="block">\mathbf{X} = \begin{pmatrix} -\mathbf{B} \\ \mathbf{I}_{n-r} \end{pmatrix} , </math>
where <math>\mathbf{I}_{n-r}</math> is the <math>(n-r)\times (n-r)</math> [[identity matrix]]. So, <math>\mathbf{X}</math> is an <math>n \times (n-r)</math> matrix such that
<math display="block"> \mathbf{A}\mathbf{X} = \begin{pmatrix}\mathbf{A}_1 & \mathbf{A}_1\mathbf{B} \end{pmatrix}\begin{pmatrix} -\mathbf{B} \\ \mathbf{I}_{n-r} \end{pmatrix} = -\mathbf{A}_1\mathbf{B} + \mathbf{A}_1\mathbf{B} = \mathbf{0}_{m \times (n-r)}. </math>

Therefore, each of the <math>n-r</math> columns of <math>\mathbf{X}</math> are particular solutions of <math>\mathbf{Ax} = {0}_{{F}^{m}}</math>.

Furthermore, the <math>n-r</math> columns of <math>\mathbf{X}</math> are [[linearly independent]] because <math>\mathbf{Xu} = \mathbf{0}_{{F}^{n}}</math> will imply <math>\mathbf{u} = \mathbf{0}_{{F}^{n-r}}</math> for <math>\mathbf{u} \in {F}^{n-r}</math>:
<math display="block"> \mathbf{X}\mathbf{u} = \mathbf{0}_{{F}^{n}} \implies \begin{pmatrix}
-\mathbf{B} \\
 \mathbf{I}_{n-r}
\end{pmatrix}\mathbf{u} = \mathbf{0}_{{F}^{n}} \implies \begin{pmatrix}
-\mathbf{B}\mathbf{u} \\
 \mathbf{u}
\end{pmatrix} = \begin{pmatrix}
\mathbf{0}_{{F}^{r}} \\
 \mathbf{0}_{{F}^{n-r}}
\end{pmatrix} \implies \mathbf{u} = \mathbf{0}_{{F}^{n-r}}.</math>
Therefore, the column vectors of <math>\mathbf{X}</math> constitute a set of <math>n-r</math> linearly independent solutions for <math>\mathbf{Ax} = \mathbf{0}_{\mathbb{F}^{m}}</math>.

We next prove that ''any'' solution of <math>\mathbf{Ax} = \mathbf{0}_{{F}^{m}}</math> must be a [[linear combination]] of the columns of <math>\mathbf{X}</math>.

For this, let
<math display="block">\mathbf{u} = \begin{pmatrix}
 \mathbf{u}_1 \\
 \mathbf{u}_2
\end{pmatrix} \in {F}^{n}</math>

be any vector such that <math>\mathbf{Au} = \mathbf{0}_{{F}^{m}}</math>. Since the columns of <math>\mathbf{A}_1</math> are linearly independent, <math>\mathbf{A}_1\mathbf{x} = \mathbf{0}_{{F}^{m}}</math> implies <math>\mathbf{x} = \mathbf{0}_{{F}^{r}}</math>.

Therefore,
<math display="block">\begin{array}{rcl}
\mathbf{A}\mathbf{u} & = & \mathbf{0}_{{F}^{m}} \\
\implies \begin{pmatrix}\mathbf{A}_1 & \mathbf{A}_1\mathbf{B}\end{pmatrix} \begin{pmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \end{pmatrix} & = & \mathbf{A}_1\mathbf{u}_1 + \mathbf{A}_1\mathbf{B}\mathbf{u}_2 & = & \mathbf{A}_1(\mathbf{u}_1 + \mathbf{B}\mathbf{u}_2) & = & \mathbf{0}_{\mathbb{F}^{m}} \\
\implies \mathbf{u}_1 + \mathbf{B}\mathbf{u}_2 & = & \mathbf{0}_{{F}^{r}} \\
\implies \mathbf{u}_1 & = & -\mathbf{B}\mathbf{u}_2
\end{array}</math>
<math display="block"> \implies \mathbf{u} = \begin{pmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \end{pmatrix}
= \begin{pmatrix} -\mathbf{B} \\ \mathbf{I}_{n-r} \end{pmatrix}\mathbf{u}_2
= \mathbf{X}\mathbf{u}_2. </math>

This proves that any vector <math>\mathbf{u}</math> that is a solution of <math>\mathbf{Ax} = \mathbf{0}</math> must be a linear combination of the <math>n-r</math> special solutions given by the columns of <math>\mathbf{X}</math>. And we have already seen that the columns of <math>\mathbf{X}</math> are linearly independent. Hence, the columns of <math>\mathbf{X}</math> constitute a basis for the [[null space]] of <math>\mathbf{A}</math>. Therefore, the [[kernel (matrix)|nullity]] of <math>\mathbf{A}</math> is <math>n - r</math>. Since <math>r</math> equals rank of <math>\mathbf{A}</math>, it follows that <math>\operatorname{Rank}(\mathbf{A}) + \operatorname{Nullity}(\mathbf{A}) = n</math>. This concludes our proof.