Introduction to Linear Systems

Contents

Introduction to Linear Systems #

Table of Contents #

Definition Linear Equation #

An equation which can be written in the form

\(a_1x_1 + a_2x_2 + \dots + a_nx_n = b\)

for given numbers \(a_1, a_2, \dots, a_n, b\) and unknown variables \(x_1, x_2, \dots, x_n\) is called linear.

(The numbers \(a_1, a_2, \dots, a_n\) are called coefficients.)

Example #

The following equations are linear.

\( \begin{aligned} 6x_1 - 3x_2 + 4 = x_1 && \iff && 5x_1 && - && 3x_2 && && && = && -4 \\ x_2 = 3(\sqrt{5} - x_1) + 2x_3 && \iff && -3x_1 && - && x_2 && + && 2x_3 && = && 3\sqrt{5} \\ \end {aligned} \)

The following equations are non linear.

\( \begin{aligned} 5x_1 + x_2 = 6x_1x_2 && \iff && 5x_1 && + && x_2 && - && \textcolor{red}{6x_1x_2} && = && 0 \\ 3x_2 = 4\sqrt{x_1} - 5 && \iff && \textcolor{red}{4\sqrt{x_1}} && - && 3x_2 && && && = && 5 \\ \end {aligned} \)

Definition Linear System #

A system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.

Example#

\( \begin{aligned} 2x_1 && - && x_2 && + && \frac{3}{2} x_3 && = && 8 \\ x_1 && - && && && 4x_3 && = && -7 \\ 5x_1 && + && 2x_2 && + && x_3 && = && 11 \\ \end {aligned} \)

Definition - Solution Set of a linear system #

Solution to a Linear System

A solution to a linear system is a collection of numerical values that when substituted for the variables of the system make each equation true.

Example#

\((-3, -12.5, 1)\) is a solution to the following linear system

\( \begin{aligned} 2x_1 - x_2 + 1.5x_3 &= 8 \\ x_1 - 4x_3 &= -7 \\ \end {aligned} \)

because the following equations are true.

\( \begin{aligned} 2(-3) - (-12.5) + 1.5(1) &= 8 \\ (-3) - 4(1) &= -7 \\ \end {aligned} \)

Solution Set of a Linear System

The solution set of a linear system is the set of all possible solutions of that system.

How many solutions does the linear system have?

\( \begin{aligned} x_1 - 2x_2 &= -1 &\iff x_2 = \frac{1}{2}x_1 + \frac{1}{2} \\ -x_1 + 2x_2 &= 3 &\iff x_2 = \frac{1}{2}x_1 + \frac{3}{2} \\ \end {aligned} \)

No solution.

How many solutions does the linear system have?

\( \begin{aligned} x_1 - 2x_2 &= -1 &\iff x_2 = \frac{1}{2}x_1 + \frac{1}{2} \\ -x_1 + 3x_2 &= 3 &\iff x_2 = \frac{1}{3}x_1 + 1 \\ \end {aligned} \)

One solution.

How many solutions does the linear system have?

\( \begin{aligned} x_1 - 2x_2 &= -1 &\iff x_2 = \frac{1}{2}x_1 + \frac{1}{2} \\ -x_1 + 2x_2 &= 1 &\iff x_2 = \frac{1}{2}x_1 + \frac{1}{2} \\ \end {aligned} \)

Infinitely many solutions.

How many solutions does the linear system have?

\( \begin{aligned} 1x + 0y + 0z = 2 \\ 0x + 1y + 0z = 3 \\ 0x + 0y + 1z = 5 \\ \end {aligned} \)

One solution, the point \((2, 3, 5)\).

How many solutions does the linear system have?

\( \begin{aligned} 1x + 0y - 1z = 0 \\ 0x - 1y + 1z = 0 \\ -1x + 1y + 0z = 0 \\ \end {aligned} \)

Infinitely many solutions, points of the form \((t, t, t)\).

How many solutions does the linear system have?

\( \begin{aligned} 1x + 0y - 1z = 2 \\ 0x - 1y + 1z = 3 \\ -1x + 1y + 0z = 5 \\ \end {aligned} \)

