Skip to main content

Elementary Linear Algebra: An Active Learning Approach

Section 3.1 Elimination

We start by defining the primary object under consideration in introductory linear algebra, the linear system. We define some properties of and notation for linear systems, then we describe
  1. Back-substitution, the process of solving a set of equations presented top to bottom in order exhibiting a nonincreasing number of variables (this is called upper-triangular form). We solve such a system of equations from the bottom up. In this section we will introduce back-substitution and use it only on linear systems with a unique solution, leaving the more complicated cases for Section 3.4 and Subsection 6.1.1, and
  2. Elimination, a technique of simplifying systems of linear equations so that each successive equation in the eliminated system has fewer variables than the previous equation,
  3. Gauss-Jordan Elimination, in which we implement back-substitution by a form of elimination.
Elimination and back-substitution are used together to solve systems of linear equations. Elimination by itself is used in some way in nearly every topic in the course.

Subsection 3.1.1 Concepts and Notation

Definition 3.1.1. Linear systems and notation. 

Let \(\{A_{ij}\}_{i,j=1}^{i=m,j=n}\) and \(\{b_1,b_2,\cdots,b_m\}\) be sets of real numbers (constants), and \(\{x_j\}_{j=1}^n\) be a set of real variables. Then

\begin{align}
A_{11}x_1\,\,+\,\,A_{12}x_2\,\,+\,\,\cdots\,\,+\,\,A_{1n}x_n\amp \,\,\,=\,\,\,b_1\notag\\
A_{21}x_1\,\,+\,\,A_{22}x_2\,\,+\,\,\cdots\,\,+\,\,A_{2n}x_n\amp \,\,\,=\,\,\,b_2\tag{3.1.1}\\
\vdots\qquad\qquad\quad\amp\notag\\
A_{m1}x_1\,+\,A_{m2}x_2\,\,+\,\,\cdots\,\,+\,A_{mn}x_n\amp \,\,\,=\,\,\,b_m\notag
\end{align}

is called an \(m\times n\,\) system of linear equations, or more simply, an \(m\times n\,\) linear system. We will use the terms system and linear system interchangeably since we will not encounter non-linear systems. 


An alternative to the cumbersome notation in (3.1.1) arises via matrix-vector multiplication. Define the matrix \(\A=(A_{ij})\) from the set \(\{A_{ij}\}_{i,j=1}^{i=m,j=n}\) in (3.1.1), define the vector \(\x:=\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)\) of variables, and fix the RHS vector \(\b=\left(\begin{array}{c}b_1\\b_2\\ \vdots\\b_m\end{array}\right).\) Then the \(m \times n\) system of linear equations in (3.1.1) may be expressed as



\begin{equation}
\left(\begin{array}{cccc}A_{11}\amp A_{12}\amp \cdots\amp A_{1n}\\A_{21}\amp A_{22}\amp \cdots\amp A_{2n}\\ \vdots\amp \amp \ddots\amp \vdots \\A_{m1}\amp \cdots\amp \cdots\amp A_{mn}\end{array}\right)\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=\left(\begin{array}{c}b_1\\b_2\\ \vdots\\b_m\end{array}\right)\tag{3.1.2}
\end{equation}



or more compactly as



\begin{equation}
\A\x=\b\text{.}\tag{3.1.3}
\end{equation}



 


A transparent way to represent (3.1.2) / (3.1.3) is by the augmented matrix




\begin{equation}
\left(\begin{array}{cccc|c}A_{11}\amp A_{12}\amp \cdots\amp A_{1n}\amp b_1\\A_{21}\amp A_{22}\amp \cdots\amp A_{2n}\amp b_2\\ \vdots\amp \amp \ddots\amp \vdots \\A_{m1}\amp \cdots\amp \cdots\amp A_{mn}\amp b_m\end{array}\right)\tag{3.1.4}
\end{equation}



or more compactly as



\begin{equation}
\left(\A|\b\right)\text{.}\tag{3.1.5}
\end{equation}



Note the vertical separator between the entries of \(\A\) and those of \(\b.\)  In augmented matrix notation the now-hidden variables \(x_1,\ldots,x_n\) are kept track of by position, allowing us to skip the wasteful task of writing all the variable names repeatedly. For each \(j=1,2,\ldots,n,\) the \(j^{\text{ th}}\) column is associated with the component \(x_j\) of \(\x,\) just as in (3.1.4) above.


 
For in-line representation of a linear system we will use (3.1.3) or (3.1.5). When we want to explicitly show the coefficients and RHS of a system, we will use the augmented matrix representation since it is more compact than the explicit representations but still transparent.
 
The equation \(\A\x=\b\text{,}\) though a system of linear equations in single real variables \(x_i,\) may be interpreted as a linear equation in a single variable vector \(\x.\) If we want to emphazise the equation nature of a linear system, we will call it a linear equation.



Rows: Whether using the explicit representation in (3.1.1) or the augmented matrix representation in (3.1.4) we will refer to each equation in a linear system as a “row” \(\,R_i\) for some particular row index \(i\in\{1,2,\ldots\}\text{.}\) For example in



\begin{equation*}
\begin{array}{rcrcrcrc}
2x  \amp + \amp 3y  \amp -  \amp z \amp=\amp5\\
x \amp + \amp y \amp - \amp z \amp =\amp0
\end{array}
\end{equation*}




\(R_1\) is



\begin{equation*}
2x+3y-z=5
\end{equation*}



while in the corresponding augmented matrix



\begin{equation*}
\lmatrix{rrr|r} 2 \amp 3 \amp -1 \amp 5\\1 \amp 1 \amp -1 \amp 0 \rmatrix
\end{equation*}




\(R_1\) is



\begin{equation*}
\left(\,2\,\,\,\,3\,\,\,-1\,\,\,|\,\,\,5\,\right).
\end{equation*}



The term zero row applies to matrices but not to linear systems. In a linear system, a full zero row is a row with only \(0\)’s on both sides of the vertical separator / equal sign and a LHS-only zero row has only \(0'\)s on the left-hand side of the vertical separator / equal sign and a nonzero entry on the right. Each full zero row and each LHS-only zero row of a system yield a zero row in the associated matrix \(\A.\)






Definition 3.1.2. Wide, square and tall systems.





    

  1. A wide \(m\times n\) linear system has \(m\lt n.\)

    2. 

  2. A square \(m\times n\) linear system has \(m=n.\)

    3. 

  3. A tall \(m\times n\) linear system has \(m\gt n.\)

    4. 


Definition 3.1.3. Solution of a linear system.



Let \(\A\in\R^{m\times n},\b\in\R^m.\) A vector \(\x=\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)\) is a solution to the linear system \(\A\x=\b\) if the set of components \(x_1,x_2,\ldots x_n\) of \(\x\) satisfies each of the individual equations in the system. If so we say that \(\x\,\) solves the linear system. 
A linear system \(\A\x=\b\) having one or more solutions is consistent; otherwise we say that the system is inconsistent.
The equation \(\A\x=\b\) is consistent when \(\b\) can be written as a linear combination of the columns of \(\A\) and inconsistent when \(\b\) there is no linear combination of the columns of \(\A\) which equals \(\b.\)




