Row Reduction and Echelon Form

Donovan D Chang

26 Row Reduction and Echelon Form

Note that the strategy we used was the sequential elimination of variables to obtain the value of one variable, then plug in the identified value in the equations we have, and so on. Given any consistent set of equations, applying this elimination approach will lead us to the set of answers. However, as the size of the linear system increases with increased number of equations and variables, this elementary algebraic approach would become more prone to error and even inefficient.

Therefore, we developed an algorithm called row reduction, a variant of Gaussian elimination, to first reorganize the system into a triangular shape called echelon form, and then yield solutions in a reduced echelon form. Let us begin.

Definition. (Echelon and Reduced Echelon Matrix)
A rectangular matrix in echelon form has the following properties:

Non-zero rows always are placed above all-zero rows.
Leading entry of an upper row is on the left-side columns of the leading entry of a lower row.
All entries below the any leading entry are zeroes.

Reduced echelon form requires the following in addition:

The leading entry of non-zero rows is 1.
Every value in a given column is 0 except the leading entry 1 of non-zero rows.

Let us revisit the example.

Example. Find the echelon and reduced echelon matrix of the given linear system.
For $x,y\in \mathbb{R}$ ,

$\begin{align*} x+2y &=5\\ x-2y &=-3 \end{align*}$

The augmented matrix form of the linear system is

$\begin{align*} \left( \begin{array}{cc|c} 1 & 2 & 5 \\ 1 & -2 & -3 \end{array} \right) &\sim \left( \begin{array}{cc|c} 1 & 2 & 5 \\ 0 & -4 & -8 \end{array} \right)\\ &\sim \left( \begin{array}{cc|c} 1 & 2 & 5 \\ 0 & 1 & 2 \end{array} \right)\\ &\sim \left( \begin{array}{cc|c} 1 & 0 & 1 \\ 0 & 1 & 2 \end{array} \right) \end{align*}$

Since we have only 2 equations, with only one row operation we obtained an echelon form,

$\left( \begin{array}{cc|c} 1 & 2 & 5 \\ 0 & -4 & -8 \end{array} \right)$

The last matrix is in a reduced echelon form, where the values in the last column denote the solutions of the system,

$\left( \begin{array}{cc|c} 1 & 0 & 1 \\ 0 & 1 & 2 \end{array} \right)$

Inverse and Determinant

Given a matrix equation $A\vec{x}=\vec{b}$ , if $A$ is invertible, i.e. $A^{-1}$ exists, then we can easily obtain the solution $\vec{x}$ by $\vec{x}=A^{-1}\vec{b}$ .

Recall from elementary algebra, for $A^{-1}$ to be defined, $A$ is a $n\times n$ matrix and its determinant $|A|\neq 0$ . Here, we demonstrate the notion of determinant naturally arises during the course to obtain the inverse of a $2\times 2$ matrix $A=\begin{pmatrix} a & b\\ c & d \end{pmatrix}$ . Note that this algorithm is applicable to any $n\times n$ matrix.

$\begin{align*} \left(\begin{array}{c|c} A &I \end{array}\right) & = \left(\begin{array}{cc|cc} a & b & 1 & 0\\ c & d & 0 & 1 \end{array}\right)\\ &\sim \left(\begin{array}{cc|cc} ac & bc & c & 0\\ ac & ad & 0 & a \end{array}\right)\\ &\sim \left(\begin{array}{cc|cc} ac & bc & c & 0\\ 0 & ad-bc & -c & a \end{array}\right)\\ &\sim \left(\begin{array}{cc|cc} ac & bc & c & 0\\ 0 & 1 & \frac{-c}{ad-bc} & \frac{a}{ad-bc} \end{array}\right)\\ &\sim \left(\begin{array}{cc|cc} ac & 0 & \frac{acd}{ad-bc} & \frac{-abc}{ad-bc}\\ 0 & 1 & \frac{-c}{ad-bc} & \frac{a}{ad-bc} \end{array}\right)\\ &\sim \left(\begin{array}{cc|cc} 1 & 0 & \frac{d}{ad-bc} & \frac{-b}{ad-bc}\\ 0 & 1 & \frac{-c}{ad-bc} & \frac{a}{ad-bc} \end{array}\right) &&= \left(\begin{array}{c|c} I &A^{-1} \end{array}\right) \end{align*}$

Therefore, given $det(A)=ad-bc\neq 0$ ,

$A^{-1} = \frac{1}{ad-bc}\begin{pmatrix} d & -b\\ -c & a \end{pmatrix}$

26 Row Reduction and Echelon Form

License

Share This Book