No solution.

Definition - Consistency of a linear system #

Consistency of a Linear System

Consider a linear system. One of the following holds:

1. The system has no solution.

2. The system has exactly one solution.

3. The system has infinitely many solutions.

If a linear system admits at least one solution then it is said to be consistent.

If a linear system admits no solution then it is said to be inconsistent.

Definition - Matrix, Coefficient Matrix, Augmented Matrix #

Matrix, Coefficient and Augmented

A matrix is a rectangular array of numbers.

An \(m \times n\) matrix contains \(m\) rows and \(n\) columns.

Matrices can be used to record the essential information of a linear system.

For example, to the linear system

\( \begin{aligned} x_1 && - && 2x_2 && + && x_3 && = && 0 \\ && && x_2 && - && 8x_3 && = && 8 \\ -4x_1 && + && 5x_2 && + && 9x_3 && = && -9 \\ \end {aligned} \)

we associate the coefficient matrix

\( \begin{bmatrix*}[r] 1 & -2 & 1 \\ 0 & 1 & -8 \\ -4 & 5 & 9 \\ \end {bmatrix*} \)

and the augmented matrix

\( \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 1 & -8 \\ -4 & 5 & 9 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 8 \\ -9 \\ \end {matrix*} \right. \right] \)

Definition - Equivalence of linear systems #

Equivalence of Linear Systems

Two linear systems are equivalent if they have exactly the same solution set: every solution of the first system is a solution of the seconds system and every solution of the second system is a solution of the first system.

Given a linear system, one can produce an equivalent linear system by performing an elementary operation on the equations of the system–or equivalently by performing an elementary operation on the rows of the augmented matrix representing the system.

Definition - Elementary Row Operations #

Elementary Operations on the Rows of a Matrix

There are three elementary row operations (or elementary operations on the rows of a matrix).

1. We can replace one row of the matrix by the sum of itself and a multiple of another row.

2. We can interchange two rows of the matrix.

3. We can rescale a row by multiplying all its entries by a nonzero constant

To solve a linear system, we perform elementary row operations on the augmented matrix representing the system.

Procedure - Solving linear systems #

Solving a Linear System

STEP 1 - Write down the augmented matrix of the system.

STEP 2 - Apply a carefully chosen sequence of elementary row operations so as to obtain an upper triangular matrix (more precisely, a row echelon matrix) with all rows having a one as their first nonzero entry.

\( \left[ \begin{matrix*}[r] 1 & * & * \\ 0 & 1 & * \\ 0 & 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] * \\ * \\ * \\ \end {matrix*} \right. \right] \)

STEP 3 - Apply a carefully chosen sequence of elementary row operations to the matrix resulting from Step 2 so as to obtain zeros above the leading ones.

\( \left[ \begin{matrix*}[r] \textcolor{blue}{1} & \textcolor{red}{0} & \textcolor{red}{0} \\ 0 & \textcolor{blue}{1} & \textcolor{red}{0} \\ 0 & 0 & \textcolor{blue}{1} \\ \end {matrix*} \left| \begin{matrix*}[r] * \\ * \\ * \\ \end {matrix*} \right. \right] \)

STEP 4 - Rewrite the matrix resulting from Step 3 as a linear system. This system has the same solutions set as the original system and its solutions are very easy to read off.

Definition - Row Equivalence of matrices #

Row Equivalence of Matrices

Two matrices are said to be row equivalent if there exists a sequence of elementary row operations transforming one matrix into the other.

If the augmented matrices representing two linear systems are row equivalent (derived from one another via elementary row operations) then these two linear systems have exactly the same solution set (and are thus equivalent).

Two augmented matrices which are row equivalent represent two equivalent linear systems (two linear systems with the same solutions set).

augmented matrices \(A, B\) are row equivalent \(\implies\) linear systems \(A, B\) are equivalent

Definition - Determine whether a linear system is consistent #

Determining whether a linear system is consistent

STEP 1 - Write down the augmented matrix representing the linear system.