Question: Why can’t there be exactly, say, two solutions? If there are two distinct solutions to \(\A\x=\b,\) there must an infinite number of distinct solutions parametrized by a real variable. You will explore this in the worksheet.



Remark 3.1.5. The logic of finding solutions to linear equations.



To determine whether a linear equation \(\A\x=\b\) is consistent or inconsistent we 
    

  1. assume that there is a solution, meaning that we assume each equation in Definition 3.1.1 holds true,
    2. 

  2. then use algebra to try find what the solution must be.
    3. 

 


Consider the \(2\times2\) consistent system



\begin{align*}
2x+y\amp =5\\
3x+2y\amp =9
\end{align*}



We assume a solution \(\left(\begin{array}{c}x\\y\end{array}\right)\) and do a little algebra to find out that if \(\left(\begin{array}{c}x\\y\end{array}\right)\) is a solution, it must be \(\left(\begin{array}{c}1\\3\end{array}\right).\) Logically speaking, we must verify that \(\left(\begin{array}{c}1\\3\end{array}\right)\) is a solution before concluding that it is a solution. But checking the solution is time-consuming and, it turns out, unnecessary.


 


When we solve a given linear system, we will perform algebraic operations to convert the system (3.1.1) to the trivial system



\begin{align}
x_1\amp =t_1\notag\\
x_2\amp =t_2\tag{3.1.6}\\
\amp \,\,\,\vdots\notag\\
x_n\amp =t_n\notag
\end{align}



where \(t_1,t_2,\ldots,t_n\) are real numbers. Although (3.1.6) is in the form of a solution it is also a system, in a form which makes it very easy to solve - the solution may be read directly from the system.


 
Since the algebraic operations we will use are crafted to leave the solution set unchanged, any solution to the trivial system must be a solution of the original system. This permits us to bypass the obligatory solution check.

Systems which have fewer variables in each subsequent equation are called row-echelon systems, defined precisely in Definition 3.1.6. For row-echelon systems, the algebra needed to find a solution (or show that none exists) is particularly easy.


Further down in this section we will show how to use algebra to convert any linear system into an equivalent row-echelon linear system but for now we will consider row-echelon linear systems on their own.

Subsection 3.1.2 Row-Echelon and Upper-Triangular Forms




Definition 3.1.6. Row-echelon form.



A linear system / augmented matrix is in row-echelon form if 
    

  1. Any full zero rows and LHS-only zero rows are grouped together at the bottom, and
    2. 

  2. Starting with the second row, the first nonzero entry in each nonzero row is strictly to the right of the first nonzero entry in the row above it.
    3. 

 
The same criteria holds for (non-augmented) matrices; a matrix \(\U\in\R^{m\times n}\) is in row-echelon form if \(U_{ij}=0\) when \(i\gt j.\) Unless otherwise indicated \(\U\) will always denote a matrix in row-echelon form.
 
A linear system is in row-echelon form when its augmented matrix is in row-echelon form.
 
We call a linear system in row-echelon form a row-echelon system.

It may seem silly to discuss full zero rows at all, but full zero rows as well as LHS-only zero rows may result when we use elimination to convert a general linear system into an equivalent row-echelon system so we include them in the above definition.



Example 3.1.7. Examples and non-examples of row-echelon form.

The linear system

\begin{equation*}
\left(\begin{array}{rrrr|r}3\amp -1\amp 4\amp 1\amp 9\\0\amp 0\amp 7\amp 4\amp -12 \\0\amp 0\amp 0\amp 0\amp 0 \end{array} \right)
\end{equation*}

is in row-echelon form. 


The linear system



\begin{equation*}
\left(\begin{array}{rrrr|r}2\amp -1\amp 6\amp 3\amp -2\\0\amp 0\amp 7\amp 0\amp -12 \\0\amp 5\amp 49\amp 8\amp -64 \end{array} \right)
\end{equation*}



is not in row-echelon form.


 


The linear systems



\begin{equation*}
\left(\begin{array}{rrr|r}-4\amp 3\amp -2\amp 1\\0\amp 12\amp -6\amp -18 \\0\amp 0\amp 15\amp 0 \end{array} \right)
\end{equation*}



and



\begin{equation*}
\left(\begin{array}{rrr|r}1\amp -1\amp 2\amp -1\\0\amp 1\amp 7\amp 14 \\0\amp 0\amp 0\amp 0 \end{array} \right)
\end{equation*}



are in row-echelon form.


 


The linear system



\begin{equation*}
\left(\begin{array}{rrr|r}-2\amp 10\amp 6\amp 8\\0\amp 1\amp -6\amp 9\\0\amp 2\amp -1\amp 9 \end{array} \right)
\end{equation*}



is not in row-echelon form.


 


The linear system



\begin{equation*}
\left(\begin{array}{rrr|r}9\amp 4\amp -4\amp -36\\0\amp 7\amp -3\amp -13 \\0\amp 0\amp 2\amp -6\\0\amp 0\amp 0\amp 2\end{array} \right)
\end{equation*}



is in row-echelon form.


 


The linear system



\begin{equation*}
\left(\begin{array}{rrr|r}-4\amp 1\amp -1\amp 9\\0\amp 5\amp -26\amp -39 \\0\amp 0\amp -5\amp -25\\0\amp 0\amp 1\amp -3\end{array} \right)
\end{equation*}



is not in row-echelon form.



Definition 3.1.8. Pivots, pivot rows and columns, and free rows and columns.



In an \(m\times n\) system in row-echelon form, the first nonzero entry in the \(i^{\text{ th } }\) row of \(\U\) is called a pivot. A pivot may be associated with a system \(\left(\U|\c\right)\) or a matrix \(\U.\) 
If a pivot occurs in the \(j^{\text{ th } }\) column we call \(x_j\) a pivot variable. All variables in \(\x\) which are not pivot variables are called free variables.

 
Let \(\ell:=\min\{m,n\}.\) If \(\U\) exhibits \(\ell\) pivots we say that \(\U\) or the system, whichever is applicable, exhibits a full set of pivots.
 
Any row or column with a pivot is called a pivot row or pivot column respectively. Any row or column of \(\U\) that is not a pivot row or a pivot column is called a free row or a free column.

Since every nonzero entry must lie on or above the diagonal in \(\U\in\R^{m\times n},\) all pivots must lie on or above the diagonal. No full zero row or LHS-only zero row is a pivot row.



Example 3.1.9. Pivots.

In the linear system below the pivots are in boldface.

\begin{equation*}
\left(\begin{array}{rrrr|r}\mathbf{6}\amp -8\amp 3\amp -2\amp 4\\0\amp 0\amp \mathbf{7}\amp 8\amp -5 \\0\amp 0\amp 0\amp \mathbf{3}\amp 6 \\0\amp 0\amp 0\amp 0\amp 0 \end{array} \right).
\end{equation*}

Proof.

\((\Rightarrow)\) Suppose \(\U\x=\vec{c}\) is inconsistent and BWOC suppose that \(\left(\U|\vec{c}\right)\) exhibits no LHS-only zero rows, and discard all full zero rows.
 
