\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Algebra

Reduced row echelon form

Reduced row echelon form is the matrix arrived at after back substitution is continued further to produce zeros above the pivots.

From reduced row echelon form of a matrix \( A \), it is easy to calculate the null space of \( A \).

Can you remember their form? On the reverse there are two examples.


Two matrices in reduced row echelon form:

\[ R_1 = \begin{bmatrix}I && F \end{bmatrix} = \begin{bmatrix} 1 & 0 & 7 & 2 \\ 0 & 1 & 3 & 6 \\ \end{bmatrix} \]
\[ R_2 = \begin{bmatrix}I && F \end{bmatrix} = \begin{bmatrix} 1 & 0 & 9 & 5 \\ 0 & 1 & 8 & 2 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \]

Null space and reduced row echelon form

Consider the equation:

\[ Ax = 0 \]

By definition, the set of vectors that "solve" this equation, \( \{ x \in R^{n} : Ax = 0 \} \) are the null space of \( A \). The magic of this equation is that any row-operations (multiple of rows added to other rows) that transform \( A \) into some other matrix \( A' \) do not alter the null space. In other words, \( A \) and \( A' \) have the same null space. So \( A \) has the same null space as the reduced row echelon form of \( A \).

Reading the null space from a matrix in reduced row echelon form

Consider the matrix:

\[ A' = \begin{bmatrix}I && F \end{bmatrix} = \begin{bmatrix} 1 & 0 & 7 & 2 \\ 0 & 1 & 3 & 6 \\ \end{bmatrix} \]

We can see two convenient basis of the column space have been collected in the \( 0^{\text{th}} \) and \( 1^{\text{st}} \) columns. These vectors uniquely span the whole columns space of \( A' \). All other columns can be expressed in terms of these two vectors. The null space (the ratios of these vectors that add to zero) can be enumerate by following these steps:

  1. Choose one of the vectors that have not been designated as a basis (e.g. \( \begin{bmatrix}7 & 3\end{bmatrix}\) ).
  2. Find a combination of the basis, \( \begin{bmatrix}1 & 0\end{bmatrix} \) and \( \begin{bmatrix}0 & 1\end{bmatrix} \), that sum to \( \begin{bmatrix}7 & 3\end{bmatrix} \).
  3. Set the weighting for \( \begin{bmatrix}7 & 3\end{bmatrix} \) at 1, and set the weighting for the basis vectors to cancel this out (i.e. -1).
  4. Set 0 to be the weightings for all other columns.

Following these steps \( \begin{bmatrix} -7 & -3 & 1 & 0 \end{bmatrix} \) is one vector in the null space. The other is: \( \begin{bmatrix} -2 & -6 & 0 & 1 \end{bmatrix} \) .

These two vectors form a basis for the null space.