STEP 2 - Apply a carefully chosen sequence of elementary row operations so as to obtain a ROW ECHELON MATRIX: in each row, the leftmost nonzero entry is located in a column to the right of the leftmost nonzero entry of the row above it. (In the following schematic, a \(*\) represents any number and a \(\blacksquare\) represents any nonzero number.)

\( \left[ \begin{matrix*}[r] \blacksquare & * & * & * & * & * & * & * & * \\ 0 & 0 & 0 & \blacksquare & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & \blacksquare & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \blacksquare & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end {matrix*} \left| \begin{matrix*}[r] * \\ * \\ * \\ * \\ 0 \\ \end {matrix*} \right. \right] \)

If in the resulting row echelon matrix a row has its leading (leftmost) nonzero coefficient in the last (rightmost) column then the linear system is inconsistent.

\( \left[ \begin{matrix*}[r] \textcolor{blue}{1} & * & * \\ 0 & 0 & \textcolor{blue}{5} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end {matrix*} \left| \begin{matrix*}[r] * \\ * \\ \textcolor{red}{2} \\ 0 \\ \end {matrix*} \right. \right] \)

If in the resulting row echelon matrix no row has its leading (leftmost) nonzero coefficient in the last (rightmost) column then the linear system is consistent.

\( \left[ \begin{matrix*}[r] \textcolor{blue}{6} & * & * \\ 0 & 0 & \textcolor{blue}{4} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end {matrix*} \left| \begin{matrix*}[r] * \\ * \\ 0 \\ 0 \\ \end {matrix*} \right. \right] \)

Example#

Use elementary row operations to solve the system. Check the solution by substituting it back into the original system.

\( \begin{aligned} x_1 && - && 2x_2 && + && x_3 && = && 0 \\ && && 2x_2 && - && 8x_3 && = && 8 \\ -4x_1 && + && 5x_2 && + && 9x_3 && = && -9 \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 2 & -8 \\ -4 & 5 & 9 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 8 \\ -9 \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow \frac{1}{2} r_2}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 1 & -4 \\ -4 & 5 & 9 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 4 \\ -9 \\ \end {matrix*} \right. \right] \underset{r_3 \leftarrow r_3 + 4r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 1 & -4 \\ 0 & -3 & 13 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 4 \\ -9 \\ \end {matrix*} \right. \right] \underset{r_3 \leftarrow r_3 + 3r_2}{\rightarrow} \left[ \begin{matrix*}[r] \textcolor{blue}{1} & -2 & 1 \\ 0 & \textcolor{blue}{1} & -4 \\ 0 & 0 & \textcolor{blue}{1} \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 4 \\ 3 \\ \end {matrix*} \right. \right] \)

The system is consistent since the last column of the row echelon matrix contains no leading nonzero coefficient.

\( \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 1 & -4 \\ 0 & 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 4 \\ 3 \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow r_2 + 4r_3}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 16 \\ 3 \\ \end {matrix*} \right. \right] \underset{r_1 \leftarrow r_1 - r_3}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] -3 \\ 16 \\ 3 \\ \end {matrix*} \right. \right] \underset{r_1 \leftarrow r_1 + 2r_2}{\rightarrow} \left[ \begin{matrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] 29 \\ 16 \\ 3 \\ \end {matrix*} \right. \right] \)

\( \begin{aligned} (29) && - && 2(16) && + && (3) && = && 0 \\ && && 2(16) && - && 8(3) && = && 8 \\ -4(29) && + && 5(16) && + && 9(3) && = && -9 \\ \end {aligned} \)

The solution set to this linear system is \(\{(29, 16, 3)\}\).

Example#

Determine whether the linear system is consistent or not.