Now each row has at least one pivot. Set all free variables \(x_i\) equal to \(0.\) Let \(R_i\) be any row remaining after discarding the full zero rows and let \(x_i\) be the variable associated with the pivot in \(R_i.\)

 
We may solve the equation represented by \(R_i\) for \(x_i.\) Since \(R_i\) is arbitrary, we conclude that we may solve for each pivot variable. Doing so and including the zero values for the free variables produces a solution to the system, hence the system is consistent.
 



\((\Leftarrow)\) Suppose \(\U\x=\vec{c}\) exhibits a LHS-only zero row \(R_j\) and let \(c_j=c\ne0.\)  Such a row represents the equation



\begin{equation*}
0x_1+0x_2+\cdots+0x_n=c
\end{equation*}



which is not satisfied for any \(x_1,x_2,\ldots,x_n.\) This equation is inconsistent and hence any system of which \(R_j\) is a row, including \(\U\x=\vec{c},\) is inconsistent.


Proof.
Let \(\U\x=\vec{c}\) be a consistent wide row-echelon linear system. Because there are more columns than rows, there are more variables than equations.  Consequently at least one equation in \(\U\x=\vec{c}\) will exhibit at least one variable which will remain unspecified after back-substitution, and hence allowed to take on any real value in a solution. This leads to an infinite number of solutions, one for each real number.
Proof.
Suppose \(\U\x=\vec{c}\) is an \(m\times n\) row-echelon linear system with \(m\lt n,\) and suppose that \(\left(\U|\vec{c}\right)\) shows a full set of pivots so that there are no full zero rows nor LHS-only zero rows. Then by Theorem 3.1.10, \(\U\x=\vec{c}\) is consistent, and it is wide by hypothesis.  Now Theorem 3.1.11 guarantees that \(\U\x=\vec{c}\) has an infinite number of solutions.
In Example 3.1.13 below we show three examples of wide row-echelon linear systems.



Example 3.1.13. Wide row-echelon systems and their solution sets.

In each system below let \(\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)\) represent the vector of variables. 
    

  1. 

    

    The augmented matrix
    

    
\begin{equation*}
\left(\begin{array}{rrrr|r}1\amp 0\amp -5\amp 2\amp 4\\0\amp 0\amp 0\amp 4\amp -12 \\0\amp 0\amp 0\amp 0\amp 0 \end{array} \right)
\end{equation*}

    

    is in row-echelon form and represents a consistent linear system since no row of the form \(0=c\ne0\) is present. By Corollary 3.1.12 the system is consistent and by Corollary 3.1.30 it therefore has an infinite number of solutions. Intuitively, the infinitude of solutions springs from the fact that the first three variables \(x,y,z\) cannot be individually specified, so in any solution two of \(x,y,z\) must be left as variables, allowed to take on any two real values.
    

    

    The pivots are \(1\) and \(4,\) and only the first two rows are pivot rows so the system does not exhibit a full set of pivots.
    

    We will learn how to solve this type of system in Subsection 6.1.1 and Section 3.4.
    

    2. 

  2. 

    

    The augmented matrix
    

    
\begin{equation*}
\left(\begin{array}{rrrr|r}2\amp -1\amp 8\amp 1\amp 3\\0\amp 0\amp 1\amp 1\amp -1 \\0\amp 0\amp 0\amp 6\amp 0 \end{array} \right)
\end{equation*}

    

    is in row-echelon form and represents a consistent linear system since no row of the form \(0=c\ne0\) is present. By Corollary 3.1.30 the system has an infinite number of solutions. Intuitively, the infinitude of solutions springs from the fact that the the first two variables \(x,y\) cannot be individually specified, so in any solution one of \(x,y\) must be left as a variable, allowed to take on any real value.
    

    

    The three pivots are \(2,\) \(1\) and \(6,\) and since all three rows are pivot rows so the system exhibits a full set of pivots.
    

    As in Example 3.1.13 we will learn how to solve this type of system in Subsection 6.1.1 and Section 3.4.
    

    3. 

  3. 

    The augmented matrix
    

    
\begin{equation*}
\left(\begin{array}{rrrr|r}1\amp -4\amp 5\amp -7\amp 1\\0\amp 0\amp -5\amp 2\amp -8\\0\amp 0\amp 0\amp 0\amp 1 \end{array} \right)
\end{equation*}

    

    is in row-echelon form and shows two pivots, \(1\) and \(-5\) which do not constitute a full set of pivots.  This is an inconsistent linear system because of the presence of the third row which represents the equation
    

    
\begin{equation*}
0x+0y+0z+0w=1
\end{equation*}

    

    (or just \(0=1\)). This equation is absurd (that is, false for all \(x,y,z,w\in\R\)) showing that the implicit assumption of a solution \(\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)\) was invalid, so we conclude that the system has no solution.
    

    4. 

Square systems will be of particular interest to us, since unlike wide systems they may have a single unique solution.



Definition 3.1.14. Singular and nonsingular systems.



Let \(\A\in\R^{n\times n}\) and \(\b\in\R^n.\) 
The linear system \(\A\x=\b\) is singular if it has either no solutions or an infinite number of distinct solutions.
 
If \(\A\x=\b\) is not singular, we say that \(\A\x=\b\) is nonsingular.
Proof.

Example 3.1.17. Constructing a singular system.



Consider the \(2\times 2\) system below



\begin{equation*}
\begin{array}{rrrrr}
\amp3x\amp-\amp5y\amp=\amp9\\
\amp cx\amp+\amp20y\amp=\amp b_2\,.
\end{array}
\end{equation*}



 
    

  1. Find a coefficient \(c\) which makes the system singular.
    2. 

  2. For the \(c\) you found above, find \(b_2\) which makes the system consistent.
    3. 

 

Solution: To ensure that the resulting system is singular, the RHS of \(R_2\) must be a multiple of the RHS of \(R_1.\) To ensure this \(c\) must satisfy \(3\cdot 20-5c=0,\) or \(c=-12.\) Then elimination will yield full zero row for the second row, and since the eliminated system exhibits a full set of pivots, by Corollary 3.1.31 it has an infinite number of solutions.

Definition 3.1.18. Upper-triangular systems / matrices.



A square linear system in row-echelon form is called upper-triangular: 

\begin{equation}
\U=\left(\begin{array}{ccccc} \ast \amp \ast \amp \ast \amp \cdots \amp \ast \\
0 \amp \ast \amp \ast \amp \cdots \amp \ast \\ 0 \amp 0 \amp \ast \amp \cdots \amp \ast \\ \vdots \amp \vdots \amp \ddots \amp \ddots \amp \vdots \\
0 \amp 0 \amp \cdots \amp 0 \amp \ast \end{array}\right)\tag{3.1.7}
\end{equation}



Figure 3.1.19. Upper triangular matrices. The \(\ast\) represent possibly distinct arbitrary real numbers.
 
The same criteria holds for (non-augmented) matrices; a matrix \(\U\in\R^{n\times n}\) is upper-triangular if \(U_{ij}=0\) when \(i\gt j.\)

Proof.
Suppose \(\U\x=\vec{c}\) is a consistent singular row-echelon linear system. Then \(\U\x=\vec{c}\) has 1) at least one full zero row and 2) no LHS-only zero rows. Discarding any full zero rows results in a consistent wide row-echelon system, so by Theorem 3.1.11 the system has an infinite number of solutions.
Proof.

