Skip to main content

Linear Algebra with SageMath: A Gentle Introduction

Ajit Kumar

Section 1.3 Echelon Forms

In this section we define the row echelon form of matrices its useful to deal with various concepts related to matrices. We shall see how Sage can be used to convert any matrix to its row-echelon form.

Subsection 1.3.1 Row Echelon Form

Definition 1.3.1.

An \(m \times n\) matrix \(A\) is said to be in row-echelon form or row-echelon matrix if it satisfies the following conditions:
  1. All zero rows (consisting entirely of zeros) are at the bottom.
  2. The first nonzero entry from the left in each nonzero row is a 1, called the leading 1 or pivot element for that row. Row containing pivot elements are called the pivot row and the columns containing the pivot element are called the pivot columns.
  3. Each leading 1 is to the right of all leading 1s in the rows above it.
  4. Each leading 1 is the only nonzero entry in its column.

Example 1.3.2. Echelon Matrices.

Following are examples of echelon matrices:
\begin{equation*} \begin{pmatrix} 1 \amp 2 \amp 4 \\ 0 \amp 1 \amp -5 \\ 0 \amp 0 \amp 0 \end{pmatrix}, \begin{pmatrix} 1\amp 3 \amp 6 \amp 8 \amp 0 \\ 0\amp 0 \amp 1 \amp 9 \amp 1 \\ 0\amp 0 \amp 0 \amp 1 \amp -1 \\ \end{pmatrix}, \begin{pmatrix} 1\amp 0 \amp 3 \amp 4 \\ 0\amp 1 \amp 2 \amp 1 \\ 0\amp 0 \amp 1 \amp 4 \\ 0 \amp 0 \amp 0 \amp 1 \end{pmatrix}\text{.} \end{equation*}

Example 1.3.3. Non Echelon Matrices.

Following are examples of some non echelon matrices:
\begin{equation*} \begin{pmatrix} 1\amp 3 \amp 6 \amp 8 \amp 0 \\ 0\amp 0 \amp 1 \amp 9 \amp 1 \\ 0\amp 1 \amp 0 \amp 1 \amp -1 \\ \end{pmatrix} , \quad \begin{pmatrix} 0\amp 1 \amp 6 \amp 8 \amp 0 \\ 0\amp 1 \amp 1 \amp 9 \amp 1 \\ 0\amp 1 \amp 0 \amp 1 \amp -1 \\ \end{pmatrix} , \quad \begin{pmatrix} 1 \amp 6 \amp 8 \amp 0 \\ 0 \amp 5 \amp 9 \amp 1 \\ 0 \amp 0 \amp 1 \amp -1 \\ \end{pmatrix}\text{.} \end{equation*}
Every nonzero \(m \times n\) matrix \(A\) is row equivalent to a matrix which is a row echelon matrix. We employ the following procedures to convert a matrix into a row echelon form:
  1. Choose a pivot element from the nonzero entries in the 1st column. Row containing pivot is called the pivot row.
  2. Interchange rows (if necessary) so that pivot row is the new 1st row.
  3. Multiply pivot row by a constant so that the new pivot is 1.
  4. Make all subsequent entries in the 1st column 0 by using elementary row operations.
  5. Repeat this process with next column.

Example 1.3.4.