\( \begin{aligned} && && x_2 && - && 4x_3 && = && 8 \\ 2x_1 && - && 3x_2 && + && 2x_3 && = && 1 \\ 5x_1 && - && 8x_2 && + && 7x_3 && = && 1 \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] 0 & 1 & -4 \\ 2 & -3 & 2 \\ 5 & -8 & 7 \\ \end {matrix*} \left| \begin{matrix*}[r] 8 \\ 1 \\ 1 \\ \end {matrix*} \right. \right] \underset{r_1 \leftrightarrow r_3}{\rightarrow} \left[ \begin{matrix*}[r] 5 & -8 & 7 \\ 2 & -3 & 2 \\ 0 & 1 & -4 \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ 1 \\ 8 \\ \end {matrix*} \right. \right] \underset{r_1 \leftarrow r_1 + (-2)r_2}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 3 \\ 2 & -3 & 2 \\ 0 & 1 & -4 \\ \end {matrix*} \left| \begin{matrix*}[r] -1 \\ 1 \\ 8 \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow r_2 + (-2)r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -2 & 3 \\ 0 & 1 & -4 \\ 0 & 1 & -4 \\ \end {matrix*} \left| \begin{matrix*}[r] -1 \\ 3 \\ 8 \\ \end {matrix*} \right. \right] \underset{r_3 \leftarrow r_3 + (-1)r_2}{\rightarrow} \left[ \begin{matrix*}[r] \textcolor{blue}{1} & -2 & 3 \\ 0 & \textcolor{blue}{1} & -4 \\ 0 & 0 & 0 \\ \end {matrix*} \left| \begin{matrix*}[r] -1 \\ 3 \\ \textcolor{red}{5} \\ \end {matrix*} \right. \right] \)

The system is inconsistent since the last column of the row echelon matrix contains at least one leading nonzero coefficient.

\( \begin{aligned} x_1 && - && 2x_2 && + && 3x_3 && = && -1 \\ && && x_2 && - && 4x_3 && = && 3 \\ && && && && 0 && = && 5 \\ \end {aligned} \)

The last equation is not true no matter which values are plugged in for \(x_1, x_2, x_3\). Therefore, the system has no solution.

Example#

For what value of parameter \(h\) is the linear system consistent?

\( \begin{aligned} 3x_1 && - && 9x_2 && = && 4 \\ -2x_1 && + && 6x_2 && = && h \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] 3 & -9 \\ -2 & 6 \\ \end {matrix*} \left| \begin{matrix*}[r] 4 \\ h \\ \end {matrix*} \right. \right] \underset{r_1 \leftarrow \frac{1}{3} r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -3 \\ -2 & 6 \\ \end {matrix*} \left| \begin{matrix*}[r] \frac{4}{3} \\ h \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow r_2 + 2r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -3 \\ 0 & 0 \\ \end {matrix*} \left| \begin{matrix*}[r] \frac{4}{3} \\ h + \frac{8}{3} \\ \end {matrix*} \right. \right] \)

If \(h + \frac{8}{3} = 0 \iff h = -\frac{8}{3}\) then the last column contains no leading nonzero coefficient and so the linear system is consistent.

If \(h + \frac{8}{3} \ne 0 \iff h \ne -\frac{8}{3}\) then the last column contains at least one leading nonzero coefficient and so the linear system is inconsistent.

Example#

Find the point of intersection of the lines \(x_1 - x_2 = 1\) and \(x_1 + 2x_2 = 4\).