\((\Leftarrow)\)Suppose \(\U\x=\vec{c}\) is upper-triangular with \(n\) pivots. Then it can be solved by back-substitution, defined below in Algorithm 3.1.22. Since \(\U\x=\vec{c}\) has \(n\) pivots, it has \(n\) pivot variables and hence no free variables and therefore the solution we find will be unique.
 

\((\Rightarrow)\) Suppose the consistent system \(\U\x=\vec{c}\) is nonsingular and has fewer than \(n\) pivots. Since \(\U\x=\vec{c}\) is consistent it has no LHS-only zero rows; since it has fewer than \(n\) pivots it has fewer than \(n\) pivot variables and hence at least one free variable and at least one full zero row. Discard all full zero rows, leaving a consistent wide system which by Theorem 3.1.11 has an infinite number of solutions. This contradicts Definition 3.1.14 so our assumption that the system has fewer than \(n\) pivots is false. We conclude that \(\U\x=\vec{c}\) has \(n\) pivots.

Subsection 3.1.3 Using Elimination and Back Substitution To Solve Systems



In this section we will only solve consistent square systems with unique solutions. So, although we will do elimination on all systems in this section, our application of back-substitution will be limited.



Example 3.1.23. Solving an upper-triangular system by back-subsitution.

Determine whether the square linear system below is consistent or inconsistent. If it is consistent, solve it using back-substitution.

\begin{equation*}
\left(\begin{array}{rrr|r}4\amp -1\amp 6\amp 1\\0\amp -11\amp 5\amp 1\\0\amp 0\amp 4\amp -8\end{array} \right)
\end{equation*}



We assume that the solution vector is \(\x=\left(\begin{array}{r}x\\y\\z\end{array}\right).\) The system is in upper-triangular form and represents a consistent linear system since no row of the form \(0=c\ne0\) is present. By Theorem 3.1.21 this system has a unique solution \(\left(\begin{array}{c}x\\y\\z\end{array}\right).\) We find this unique solution by back-substitution as follows
 
The third equation is \(4z=-8\) which gives \(z=-2.\)

 
The second equation is now \(-11y+5(-2)=1\) which yields \(y=-1.\)

 
Now the first equation is \(4x-(-1)+6(-2)=1\) from which we obtain \(x=3.\)

 
Now the solution to the system is \(\x=\left(\begin{array}{r}x\\y\\z\end{array}\right)=\left(\begin{array}{r}3\\-1\\-2\end{array}\right).\)


Example 3.1.24. An inconsistent upper-triangular system.



The augmented matrix



\begin{equation*}
\left(\begin{array}{rrr|r}3\amp 5\amp -1\amp 4\\0\amp 2\amp 8\amp -4\\0\amp 0\amp 0\amp 3\end{array} \right)
\end{equation*}



is in upper-triangular form. This represents an inconsistent linear system because the third row \(0=3\) cannot be satisfied by any \(x,y,z,\) showing that the implicit assumption of a solution \(\left(\begin{array}{c}x\\y\\z\end{array}\right)\) was invalid. We conclude that the system has no solution.



Remark 3.1.25.

It is unlikely that any given linear system is in row-echelon form. But elimination, described below, is a technique by which one may use row operations to convert a general linear system into an equivalent row-echelon linear system with the same solution set as the original system.

Definition 3.1.26. Row Operations.



A row operation on a linear system is 1) a row swap or 2) the replacement of one of the rows in the system with some linear combination of rows in the system.
 1 
Another way to characterize the set of permissible row operations is as the set of operations which can be implemented by left-multiplication of the augmented matrix by some matrix \(E;\) see Section 3.7.


The most common row operation is the linear combination replacement




\begin{equation*}
\a_1R_i+\a_2R_j\rightarrow R_j,\quad \a_2\ne0.
\end{equation*}



Well-chosen \(\a_1,\a_2\) can help minimize the appearance of fractions in the computation.






A useful special case of linear combination replacement is scalar multiple replacement




\begin{equation*}
\a R_j\rightarrow R_j
\end{equation*}



for \(\a\ne0,1.\)







Finally, if it is convenient to exchange the positions of two rows, we will use the row swap




\begin{equation*}
R_i\longleftrightarrow R_j
\end{equation*}



for \(i\ne j.\)






Definition 3.1.27. Elimination.



The process of using a sequence of row operations to convert a given linear system \(\left(\A|\b\right)\) into row-echelon form \(\left(\U|\vec{c}\right).\) 
We say \(\A\x=\b\) or \(\left(\A|\b\right)\) eliminates to \(\U\x=\vec{c}\) or \(\left(\U|\vec{c}\right).\)


Example 3.1.28. Elimination to row-echelon form is not unique.

One may easily find two different sets of three row operations each of which put \(\left(\begin{array}{rrr} -4\amp 5\amp -1\\-3\amp 3\amp 7\\2\amp 0\amp 2 \end{array} \right)\) in upper-triangular form.
 



Solution: We may use, for example



\begin{equation*}
3R_1-4R_2\rightarrow R_2, R_1+2R_3\rightarrow R_3,-5R_2+3R_3\rightarrow R_3,\text{ or } \nonumber
\end{equation*}



to obtain



\begin{equation*}
\left(\begin{array}{rrr} -4\amp 5\amp -1\\0\amp 3\amp -31\\0\amp 0\amp 164 \end{array} \right)
\end{equation*}



or



\begin{equation*}
-6R_1+8R_2\rightarrow R_2, 2R_1+4R_3\rightarrow R_3,10R_2+6R_3\rightarrow R_3
\end{equation*}



to obtain



\begin{equation*}
\left(\begin{array}{rrr} -4\amp 5\amp -1\\0\amp -6\amp 62\\0\amp 0\amp 656 \end{array} \right)
\end{equation*}



Proof.
Consider the \(m\times n\) linear system \(\A\x=\b.\) It suffices to demonstrate that the solution set of \(\A\x=\b\) is invariant under 1) an arbitrary row swap and 2) an arbitrary linear combination replacement, since elimination is a finite composition of some number of each of these two row operations.
 
1) To prove that a row swap leaves the solution set unchanged, we need only note that a linear system is a set of equations, and swapping rows does not change that set.
 
2) To prove that a general linear combination replacement leaves the solution set unchanged, fix \(i,j\in\{1,2,\ldots,m\}\) and \(\a_1\in\R,\a_2\in\R\setminus\{0\}\) suppose \(\left(\A'|\vec{b'}\right)\) is the result of applying \(\a_1R_1+\a_2R_j\rightarrow R_j\) to \(\A\x=\b.\) We prove that the solution sets of \(\A\x=\b\) and \(\A'\x=\vec{b'}\) coincide.
 



\(\left(\subseteq\right)\) Let \(\x\) be a solution of \(\A\x=\b.\) Then \(\x\) still satisfies the equations in all rows of \(\A'\x=\vec{b'}\) which are unchanged from \(\A\x=\b,\) namely the \(j^{\text{th}}.\) Now \(\x\) satisfies the equations from the \(i^{\text{th}}\) and \(j^{\text{th}}\) rows of \(\A\x=\b,\) and multiplying those equations by \(\a_1,\a_2\) respectively yields the equations



