%display latex
latex.matrix_delimiters(left='[', right=']')
latex.matrix_column_alignment('c')

$\newcommand{\la}{\langle}$ $\newcommand{\ra}{\rangle}$ $\newcommand{\vu}{\mathbf{u}}$ $\newcommand{\vv}{\mathbf{v}}$ $\newcommand{\vw}{\mathbf{w}}$ $\newcommand{\vzz}{\mathbf{z}}$ $\newcommand{\nc}{\newcommand}$ $\nc{\Cc}{\mathbb{C}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\cB}{\mathcal{B}}$ $\nc{\cE}{\mathcal{E}}$ $\nc{\cC}{\mathcal{C}}$ $\nc{\cD}{\mathcal{D}}$ $\nc{\mi}{\mathbf{i}}$ $\nc{\span}[1]{\langle #1 \rangle}$ $\nc{\ol}[1]{\overline{#1} }$ $\nc{\norm}[1]{\left\| #1 \right\|}$ $\nc{\abs}[1]{\left| #1 \right|}$ $\nc{\vz}{\mathbf{0}}$ $\nc{\vo}{\mathbf{1}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\tr}{tr}$ $\DMO{\nullsp}{nullsp}$ $\nc{\va}{\mathbf{a}}$ $\nc{\vb}{\mathbf{b}}$ $\nc{\vx}{\mathbf{x}}$ $\nc{\ve}{\mathbf{e}}$ $\nc{\vd}{\mathbf{d}}$ $\nc{\vh}{\mathbf{h}}$ $\nc{\ds}{\displaystyle}$ $\nc{\bm}[1]{\begin{bmatrix} #1 \end{bmatrix}}$ $\nc{\gm}[2]{\bm{\mid & \cdots & \mid \\ #1 & \cdots & #2 \\ \mid & \cdots & \mid}}$ $\nc{\MN}{M_{m \times n}(K)}$ $\nc{\NM}{M_{n \times m}(K)}$ $\nc{\NP}{M_{n \times p}(K)}$ $\nc{\MP}{M_{m \times p}(K)}$ $\nc{\PN}{M_{p \times n}(K)}$ $\nc{\NN}{M_n(K)}$ $\nc{\im}{\mathrm{Im\ }}$ $\nc{\ev}{\mathrm{ev}}$ $\nc{\Hom}{\mathrm{Hom}}$ $\nc{\com}[1]{[\phantom{a}]^{#1}}$ $\nc{\rBD}[1]{ [#1]_{\cB}^{\cD}}$ $\DMO{\id}{id}$ $\DMO{\rk}{rk}$ $\DMO{\nullity}{nullity}$ $\DMO{\End}{End}$ $\DMO{\proj}{proj}$ $\nc{\GL}{\mathrm{GL}}$

Row Equivalence

We now make precise that special form of a linear system from which we read-off (a parametrization of) its solution set.

First, we introduce a few new terms.

The pivot of a nonzero row of a matrix is its first (i.e. "leftmost") nonzero entry.

A matrix is in row echelon form (or is a row echelon matrix) if the pivot of the previous row is strictly to the left of the pivot, if any, of the current row.

A matrix is in reduced row echelon form (or is a reduced row echleon matrix) if

1. It is in row echelon form
2. All its pivots are 1; and
3. A pivot is the only nonzero entry of its column.

A pivotal column of a row echelon matrix is a column that contains the pivot of a row.

Example.

The matrix $\bm{1 & * & * & * & * \\ 0 & 0 & -2 & * & * \\ 0 & 0 & 0 & 1 & *}$ where each $*$ represents an arbitrary entry, is in row echelon (but not reduced echelon) form. The 1st, 3rd and 4th columns are pivotal.

The matrix $\bm{1 & 0 & * & 0 & * \\ 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 1 & *}$ is in reduced row echelon form. The 1st, 2nd and 4th columns are pivotal.

As we have seen, a system whose agumented matrix is in rref is solved. But in general, how can we solve a system?

Elementary Row Operations

You probably know how to solve a simple linear system, like $$ \begin{align*} -2x - y & = 1 \\ 3x + 2y & = -2 \end{align*} $$

If you examine how you solve it, you will realize that it involves only a couple of operations, like swapping two equations, multiplying an equation by a number (scalar) and adding a multiple of an equation to another.

The "legitmacy" of these operations come to the fact that none of them changes the solution set.

In the language of matrix, these operations become what known as the elementary row operations (EROs). They are

1. swapping two rows. ($R_i \leftrightarrow R_j$)
2. multiplying a row by a non-zero scalar. ($R_i \rightarrow cR_i$, $c \neq 0$)
3. adding a multiple of a row to another. ($cR_i+R_j \rightarrow R_j$)

Checkpoint. Check that EROs do not change the solution sets.

Each ERO is reversible.

$$\rho$$	$$\rho^{-1}$$
$$R_i \leftrightarrow R_j$$	$$R_i \leftrightarrow R_j$$
$$R_i \rightarrow cR_i$$	$$R_i \rightarrow \dfrac{1}{c}R_i$$
$$cR_i + R_j \rightarrow R_j$$	$$-cR_i + R_j \rightarrow R_j$$

We say that two matrices (of the same shape) are row equivalent if one can be obtained from the other by a finite sequence of EROs.

Checkpoint. Check that row equivalence is an equivalence relation on $M_{m \times n}(K)$.

Since EROs, when applied to the augmented matrix, do not change the solution set of the corresponding linear system, it follows immediately that

Proposition. Two linear systems with row equivalent augmented matrices have the same set of solutions. In particular, two equivalent matrices have the same nullspace.

Later, we will see that the converse of the second statement is also true; that is, two matrices with the same nullspace are row equivalent.

EROs are sufficient for the purpose of solving systems of linear equations because of the following theorem.

Fundamental Theorem of Linear Algebra

Every matrix is row equivalent to a unique reduced row echelon matrix.

And we have an efficient algorithm--Gauss Jordan Elimination--for computing the rref of a given matrix. But first let us see what information about a linear system that can be extracted from the rref of its augmented matrix.

Solving linear systems from rref of its augmented matrix

Consider the following system of linear equations $$ \begin{align*} x_2 -2x_3 - x_4 &= -2 \\ -x_1 -2x_2 +2x_3 -x_4 &=1 \\ x_2 -4x_3 +2x_4 &= -4 \end{align*} \tag{1} $$ with augemented matrix:

%display latex 

A = matrix(QQ,[[0,1,-2,-1],[-1,-2,2,-1],[0,1,-4,2]])
b = column_matrix(QQ,[-2,1,-4])
Ab = block_matrix([A,b],ncols =2);
R = Ab.rref(); Ab, R #the augmented matrix and its rref

$$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left[\begin{array}{cccc|c} 0 & 1 & -2 & -1 & -2 \\ -1 & -2 & 2 & -1 & 1 \\ 0 & 1 & -4 & 2 & -4 \end{array}\right], \left[\begin{array}{cccc|c} 1 & 0 & 0 & 6 & 1 \\ 0 & 1 & 0 & -4 & 0 \\ 0 & 0 & 1 & -\frac{3}{2} & 1 \end{array}\right]\right)$$