\( \begin{aligned} x_1 && - && x_2 && = && 1 \\ x_1 && + && 2x_2 && = && 4 \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] 1 & -1 \\ 1 & 2 \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ 4 \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow r_2 + (-1)r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -1 \\ 0 & 3 \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ 3 \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow \frac{1}{3} r_2}{\rightarrow} \underbrace{ \left[ \begin{matrix*}[r] \textcolor{#0096FF}{1} & -1 \\ 0 & \textcolor{#0096FF}{1} \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ 1 \\ \end {matrix*} \right. \right] }_{\textcolor{#0096FF}{\textbf{consistent}}} \underset{r_1 \leftarrow r_1 + r_2}{\rightarrow} \left[ \begin{matrix*}[r] 1 & 0 \\ 0 & 1 \\ \end {matrix*} \left| \begin{matrix*}[r] 2 \\ 1 \\ \end {matrix*} \right. \right] \)

\( \begin{aligned} (2) && - && (1) && = && 1 \\ (2) && + && 2(1) && = && 4 \\ \end {aligned} \)

The solution set of the linear system is \(\{(2, 1)\}\).

The two lines intersect at the point \((2, 1)\).

Definition - Row Echelon Matrix #

DEFINITION - Row Echelon Matrix

A zero row of a matrix is a row whose entries are all zero.

A nonzero row of a matrix is a row that contains at least one nonzero entry.

The leading entry of a (nonzero) row is the leftmost nonzero entry in that row.

A row echelon matrix is a matrix possessing the following two properties: (1) the nonzero rows are located above the zero rows, and (2) in each row, the leading entry is located in a column to the right of the leading entry of the row above it.

\( \left[ \begin{matrix*}[r] \blacksquare & * & * & * & * \\ 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {matrix*} \right] \)

\( \left[ \begin{matrix*}[r] \blacksquare & * & * & * & * & * & * & * & * & * \\ 0 & 0 & 0 & \blacksquare & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \blacksquare & * & * \\ \end {matrix*} \right] \)

Definition - Reduced Row Echelon Matrix #

DEFINITION - Reduced Row Echelon Matrix

A reduced row echelon matrix is a row echelon matrix possessing the following two additional properties: (1) in each nonzero row the leading entry is a \(1\) and (2) each leading \(1\) is the only nonzero entry in its column.

\( \left[ \begin{matrix*}[r] 1 & 0 & * \\ 0 & 1 & * \\ 0 & 0 & 0 \\ \end {matrix*} \right] \)

\( \left[ \begin{matrix*}[r] 0 & 1 & * & 0 & 0 & * & * & 0 & 0 & * \\ 0 & 0 & 0 & 1 & 0 & * & * & 0 & 0 & * \\ 0 & 0 & 0 & 0 & 1 & * & * & 0 & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & * \\ \end {matrix*} \right] \)

Theorem #

THEOREM

Each matrix is row equivalent to one and only one reduced row echelon matrix.

Each (nonzero) matrix is row equivalent to several different row echelon matrices (a matrix whose entries are all zero is not row equivalent to any other matrix).

If two row echelon matrices are row equivalent then their leading entries occupy exactly the same positions in both matrices.

Definition - Pivot Position #

DEFINITION - Pivots

The pivot positions of a matrix are the positions occupied by the leading entries of the associated reduced row echelon matrix.

A pivot column is a column containing a pivot position.

Example#

Find the pivot positions and pivot columns of the following matrix.

\( \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 2 & 4 & 5 & 4 \\ 4 & 5 & 4 & 2 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + (-2)r_1}{\rightarrow} \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & 0 & -3 & -6 \\ 4 & 5 & 4 & 2 \\ \end {bmatrix*} \underset{r_2 \leftarrow (-\frac{1}{3})r_2}{\rightarrow} \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & 0 & 1 & 2 \\ 4 & 5 & 4 & 2 \\ \end {bmatrix*} \underset{r_2 \leftrightarrow r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 4 & 5 & 4 & 2 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + (-4)r_1}{\rightarrow} \underbrace{ \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & -3 & -12 & -18 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} }_{\textbf{row echelon}} \underset{r_2 \leftarrow (-\frac{1}{3})r_2}{\rightarrow} \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & 1 & 4 & 6 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} \)

\( \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & 1 & 4 & 6 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + (-4)r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 2 & 4 & 5 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + (-2)r_2}{\rightarrow} \begin{bmatrix*}[r] 1 & 0 & 4 & 9 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + (-4)r_3}{\rightarrow} \underbrace{ \begin{bmatrix*}[r] \boxed{1} & 0 & 0 & 1 \\ 0 & \boxed{1} & 0 & -2 \\ 0 & 0 & \boxed{1} & 2 \\ \end {bmatrix*} }_{\textbf{reduced}} \)

Example#

Find the pivot positions and pivot columns of the following matrix.