\begin{equation}
\a_1A_{i1}x_1+\a_1A_{i2}x_2+\cdots+\a_1A_{in}x_n=\a_1b_i\tag{3.1.8}
\end{equation}



and



\begin{equation}
\a_2A_{j1}x_1+\a_2A_{j2}x_2+\cdots+\a_2A_{jn}x_n=\a_2b_j.\tag{3.1.9}
\end{equation}



Adding the LHS and RHS of each of (3.1.8) and (3.1.9) respectively gives



\begin{equation*}
\a_1A_{i1}x_1+\cdots+\a_1A_{in}x_n+\a_2A_{j1}x_1+\cdots+\a_2A_{jn}x_n=\a_1b_i+\a_2b_j
\end{equation*}



or



\begin{equation*}
\left(\a_1A_{i1}+\a_2A_{j1}\right)x_1+\cdots+\left(\a_1A_{in}+\a_2A_{jn}\right)x_n=\a_1b_i+\a_2b_j
\end{equation*}



which is precisely the equation for row \(j\) in \(\A'\x=\vec{b'},\) now evidently satisfied by \(x_1,x_2,\ldots,x_n.\) So every solution of \(\A\x=\b\) is a solution of \(\A'\x=\vec{b'}.\)



 



\(\left(\supseteq\right)\) Let \(\x\) be a solution of \(\A'\x=\vec{b'}.\) All equations in \(\A\x=\b\) are satisfied except possibly for the \(j^{\text{th}}\) row. The \(j^{\text{th}}\) row of \(\A'\x=\vec{b'}\) is



\begin{equation*}
\left(\a_1A_{i1}+\a_2A_{j1}\right)x_1+\cdots+\left(\a_1A_{in}+\a_2A_{jn}\right)x_n=\a_1b_i+\a_2b_j
\end{equation*}



or



\begin{equation*}
\a_1A_{i1}x_1+\cdots+\a_1A_{in}x_n+\a_2A_{j1}x_1+\cdots+\a_2A_{jn}x_n=\a_1b_i+\a_2b_j.
\end{equation*}



which we may rewrite as



\begin{equation*}
\a_1\left(A_{i1}x_1+\cdots+A_{in}x_n-b_i\right)+\a_2A_{j1}x_1+\cdots+\a_2A_{jn}x_n=\a_2b_j.
\end{equation*}



The expression in the parentheses equals zero since \(\x\) satisfies the equation in the \(i^{\text{th}}\) row of \(\A'\x=\vec{b'},\) yielding



\begin{equation*}
\a_2A_{j1}x_1+\cdots+\a_2A_{jn}x_n=\a_2b_j
\end{equation*}



which we may divide by \(\a_2\ne0\) to obtain



\begin{equation*}
A_{j1}x_1+\cdots+A_{jn}x_n=b_j.
\end{equation*}



This shows that \(\x\) satisfies the \(j^{\text{th}}\) row of \(\A\x=\b.\) Now we conclude that \(\x\) indeed satisfies \(\A\x=\b,\) so every solution of \(\A'\x=\vec{b'}\)is a solution of \(\A\x=\b.\)



 
We have shown both subset inclusions and we now are assured that the solution sets of \(\A'\x=\vec{b'}\) and \(\A\x=\b\) coincide.  Hence elimination does not change the solution set from that of the original system.

Theorem 3.1.29 provides us with generalizations of a number of theorems above relating only to row-echelon systems.


Proof.
Let \(\A\x=\b\) be a consistent wide linear system eliminating to \(\U\x=\vec{c},\) by Theorem 3.1.29 also a consistent wide system and in row-echelon form. By Theorem 3.1.11 \(\U\x=\vec{c}\) has an infinite number of solutions. By Theorem 3.1.29 each of those solutions are solutions of \(\A\x=\b,\) so \(\A\x=\b\) has an infinite number of solutions.
Proof.
Suppose \(\A\x=\b\) is a consistent singular system eliminating to \(\U\x=\vec{c},\) by Theorem 3.1.29 also a consistent singular system. Then by Definition 3.1.14 \(\U\x=\vec{c}\) does not have a full set of pivots and hence has 1) at least one full zero row and 2) no LHS-only zero rows. Discarding all full zero rows results in a wide row-echelon system, which by Theorem 3.1.20 has an infinite number of solutions. Now by Theorem 3.1.29 \(\A\x=\b\) has an infinite number of solutions.
Proof.
Suppose \(\A\x=\b\) is a square system eliminating to \(\U\x=\vec{c}.\)

 
First suppose that \(\U\x=\vec{c}\) exhibits a full set of pivots. By Theorem 3.1.21 \(\U\x=\vec{c}\) is nonsingular and hence by Definition 3.1.14 has a unique solution \(\x,\) which by Theorem 3.1.29 is the unique solution to \(\A\x=\b.\)

 
Now suppose that \(\U\x=\vec{c}\) does not have a full set of pivots. By Theorem 3.1.21 \(\U\x=\vec{c}\) is singular and hence by Definition 3.1.14 has either no solution or an infinite number of solutions. By Theorem 3.1.29 the same is true for \(\A\x=\b.\)

When we solve a consistent linear system using elimination in this section, we will cite Theorem 3.1.29 to conclude that the original system is solved by the same \(\x\) that solves the reduced system. In subsequent sections we will cast aside this requirement for brevity.


In Example 3.1.34 below we include, for one time only, the explicit representation of the linear system \(\A\x=\b.\) All subsequent examples will use only the augmented matrix representation and you should, too.




Example 3.1.34. Solving a linear system using elimination and back-substitution, featuring explicit and augmented matrix notation.



Determine whether the linear system



\begin{equation*}
\begin{array}{rrcrcrcrr}
\amp 2x  \amp + \amp 3y  \amp - \amp z \amp = \amp 5\\
\amp x \amp + \amp y \amp - \amp z \amp = \amp 0\\
\amp  3x \amp - \amp  y \amp + \amp 2z \amp = \amp 7
\end{array}
\end{equation*}



is consistent or inconsistent by using elimination. If it is consistent, find the solution vector.


 


The corresponding augmented matrix is



\begin{equation}
\left(\A|\b\right)=\lmatrix{rrr|r} 2 \amp 3 \amp -1 \amp 5\\1 \amp 1 \amp -1 \amp 0\\3 \amp -1 \amp 2\amp 7 \rmatrix\text{.}\tag{3.1.10}
\end{equation}




Step 1: First we perform the row operations \(R_1-2R_2 \rightarrow R_2\) and  \(3R_1-2R_3 \rightarrow R_3\) to eliminate \(x\) from the second and third rows. This gives the equivalent system:



\begin{equation*}
\begin{array}{rrcrcrcr}
\amp 2x \amp + \amp 3y \amp -\amp z \amp = 5\\
\amp \amp \amp y \amp + \amp z \amp =5\\
\amp \amp \amp  11y \amp - \amp 7z \amp = 1
\end{array}
\end{equation*}



The updated augmented matrix is



\begin{equation*}
\lmatrix{rrr|r} 2 \amp 3 \amp -1 \amp 5\\0 \amp 1 \amp 1 \amp 5\\0 \amp 11 \amp -7 \amp 1 \rmatrix
\end{equation*}




