Editing Kernel (linear algebra) (section)

==Computation by Gaussian elimination==
A [[Basis (linear algebra)|basis]] of the kernel of a matrix may be computed by [[Gaussian elimination]].

For this purpose, given an {{math|''m'' × ''n''}} matrix {{mvar|A}}, we construct first the row [[augmented matrix]] <math> \begin{bmatrix}A \\ \hline I \end{bmatrix},</math> where {{math|''I''}}<!-- necessary to ensure a serif font --> is the {{math|''n'' × ''n''}} [[identity matrix]].

Computing its [[column echelon form]] by Gaussian elimination (or any other suitable method), we get a matrix <math> \begin{bmatrix} B \\\hline C \end{bmatrix}.</math> A basis of the kernel of {{Mvar|A}} consists in the non-zero columns of {{mvar|C}} such that the corresponding column of {{mvar|B}} is a [[zero matrix|zero column]].

In fact, the computation may be stopped as soon as the upper matrix is in column echelon form: the remainder of the computation consists in changing the basis of the vector space generated by the columns whose upper part is zero.

For example, suppose that
<math display="block">A = \begin{bmatrix}
1 & 0 & -3 & 0 &  2 & -8 \\
0 & 1 &  5 & 0 & -1 & 4 \\
0 & 0 &  0 & 1 & 7 & -9 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}. </math>
Then
<math display="block"> \begin{bmatrix} A \\ \hline I \end{bmatrix} =
\begin{bmatrix}
1 & 0 & -3 & 0 &  2 & -8 \\
0 & 1 &  5 & 0 & -1 & 4 \\
0 & 0 &  0 & 1 & 7 & -9 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\hline
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}. </math>

Putting the upper part in column echelon form by column operations on the whole matrix gives
<math display="block"> \begin{bmatrix} B \\ \hline C \end{bmatrix} =
\begin{bmatrix}
1 & 0 &  0 & 0 &  0 & 0 \\
0 & 1 &  0 & 0 &  0 & 0 \\
0 & 0 &  1 & 0 &  0 & 0 \\
0 & 0 &  0 & 0 &  0 & 0 \\
\hline
1 & 0 &  0 & 3 & -2 & 8 \\
0 & 1 &  0 & -5 & 1 & -4 \\
0 & 0 &  0 & 1 & 0 & 0 \\
0 & 0 &  1 & 0 & -7 & 9 \\
0 & 0 &  0 & 0 & 1 & 0 \\
0 & 0 &  0 & 0 & 0 & 1
\end{bmatrix}. </math>

The last three columns of {{mvar|B}} are zero columns. Therefore, the three last vectors of {{mvar|C}},
<math display="block">\left[\!\! \begin{array}{r} 3 \\ -5 \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right] ,\;
\left[\!\! \begin{array}{r} -2 \\ 1 \\ 0 \\ -7 \\ 1 \\ 0 \end{array} \right],\;
\left[\!\! \begin{array}{r} 8 \\ -4 \\ 0 \\ 9 \\ 0 \\ 1 \end{array} \right] </math>
are a basis of the kernel of {{mvar|A}}.

Proof that the method computes the kernel: Since column operations correspond to post-multiplication by invertible matrices, the fact that <math>\begin{bmatrix} A \\ \hline I \end{bmatrix}</math> reduces to <math>\begin{bmatrix} B \\ \hline C \end{bmatrix}</math> means that there exists an invertible matrix <math>P</math> such that <math> \begin{bmatrix} A \\ \hline I \end{bmatrix} P = \begin{bmatrix} B \\ \hline C \end{bmatrix}, </math> with <math>B</math> in column echelon form. Thus {{nowrap|<math>AP = B</math>,}} {{nowrap|<math>IP = C </math>,}} and {{nowrap|<math> AC = B </math>.}} A column vector <math>\mathbf v</math> belongs to the kernel of <math>A</math> (that is <math>A \mathbf v = \mathbf 0</math>) if and only if <math>B \mathbf w = \mathbf 0,</math> where {{nowrap|<math>\mathbf w = P^{-1} \mathbf v = C^{-1} \mathbf v</math>.}} As <math>B</math> is in column echelon form, {{nowrap|<math>B \mathbf w = \mathbf 0</math>,}} if and only if the nonzero entries of <math>\mathbf w</math> correspond to the zero columns of {{nowrap|<math>B</math>.}} By multiplying by {{nowrap|<math>C</math>,}} one may deduce that this is the case if and only if <math>\mathbf v = C \mathbf w</math> is a linear combination of the corresponding columns of {{nowrap|<math>C</math>.}}