\( \begin{bmatrix*}[r] 0 & -3 & -6 & 4 & 9 \\ -1 & -2 & -1 & 3 & 1 \\ -2 & -3 & 0 & 3 & -1 \\ 1 & 4 & 5 & -9 & -7 \\ \end {bmatrix*} \underset{r_1 \leftrightarrow r_4}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ -1 & -2 & -1 & 3 & 1 \\ -2 & -3 & 0 & 3 & -1 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + r_1}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 2 & 4 & -6 & -6 \\ -2 & -3 & 0 & 3 & -1 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_2 \leftarrow \frac{1}{2} r_2}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ -2 & -3 & 0 & 3 & -1 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \)

\( \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ -2 & -3 & 0 & 3 & -1 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_3 \leftarrow r_3 + 2r_1}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 5 & 10 & -15 & -15 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_3 \leftarrow \frac{1}{5} r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_3 \leftarrow r_3 + (-1)r_2}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \)

\( \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & -3 & -6 & 4 & 9 \\ \end {bmatrix*} \underset{r_3 \leftrightarrow r_4}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & -3 & -6 & 4 & 9 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} \underset{r_3 \leftarrow r_3 + 3r_2}{\rightarrow} \underbrace{ \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 0 & 0 & -5 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} }_{\textbf{row echelon}} \underset{r_3 \leftarrow (-\frac{1}{5})r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} \)

\( \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & -3 & -3 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + 3r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & -9 & -7 \\ 0 & 1 & 2 & 0 & -3 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + 9r_3}{\rightarrow} \begin{bmatrix*}[r] 1 & 4 & 5 & 0 & -7 \\ 0 & 1 & 2 & 0 & -3 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + (-4)r_2}{\rightarrow} \underbrace{ \begin{bmatrix*}[r] \boxed{1} & 0 & -3 & 0 & 5 \\ 0 & \boxed{1} & 2 & 0 & -3 \\ 0 & 0 & 0 & \boxed{1} & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end {bmatrix*} }_{\textbf{reduced}} \)

Algorithm - Row Reduction #

PROCEDURE - Row Reduction Algorithm (or how to find the reduced row echelon matrix which is row equivalent to a given matrix)

FORWARD PHASE - produces a row echelon matrix which is row equivalent to the given matrix

STEP 1 - Begin with the leftmost nonzero column. The first pivot position is at the top of the column.

STEP 2 - Select a nonzero entry in the pivot column as the pivot. Interchange rows if necessary to move this entry into the pivot position.

STEP 3 - Use row replacement operations to create zeros in all positions below the pivot.

STEP 4 - Ignoring the rows containing previously identified pivot positions, repeat Steps 1 to 3 until there are no more nonzero rows to modify.

BACKWARD PHASE - produces a reduced row echelon matrix which is row equivalent to the given matrix

STEP 5 - Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, make it 1 by a scaling operation.

Use the row reduction algorithm to find the reduced row echelon matrix which is row equivalent to the given matrix.

\( \text{STEP 1} \left[ \left| \begin{matrix*}[r] \boxed{0} \\ 3 \\ 3 \\ \end {matrix*} \right| \begin{matrix*}[r] 3 & -6 & 6 & 4 & -5 \\ -7 & 8 & -5 & 8 & 9 \\ -9 & 12 & -9 & 6 & 15 \\ \end {matrix*} \right] \underset{r_1 \leftrightarrow r_2}{\text{STEP 2}\rightarrow} \left[ \left| \begin{matrix*}[r] \boxed{3} \\ 0 \\ 3 \\ \end {matrix*} \right| \begin{matrix*}[r] -7 & 8 & -5 & 8 & 9 \\ 3 & -6 & 6 & 4 & -5 \\ -9 & 12 & -9 & 6 & 15 \\ \end {matrix*} \right] \underset{r_3 \leftarrow r_3 + (-1)r_1}{\text{STEP 3}\rightarrow} \left[ \left| \begin{matrix*}[r] \boxed{3} \\ 0 \\ 0 \\ \end {matrix*} \right| \begin{matrix*}[r] -7 & 8 & -5 & 8 & 9 \\ 3 & -6 & 6 & 4 & -5 \\ -2 & 4 & -4 & -2 & 6 \\ \end {matrix*} \right] \text{STEP 4} \)