Step 2: Next we perform the row operation \(-11R_2+R_3 \rightarrow R_3\) to eliminate \(y\) from the third row. This gives the equivalent system:



\begin{equation*}
\begin{array}{rrcrcrcr}
\amp 2x \amp + \amp 3y \amp - \amp z \amp = 5\\
\amp \amp \amp y \amp + \amp z \amp =5\\
\amp \amp \amp   \amp \amp -18z \amp = -54\\
\end{array}
\end{equation*}



Starting with the updated augmented matrix, we have



\begin{equation}
\lmatrix{rrr|r} 2 \amp 3 \amp -1 \amp 5\\0 \amp 1 \amp 1 \amp 5\\0 \amp 0 \amp -18\amp -54 \rmatrix\tag{3.1.11}
\end{equation}



Elimination is complete, and we begin the process of back-substitution.  Since we have eliminated \(x\) and \(y\) from \(R_3,\) we can easily solve \(R_3\) for \(z\text{:}\)




\begin{equation*}
-18z = -54 \Rightarrow z = 3
\end{equation*}



Substituting \(z=3\) into \(R_2\) we find:



\begin{equation*}
y + 3 = 5 \Rightarrow y = 2
\end{equation*}



Finally we can substitute \(y=2, z=3\) into \(R_1\) to solve for \(x\text{:}\)




\begin{equation*}
2x+3(2)-3=5\Rightarrow x = 1\text{.}
\end{equation*}



to give us the unique solution \(\left(\begin{array}{c}x\\y\\z\end{array}\right) = \left(\begin{array}{c}1\\2\\3\end{array}\right)\) to the row-echelon system (3.1.11). By Theorem 3.1.29 this is the unique solution to the original system (3.1.10) as well.



Example 3.1.35. Using elimination to determine the consistency of a wide system.

Use elimination to determine how many solutions the \(3\times4\) linear system below has.

\begin{equation*}
\begin{array}{rcrcrcrcrr}
x  \amp - \amp 2y  \amp + \amp 3z \amp - \amp w \amp=\amp -4\\
4x \amp - \amp 11y \amp + \amp 18z \amp + \amp w \amp =\amp 2\\
-2x \amp + \amp 10y \amp - \amp 18z \amp  \amp  \amp =\amp 4
\end{array}\text{.}
\end{equation*}





Performing elimination on the corresponding augmented matrix yields



\begin{align*}
\left(\begin{array}{rrrr|r}1 \amp -2\amp 3\amp -1\amp -4\\
4\amp -11\amp 18\amp 1 \amp 2\\
-2\amp 10\amp -18\amp 0 \amp 4\end{array}\right)\!\!\!\amp\underset{2R_1+R_3\rightarrow R_3}{\xrightarrow{-4R_1+R_2\rightarrow R_2}}\!\!\!\left(\begin{array}{rrrr|r}1 \amp -2\amp 3\amp -1 \amp -4\\
0 \amp -3 \amp 6\amp 5\amp 18\\
0 \amp 6 \amp -12\amp -2\amp -4\end{array}\right)\\
\!\!\!\amp \xrightarrow{2R_2+R_3\rightarrow R_3}\left(\begin{array}{rrrr|r}1 \amp -2\amp 3\amp -1\amp -4\\
0 \amp -3 \amp 6\amp 5\amp 18\\
0\amp 0\amp 0\amp 8\amp 32\end{array}\right)
\end{align*}



 
The augmented system has a full set of pivots, so by Corollary 3.1.12 is consistent and has an infinite number of solutions. Hence by Theorem 3.1.29 the original system is consistent and has an infinite number of solutions as well.
The system in Example 3.1.35 has an infinite set of individual solutions, a property of every consistent wide system. The process of using elimination to solve such systems is studied in detail in Subsection 6.1.1 and Section 3.4.



Example 3.1.36. When elimination reveals an inconsistent system.



Determine whether the \(3\times 3\) linear system below is consistent or inconsistent by using elimination. If it is consistent, find the solution vector.



\begin{equation*}
\begin{array}{rcrcrcrr}
x  \amp - \amp y  \amp + \amp z \amp=\amp -2\\
x \amp + \amp y \amp + \amp z\amp =\amp 0\\
3x \amp + \amp y \amp + \amp 3z \amp =\amp 1
\end{array}\text{.}
\end{equation*}



 


Performing elimination on the corresponding augmented matrix yields



\begin{align*}
\left(\begin{array}{rrr|r}1 \amp -1\amp 1\amp -2\\
1\amp 1\amp 1\amp 0\\
3\amp 1\amp 3\amp 1\end{array}\right)\!\!\!\amp\underset{-3R_1+R_3\rightarrow R_3}{\xrightarrow{-R_1+R_2\rightarrow R_2}}\!\!\!\left(\begin{array}{rrr|r}1 \amp -1\amp 1\amp -2 \\
0 \amp 2 \amp 0\amp 2\\
0 \amp 4 \amp 0\amp 7\end{array}\right)\\
\!\!\!\amp \xrightarrow{-2R_2+R_3\rightarrow R_3}\left(\begin{array}{rrr|r}1 \amp -1\amp 1\amp -2\\
0 \amp 2 \amp 0\amp 2\\
0\amp 0\amp 0\amp 3\end{array}\right)
\end{align*}



 



\begin{equation*}
R_3:\,0 = 3\text{.}
\end{equation*}



This means that our implicit assumption that the system has a solution (see Theorem 3.1.29) implies that \(0=3\) which is absurd.  Thus the assumption that the system has a solution is incorrect, and we conclude that the system has no solutions.



Example 3.1.37. When would we use a row swap?



Suppose we needed to perform elimination on the following system.



\begin{equation*}
\left(\begin{array}{rrr|r}0\amp 2\amp -1\amp 1\\4\amp 1\amp -5\amp -13\\5\amp 0\amp -3\amp 12\end{array}\right)\text{.}
\end{equation*}



 


We cannot begin the elimination unless the \(1,1\)-entry is a pivot, but \(A_{11}=0.\) To remedy this, we we employ either of two row swaps



\begin{equation*}
\begin{array}{llc}\left(\begin{array}{rrr|r}0\amp 2\amp -1\amp 1\\4\amp 1\amp -5\amp -13\\5\amp 0\amp -3\amp 12\end{array}\right)\amp\xrightarrow{R_1\leftrightarrow R_2}\amp\left(\begin{array}{rrr|r}4\amp 1\amp -5\amp -13\\0\amp 2\amp -1\amp 1\\5\amp 0\amp -3\amp 12\end{array}\right).\end{array}
\end{equation*}



or



\begin{equation*}
\begin{array}{llc}\left(\begin{array}{rrr|r}0\amp 2\amp -1\amp 1\\4\amp 1\amp -5\amp -13\\5\amp 0\amp -3\amp 12\end{array}\right)\amp\xrightarrow{R_1\leftrightarrow R_3}\amp\left(\begin{array}{rrr|r}5\amp 0\amp -3\amp 12\\4\amp 1\amp -5\amp -13\\0\amp 2\amp -1\amp 1\end{array}\right).\end{array}
\end{equation*}