Reduce the matrix \(A=\begin{pmatrix}1\amp 2 \amp 4 \\ 1\amp 0 \amp 2 \\ 2\amp 4 \amp 1 \end{pmatrix}\) to row echelon form.
Solution.
\(\begin{pmatrix} 1\amp 2 \amp 4 \\ 1\amp 0 \amp 2 \\ 2\amp 4 \amp 1 \\ \end{pmatrix} \xrightarrow{ \begin{array}{c} R_2\to R_2-R_1 \\ R_3\to R_3-2R_1 \\ \end{array}} \begin{pmatrix} 1\amp 2 \amp 4 \amp \\ 0\amp -2 \amp -2 \amp \\ 0\amp 0 \amp -7 \amp \\ \end{pmatrix} \xrightarrow{\begin{array}{c} R_1\to\frac{-1}{7}R_1 \\ R_2\to\frac{-1}{2}R_2 \\ \end{array}} \begin{pmatrix} 1\amp 2 \amp 4 \\ 0\amp 1 \amp 1 \\ 0\amp 0 \amp 1 \end{pmatrix}\) This \(\begin{pmatrix} 1\amp 2 \amp 4 \\ 0\amp 1 \amp 1 \\ 0\amp 0 \amp 1 \end{pmatrix}\) is row-echelon matrix equivalent to \(A\) . We can apply elementary row operation and make it to reduced-row-echelon form.
\begin{equation*} \begin{pmatrix} 1\amp 2 \amp 4 \\ 0\amp 1 \amp 1 \\ 0\amp 0 \amp 1 \end{pmatrix}\xrightarrow{ \begin{array}{c} R_2\to R_2-R_3 \\R_1\to R_1-4R_3\\R_1\to R_1-2R_2\\ \end{array}} \begin{pmatrix} 1\amp 0 \amp 0 \\ 0\amp 1 \amp 0 \\ 0\amp 0 \amp 1 \end{pmatrix} \end{equation*}
Sage has inbulit method `A.rref()’ to convert the matrix into reduced row echelon form. You may also try ’A.echelonize()’ and ’A.echelon_form()’
Step by Step method to find RREF of a matrix

Subsection 1.3.2 Gaussian Elimination Method

Solving a system of linear equations \(AX = B\text{,}\) by reducing the augmented matrix \(A^*= [A,B]\) to echelon form by using elementary row operations and then solving the equivalent system by back substitution is called solving by Gaussian elimination process. Now we state the step involved in the Gaussian elimination process. Only use the row operations stated above and work from top to bottom.

Example 1.3.6.

Solve the following system of linear equations using the Gaussian elimination method.
\begin{align*} x+2y+4z \amp = 3 \\ x+2z \amp = 0 \\ 2x+4y+z \amp = 3 \end{align*}
Solution.
The corresponding augmented matrix is
\begin{equation*} A^* = [A~|~B]= \begin{pmatrix} 1\amp 2 \amp 4 \amp | \amp 3 \\ 1\amp 0 \amp 2 \amp | \amp 0 \\ 2\amp 4 \amp 1 \amp | \amp 3 \\ \end{pmatrix} \end{equation*}
\begin{align*} \begin{pmatrix} 1\amp 2 \amp 4 \amp | \amp 3 \\ 1\amp 0 \amp 2 \amp | \amp 0 \\ 2\amp 4 \amp 1 \amp | \amp 3 \\ \end{pmatrix} \amp \xrightarrow{ \begin{array}{c} R_2-R_1 \\ R_3-2R_1 \\ \end{array}} \begin{pmatrix} 1\amp 2 \amp 4 \amp | \amp 3 \\ 0\amp -2 \amp -2 \amp | \amp -3 \\ 0\amp 0 \amp -7 \amp | \amp -3 \\ \end{pmatrix} \\ \amp \xrightarrow{ \begin{array}{c} \frac{-1}{7}R_1 \\ \frac{-1}{2}R_2 \\ \end{array}} \begin{pmatrix} 1\amp 2 \amp 4 \amp | \amp 3 \\ 0\amp 1 \amp 1 \amp | \amp 3/2 \\ 0\amp 0 \amp 1 \amp | \amp 3/7 \\ \end{pmatrix} \end{align*}
We can do more step of row elimination to convert the first three columns into identity matrix. However, the above augmented matrix represents the following equations:
\begin{equation*} x+2y+4z=3;\quad y+z=3/2;\quad z=3/7. \end{equation*}
Using back substitution, we get
\begin{equation*} x=-6/7, y=15/14, z=3/7\text{.} \end{equation*}

Example 1.3.7.

Solve the following system of linear equations.
\begin{align*} x+y+z-w \amp = 1 \\ y-z+w \amp = -1 \\ 3x+6z-6w \amp = 6 \\ -y+z-w \amp = 1 \end{align*}
using Gaussian elimination method. Show that this system has infinitely many solutions.
Solution.
Since last row zero, it represents the equation \(0=0\text{,}\) in particular, one can eliminate one of the variables. Hence the system has infinitely many solutions.

Example 1.3.8.

Solve the following system using the Gaussian elimination method and show that it has no solution.
\begin{align*} x+3y \amp = 1 \\ 2x+y \amp = -3 \\ 2x+2y \amp = 0 \end{align*}
Solution.
Since last row represents the equation \(0=1\text{,}\) the system has no solution.

Subsection 1.3.3 Gauss-Jordan elimination method

Guass-Jordan method of solving the linear system \(AX=B\) is very similar to that of the Gaussian elimination method. In this method we continue the the row elimination till we reduce the row-reduced matrix of \(A\) to identity matrix.

Example 1.3.9.

Solve the system \(Ax=b\) using the Gauss-Jordan elimination method, where
\begin{equation*} A= \begin{pmatrix} 1\amp 0\amp 5\amp 0\\-1\amp 4\amp 1\amp 0\\3\amp 0\amp 4\amp 1\\-2\amp 1\amp 1\amp 3 \end{pmatrix} \text{ and } b=\begin{pmatrix}1\\4\\3\\5\end{pmatrix} \end{equation*}
Solution.
Let us solve this in Sage.
Clearly the solution of the above system is
\begin{equation*} x_1=11/34, x_2 = 89/85, x_3 = 23/170, x_4=253/170\text{.} \end{equation*}
We can also solve the above system using the ’A.solve_right(b)’ command in Sage.
PrevTopNext