\( \text{STEP 1} \left[ \begin{matrix*}[r] \boxed{3} \\ 0 \\ 0 \\ \end {matrix*} \left | \begin{matrix*}[r] -7 \\ \boxed{3} \\ -2 \\ \end {matrix*} \right| \begin{matrix*}[r] 8 & -5 & 8 & 9 \\ -6 & 6 & 4 & -5 \\ 4 & -4 & -2 & 6 \\ \end {matrix*} \right] \underset{r_3 \leftarrow r_3 + \frac{2}{3} r_2}{\text{STEP 3}\rightarrow} \left[ \begin{matrix*}[r] \boxed{3} \\ 0 \\ 0 \\ \end {matrix*} \left | \begin{matrix*}[r] -7 \\ \boxed{3} \\ 0 \\ \end {matrix*} \right| \begin{matrix*}[r] 8 & -5 & 8 & 9 \\ -6 & 6 & 4 & -5 \\ 0 & 0 & \frac{2}{3} & \frac{8}{3} \\ \end {matrix*} \right] \text{STEP 4} \)

\( \text{STEP 1} \left[ \begin{matrix*}[r] \boxed{3} & -7 & 8 & -5 \\ 0 & \boxed{3} & -6 & 6 \\ 0 & 0 & 0 & 0 \\ \end {matrix*} \left | \begin{matrix*}[r] 8 \\ 4 \\ \boxed{2/3} \\ \end {matrix*} \right| \begin{matrix*}[r] 9 \\ -5 \\ \frac{8}{3} \\ \end {matrix*} \right] \underset{r_3 \leftarrow \frac{3}{2} r_3}{\text{STEP 3}\rightarrow} \underbrace{ \left[ \begin{matrix*}[r] \boxed{3} & -7 & 8 & -5 \\ 0 & \boxed{3} & -6 & 6 \\ 0 & 0 & 0 & 0 \\ \end {matrix*} \left | \begin{matrix*}[r] 8 \\ 4 \\ \boxed{1} \\ \end {matrix*} \right| \begin{matrix*}[r] 9 \\ -5 \\ 4 \\ \end {matrix*} \right] }_{\textbf{row echelon}} \text{STEP 5} \)

\( \begin{bmatrix*}[r] \boxed{3} & -7 & 8 & -5 & 8 & 9 \\ 0 & \boxed{3} & -6 & 6 & 4 & -5 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \underset{r_2 \leftarrow r_2 + (-4)r_3}{\rightarrow} \begin{bmatrix*}[r] \boxed{3} & -7 & 8 & -5 & 8 & 9 \\ 0 & \boxed{3} & -6 & 6 & 0 & -21 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + (-8)r_3}{\rightarrow} \begin{bmatrix*}[r] \boxed{3} & -7 & 8 & -5 & 0 & -15 \\ 0 & \boxed{3} & -6 & 6 & 0 & -21 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \underset{r_2 \leftarrow \frac{1}{3} r_2}{\rightarrow} \begin{bmatrix*}[r] \boxed{3} & -7 & 8 & -5 & 0 & -15 \\ 0 & \boxed{1} & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \)

\( \begin{bmatrix*}[r] \boxed{3} & -7 & 8 & -5 & 0 & -15 \\ 0 & \boxed{1} & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \underset{r_1 \leftarrow r_1 + 7r_2}{\rightarrow} \begin{bmatrix*}[r] \boxed{3} & 0 & -6 & 9 & 0 & -64 \\ 0 & \boxed{1} & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} \underset{r_1 \leftarrow \frac{1}{3} r_1}{\rightarrow} \underbrace{ \begin{bmatrix*}[r] \boxed{1} & 0 & -2 & 3 & 0 & -24 \\ 0 & \boxed{1} & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & \boxed{1} & 4 \\ \end {bmatrix*} }_{\textbf{reduced}} \)

Procedure - Read off the solution set of a linear system whose augmented matrix is a reduced row echelon matrix #

PROCEDURE - How to read off the solutions of a linear system whose augmented matrix is a reduced row echelon matrix?

STEP 1 - Is the linear system consistent?