In either case after the swap we may begin elimination as usual.


Proof.
The proof is a homework exercise.

Subsection 3.1.4 Gauss-Jordan Elimination




Remark 3.1.39. Reduced row-echelon form and Gauss-Jordan elimination.



We may take elimination even further. Suppose we have eliminated \(\A\x=\b\) to \(\U\x=\vec{c}\) and have found \(\U\x=\vec{c}\) is consistent. 
    

  1. We discard any full zero rows and then eliminate above any pivots, and finally divide each pivot row by its pivot. The end result of this process is the reduced row-echelon form of the system, or RREF, denoted \(\left(\J|\vec{d}\right).\)

    2. 

  2. Unless otherwise indicated \(\J\) will always denote an RREF matrix. Each pivot column in \(\J\) is a canonical unit vector.
    3. 

  3. Putting a matrix into its RREF accomplishes both elimination and back substitution as a sequence of row operations.
    4. 

  4. The process of using valid row operations to convert \(\left(\A|\b\right)\) to the RREF is called Gauss-Jordan elimination. In Gauss-Jordan elimination we call 1) row operations in which we eliminate below pivots elimination steps, and 2) row operations in which we eliminate above pivots substitution steps.

    5. 

  5. The benefit of RREF over elimination and back-substitution is the continued efficiency of using augmented matrices and row-op notation, and the drawback is that in each substitution step of Gauss-Jordan elimination we continue to transcribe unaffected rows, an inefficiency.
    6. 

  6. To keep the computations as simple as possible, delaying the appearance of fractions is a priority. When dividing a pivot row by its pivot introduces fractions into that row, it’s best to wait until the last step to divide that pivot row by its pivot.
    7. 

  7. Though a row-echelon form of a matrix or linear system is not unique, the RREF of the matrix or linear system is unique.
    8. 

  8. An RREF system / matrix is in row-echelon form.
    9. 


Example 3.1.41. Efficient solution of Example 3.1.34 using row-op notation and Gauss-Jordan elimination.

Here, by using row-op notation, we concisely express the solution path in Example 3.1.34. We restate the problem first: 


Determine whether the \(3\times 3\) linear system below is consistent or inconsistent by using elimination. If it is consistent, find the solution vector.



\begin{equation*}
\begin{array}{rcrcrcrr}
2x  \amp + \amp 3y  \amp -  \amp z \,\amp=\amp 5\\
x \amp + \amp y \amp - \amp z \amp =\amp0\\
3x \amp - \amp  y \amp + \amp 2z \amp =\amp 7
\end{array}\text{.}
\end{equation*}



 



Solution: Performing Gauss-Jordan elimination on the corresponding augmented matrix yields



\begin{equation*}
\begin{array}{llc}\left(\begin{array}{rrr|r}2\amp 3\amp -1\amp 5\\1\amp 1\amp -1\amp 0\\3\amp -1\amp 2\amp 7\end{array}\right)\amp\underset{3R_1-2R_3\rightarrow R_3}{\xrightarrow{R_1-2R_2\rightarrow R_2}}\amp\left(\begin{array}{rrr|r}2\amp 3\amp -1\amp 5\\0\amp 1\amp 1\amp 5\\0\amp 11\amp -7\amp 1\end{array}\right)\\
\amp \xrightarrow{-11R_2+R_3\rightarrow R_3}\amp\left(\begin{array}{rrr|r}2\amp 3\amp -1\amp 5\\0\amp 1\amp 1\amp 5\\0\amp 0\amp -18\amp -54\end{array}\right)\\
\amp \xrightarrow{-\frac{1}{18}R_3\rightarrow R_3}\amp\left(\begin{array}{rrr|r}2\amp 3\amp -1\amp 5\\0\amp 1\amp 1\amp 5\\0\amp 0\amp 1\amp 3\end{array}\right)\\
\amp \underset{R_3+R_1\rightarrow R_1}{\xrightarrow{-R_3+R_2\rightarrow R_2}}\amp\left(\begin{array}{rrr|r}2\amp 3\amp 0\amp 8\\0\amp 1\amp 0\amp 2\\0\amp 0\amp 1\amp 3\end{array}\right)\\
\amp \xrightarrow{-3R_2+R_1\rightarrow R_1}\amp\left(\begin{array}{rrr|r}2\amp 0\amp 0\amp 2\\0\amp 1\amp 0\amp 2\\0\amp 0\amp 1\amp 3\end{array}\right)\\
\amp \xrightarrow{\frac{1}{2}R_1\rightarrow R_1}\amp\left(\begin{array}{rrr|r}1\amp 0\amp 0\amp 1\\0\amp 1\amp 0\amp 2\\0\amp 0\amp 1\amp 3\end{array}\right).\end{array}
\end{equation*}



The solution \(\left(\begin{array}{c}x\\y\\z\end{array}\right) = \left(\begin{array}{c}1\\2\\3\end{array}\right)\) to this system is evident. By Theorem 3.1.29 \(\left(\begin{array}{c}1\\2\\3\end{array}\right)\) solves the original system as well.



Example 3.1.42. Another example of solving a consistent square system.



Determine whether the \(3\times 3\) linear system below is consistent or inconsistent by using elimination. If it is consistent, find the solution vector.



\begin{equation*}
\begin{array}{rcrcrcrr}
3x \amp - \amp  y \amp  + \amp  5z \amp = \amp -4\\
2x \amp + \amp  y \amp  + \amp  6z \amp = \amp  5\\
5x \amp - \amp 3y \amp + \amp 9z \amp = \amp -10
\end{array}\text{.}
\end{equation*}



 



Solution: Performing Gauss-Jordan elimination on the corresponding augmented matrix yields



\begin{equation*}
\begin{array}{llc}\left(\begin{array}{rrr|r}3\amp -1\amp 5\amp -4\\2\amp 1\amp 6\amp 5\\5\amp -3\amp 9\amp -10\end{array}\right)\amp\underset{-5R_1+3R_3\rightarrow R_3}{\xrightarrow{2R_1-3R_2\rightarrow R_2}}\amp\left(\begin{array}{rrr|r}3\amp -1\amp 5\amp -4\\0\amp -5\amp -8\amp -23\\0\amp -4\amp 2\amp -10\end{array}\right)\\
\amp \xrightarrow{-4R_2+5R_3\rightarrow R_3}\amp\left(\begin{array}{rrr|r}3\amp -1\amp 5\amp -4\\0\amp -5\amp -8\amp -23\\0\amp 0\amp 42\amp 42\end{array}\right)\\
\amp \xrightarrow{\frac{1}{42}R_3\rightarrow R_3}\amp\left(\begin{array}{rrr|r}3\amp -1\amp 5\amp -4\\0\amp -5\amp -8\amp -23\\0\amp 0\amp 1\amp 1\end{array}\right)\\
\amp \underset{-5R_3+R_1\rightarrow R_1}{\xrightarrow{8R_3+R_2\rightarrow R_2}}\amp\left(\begin{array}{rrr|r}3\amp -1\amp 0\amp -9\\0\amp -5\amp 0\amp -15\\0\amp 0\amp 1\amp 1\end{array}\right)\\
\amp \xrightarrow{-\frac{1}{5}R_2\rightarrow R_2}\amp\left(\begin{array}{rrr|r}3\amp -1\amp 0\amp -9\\0\amp 1\amp 0\amp 3\\0\amp 0\amp 1\amp 1\end{array}\right)\\
\amp \xrightarrow{R_2+R_1\rightarrow R_1}\amp\left(\begin{array}{rrr|r}3\amp 0\amp 0\amp -6\\0\amp 1\amp 0\amp 3\\0\amp 0\amp 1\amp 1\end{array}\right)\\
\amp \xrightarrow{\frac{1}{3}R_1\rightarrow R_1}\amp\left(\begin{array}{rrr|r}1\amp 0\amp 0\amp -2\\0\amp 1\amp 0\amp 3\\0\amp 0\amp 1\amp 1\end{array}\right).\end{array}
\end{equation*}