Here are two more jargons: A pivotal variable of a linear system is a variable whose corresponding column is a pivot column of the rref of the system's augmented matrix. A free variable of the system is a variable that is not pivotal.

For System (1), $x_4$ is the only free variable and we rename it to $s_1$. Expressing the pivotal variables $x_1,x_2,x_3$ in terms of the free variable $s_1$, we get the following description of the solutions $$ \bm{x_1 \\ x_2 \\ x_3 \\ x_4} = \bm{1 \\ 0 \\ 1 \\ 0} + s_1 \bm{-6 \\ 4\\ 3/2 \\ 1} \qquad s_1 \in K. $$

Checkpoint Solve the following system $$ \begin{align*} -x_2 + 2x_3 &=1 \\ 2x_1 -2x_2 +x_3&=-1 \\ -x_1 + x_3&=1 \end{align*} \tag{2} $$

Checkpoint Solve the following system $$ \begin{align*} x_1 -2x_3 + x_4 &= 1 \\ 3x_1 +x_2 -4x_3+ 4x_4 &= 2 \\ x_2 + 2x_3 + x_4 &=0 \end{align*} \tag{3} $$

The end this discussion with a very important observation.

Corollary (of the FTLA)

Every homogenous system of linear equations with more unknowns than equations must have a non-trivial solution.

Proof. The number of pivotal columns is at most the number of equations. So, such a system must have a free variable and hence a non-trivial solution.