If the last column of a row echelon augmented matrix contains a pivot then the linear system it represents is inconsistent and there is no solution. STOP HERE.
If the last column of a row echelon augmented matrix contains no pivot then the linear system it represents is consistent and there is either one solution or there are infinitely many solutions. PROCEED.

STEP 2 - How many solutions are there? The variables corresponding to the columns of the coefficient matrix that do not contain a pivot act as parameters and are called free variables.

The linear system has exactly one solution when there is no free variable (i.e., when every column of the coefficient matrix contains a pivot)
The linear system has exactly one solution when there is at least one free variable (i.e., when at least one column of the coefficient matrix does not contain a pivot)

STEP 3 - How to describe the solution set?

The variables corresponding to pivot columns are called pivot variables (or basic variables). It’s easy to solve the equations of the linear system in reduced row echelon form for the pivot variables in terms of the free variables. The equations should be solved sequentially starting from the bottommost (last) equation and ending with the topmost (first) equation. This procedure yields a parametric description of the solution set.

Theorem - Rouché-Capelli #

THEOREM - Rouché-Capelli - Existence and Uniqueness of Solutions of a Linear System

For a linear system in row echelon form

When there is a pivot in the last column of the augmented matrix the system is inconsistent
When there is no pivot in the last column of the augmented matrix the system is consistent
A consistent system with free variables (pivot-free columns in the coefficient matrix) has infinitely many solutions
A consistent system with no free variables (every column of the coefficient matrix contains a pivot) has a unique (one and only one) solution

Example#

Write the linear system as an augmented matrix; identify the pivot and free variables; and express the pivot variables in terms of the free variables.

\( \begin{aligned} x_1 && + && 6x_2 && && && + && 3x_4 && && && = && 0 \\ && && && && x_3 && - && 8x_4 && && && = && 5 \\ && && && && && && && && x_5 && = && -9 \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] \boxed{1} & 6 & 0 & 3 & 0 \\ 0 & 0 & \boxed{1} & -8 & 0 \\ 0 & 0 & 0 & 0 & \boxed{1} \\ \end {matrix*} \left| \begin{matrix*}[r] 0 \\ 5 \\ -9 \\ \end {matrix*} \right. \right] \)

The basic variables are \(x_1, x_3, x_5\) and the free variables are \(x_2, x_4\).

\( \begin{aligned} x_5 &= -9 \\ x_3 - 8x_4 = 5 \iff x_3 &= 8x_4 + 5 \\ x_1 + 6x_2 + 3x_4 = 0 \iff x_1 &= -6x_2 - 3x_4 \\ \end {aligned} \)

The solution set of the linear system is \(\{(\underbrace{-6x_2 - 3x_4}_{x_1}, x_2, \underbrace{8x_4 + 5}_{x_3}, x_4, \underbrace{-9}_{x_5})\}\)

Example#

Determine the numerical values of \(h\) and \(k\) for which the linear system has (1) no solution, (2) a unique solution, and (3) infinitely many solutions.

\( \begin{aligned} x_1 && - && 3x_2 && = && 1 \\ 2x_1 && + && hx_2 && = && k \\ \end {aligned} \)

\( \left[ \begin{matrix*}[r] 1 & -3 \\ 2 & h \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ k \\ \end {matrix*} \right. \right] \underset{r_2 \leftarrow r_2 + (-2)r_1}{\rightarrow} \left[ \begin{matrix*}[r] 1 & -3 \\ 0 & h + 6 \\ \end {matrix*} \left| \begin{matrix*}[r] 1 \\ k - 2 \\ \end {matrix*} \right. \right] \)

\( \begin{aligned} \text{no solution} & \begin{cases} h + 6 = 0 \iff h = -6 \\ k - 2 \ne 0 \iff k \ne 2 \\ \end {cases} \\ \text{one solution} & \begin{cases} h + 6 \ne 0 \iff h \ne -6 \\ \end {cases} \\ \text{infinitely many solutions} & \begin{cases} h + 6 = 0 \iff h = -6 \\ k - 2 = 0 \iff k = 2 \\ \end {cases} \\ \end{aligned} \)