The solution \(\left(\begin{array}{r}x\\y\\z\end{array}\right) = \left(\begin{array}{r}-2\\3\\1\end{array}\right)\) to this system is evident. By Theorem 3.1.29 \(\left(\begin{array}{r}-2\\3\\1\end{array}\right)\) solves the original system as well.



Subsection 3.1.5 Application - finding the unique polynomial through \(\boldsymbol{n}\) points in \(\boldsymbol{\R^2}\)





In this short section we set up and show how to solve equations to construct the unique line through two given points in \(\R^2\) and the unique parabola through three given points in \(\R^2.\)

Remark 3.1.43.

The determination of the unique line is perhaps the foundational toy problem in linear algebra. The description of a general non-vertical line

\begin{equation*}
\left\{\left.(x,y)\in\R^2\right|y=mx+b\right\}
\end{equation*}

contains four variables - \(y,x,m,\) and \(b.\) The requirement that the line pass through a given pair of points \((x_1,y_1),(x_2,y_2)\in\R^2\) where \(x_1\ne x_2\) leads to two equations in the two unknowns \(m,b:\)

\begin{align*}
mx_1+b\amp =y_1\\
mx_2+b\amp =y_2.
\end{align*}

These equations may be solved algebraically for \(m,b\) to obtain a two-variable equation, like \(y=3x-5\) which still exhibits two variables allowing the equation to describe the full line in \(\R^2\) as \(x\) varies through all of \(\R.\) 


For example, suppose we wish to find the equation \(y=mx+b\) of the line passing through each of \((1,5)\) and \((3,1).\) The resulting equations are



\begin{align*}
m+b\amp =5\\
3m+b\amp =1
\end{align*}



which may be expressed as



\begin{equation*}
\left(\begin{array}{cc}1\amp1\\3\amp1\end{array}\right)\left(\begin{array}{c}m\\ b\end{array}\right)=\left(\begin{array}{c}5\\1\end{array}\right)
\end{equation*}



and solved by Gaussian elimination or using the matrix inverse.



Remark 3.1.44.

Applying the same analysis, we may determine the unique quadratic \(y=ax^2+bx+c\) passing through three given points \((x_1,y_1),(x_2,y_2),(x_3,y_3)\in\R^2\) where none of the \(x_i\)’s are equal. In this case we obtain three equations in the three unknowns \(a,b,c:\)

\begin{align*}
ax_1^2+bx_1+c\amp =y_1\\
ax_2^2+bx_2+c\amp =y_2\\
ax_3^2+bx_3+c\amp =y_3
\end{align*}

which can easily be solved by Gaussian elimination.

Subsection 3.1.6 Tall systems





Every tall system is either 1) inconsistent (to be determined through elimination), or 2) reduces to a square system or a wide system after discarding full zero rows, as follows.


In the representation below, a general tall linear system is put in row-echelon form and all zero rows and LHS-only zero rows are grouped together at the bottom. The \(\times\)’s denote entries which may be nonzero. Evidently, an \(m\times n\) row-echelon linear system \(\U\x=\vec{c}\) there can be no more than \(\min\{m,n\}\) pivots. Therefore, in a tall system there will be no more than \(n\) pivots and hence \(n\) pivot rows.



\begin{equation*}
\left(\begin{array}{ccccc|c}\times\amp \times\amp\cdots\amp \times\amp \times\amp\times\\ \times\amp \times\amp\cdots\amp \times\amp \times\amp\times\\ \times\amp \times\amp \cdots\amp\times\amp\times\amp\times\\ \amp \amp \vdots\amp  \amp\amp\vdots\\ \times\amp \times\amp \cdots\amp\times\amp\times\amp\times\\ \times\amp \times\amp \cdots\amp\times\amp\times\amp\times\\ \amp \amp \vdots\amp  \amp\amp\vdots\\ \times\amp \times\amp\cdots\amp \times\amp\times\amp\times\end{array}\right)
\longrightarrow
\left(\begin{array}{ccccc|c}\times\amp \times\amp\cdots\amp \times\amp \times\amp\times\\0\amp \times\amp\cdots\amp \times\amp \times\amp\times\\ 0\amp 0\amp \cdots\amp\times\amp\times\amp\times\\  \amp \amp \vdots\amp  \amp\amp\vdots\\  0\amp 0\amp \cdots\amp0\amp\times\amp\times\\0\amp 0\amp\cdots\amp 0\amp0\amp\times\\  \amp \amp \vdots\amp  \amp\amp\vdots\\ 0\amp 0\amp\cdots\amp 0\amp0\amp\times\end{array}\right)
\end{equation*}



So, for tall systems there must be at least \(m-n\) zero rows or LHS-only zero rows in \(\U\x=\vec{c}.\) If any of these are LHS-only zero rows, the system \(\U\x=\vec{c}\) is inconsistent and by Theorem 3.1.29 \(\A\x=\b\) is inconsistent.


If on the other hand there are no LHS-only zero rows in \(\left(\U|\vec{c}\right),\) discarding all full zero rows leaves either a square system or a wide system.



\begin{equation*}
\left(\begin{array}{ccccc|c}\times\amp \times\amp\cdots\amp \times\amp \times\amp\times\\0\amp \times\amp\cdots\amp \times\amp \times\amp\times\\ 0\amp 0\amp \cdots\amp\times\amp\times\amp\times\\  \amp \amp \vdots\amp  \amp\amp\vdots\\  0\amp 0\amp \cdots\amp0\amp\times\amp\times\\0\amp 0\amp\cdots\amp 0\amp0\amp0\\  \amp \amp \vdots\amp  \amp\amp\vdots\\ 0\amp 0\amp\cdots\amp 0\amp0\amp0\end{array}\right)
\longrightarrow
\left(\begin{array}{ccccc|c}\times\amp \times\amp\cdots\amp \times\amp \times\amp\times\\0\amp \times\amp\cdots\amp \times\amp \times\amp\times\\ 0\amp 0\amp \cdots\amp\times\amp\times\amp\times\\  \amp \amp \vdots\amp  \amp\amp\vdots\\  0\amp 0\amp \cdots\amp0\amp\times\amp\times\end{array}\right)
\end{equation*}



So the study of a given tall system reduces to a determination of whether the system is consistent and if so whether there is a unique solution or an infinitude of solutions to the resulting square or wide system.



PrevTopNext