A simple model of traffic flow can be represented by the following graph:
Write down the equations that balance each of the numbers of cars entering and leaving each of the intersections \(A, B, C\) and \(D\text{.}\)
Section 1.3 Matrices and Matrix Reduction
Matrices are generally presented in either a linear algebra or matrix methods class. The material presented here is some basics behind matrices that are needed for performing linear optimization. This should be review for most readers of the text, but is helpful for the context and notation later in the text.
Subsection 1.3.1 Linear Systems
Let’s start with an example.
Example 1.3.1. Traffic Flow.
Definition 1.3.3.
-
A linear combination of \(x_1, x_2, x_3, \ldots, x_n\) has the form\begin{equation*} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n, \end{equation*}where the constants \(a_1, a_2, \ldots, a_n \in \mathbb{R}\) are the combinations coefficients.
-
A linear equation has the form\begin{equation} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b\tag{1.3.2} \end{equation}where \(b \in \mathbb{R}\) is a constant and \(a_1, a_2, \ldots, a_n \in \mathbb{R}\text{.}\) These are the lines, planes and hyperplanes discussed in Section 1.1.
-
The \(n\)-tuple \((s_1,s_2,\ldots,s_n)\) satisfies or is a solution of (1.3.2) if this point satisfies (1.3.2) or\begin{equation*} a_1 s_1 + a_2 s_2 + \cdots + a_n s_n = b \end{equation*}
-
A system of linear equations or linear system is a set of linear equations:\begin{align} a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n \amp = b_1 , \notag\\ a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n \amp = b_2, \tag{1.3.3}\\ \vdots \amp = \vdots \notag\\ a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n \amp = b_m, \notag \end{align}and this linear system has \(m\) equations and \(n\) unknowns (variables). The equations in (1.3.1) is an example of a linear system.
Example 1.3.4. Linear Equations.
The following are linear equations:
\begin{align*}
2x + 3y \amp = 6, \amp y_1 -y_2+y_3-y_4 \amp = 10, \\
10x_1 - x_3 + 5x_5 \amp = 9, \amp \sum_{i=1}^{10} i x_i \amp = 0
\end{align*}
where summation notation has been used in the last one and note the variable names can vary. The following equations are not linear:
\begin{align*}
x_1^2+x_2 \amp = 6, \amp y_1y_2 + y_3 \amp = 5, \\
\frac{x_1+x_2}{x_3} \amp = 6, \amp \sin(x+y) \amp = z
\end{align*}
Each of the equations in the latter group have multiplications, squares, division or other functions between variables.
The next two examples give a way to determine if a point or \(n\)-tuple is a solution to a linear system.
Example 1.3.5. Showing a Point is a Solution to a Linear System.
Show that the point \((2,3)\) is a solution of the linear system:
\begin{align*}
3x_1 - x_2 \amp = 3 \\
2x_1 + 4x_2 \amp = 16
\end{align*}
Example 1.3.6.
Show that \((200,500, 100, 250, 200)\) and \((200, 450, 150, 200, 250)\) are both solutions to the linear system in (1.3.1).
Solution.
In each case, the values must satisfy each equation. In the first case:
\begin{equation*}
\begin{aligned} 250 + 200 \amp = 200 + 250, \\ 350 \amp = 100 + 250, \\ 700 \amp = 500 + 200, \\ 100 + 500 \amp = 600, \end{aligned}
\end{equation*}
and since equation equation is satisfied, it is a solution. In the second case:
\begin{equation*}
\begin{aligned} 200 + 250 \amp = 200 + 250 \\ 350 \amp = 150 + 200 \\ 700 \amp = 450 + 250 \\ 150 + 450 \amp = 600 \end{aligned}
\end{equation*}
and again, each equation is satisfied.
This shows that the linear system in (1.3.1) has more than one solution. In this case, there are different traffic levels that satisfy the equations.
Subsection 1.3.2 Elementary Row Operations
We now seek a method to solve the above linear systems (and any linear system). Gauss’ method and variations of it are the standard ways that all large linear systems are solved presently. The next section shows how to systematically solve a linear system using rules of algebra that keep linear equations linear.
Consider the following example of two linear equations:
\begin{align}
x+2y+3z \amp =6 \tag{1.3.4}\\
-2x+3y-z \amp =4 \tag{1.3.5}
\end{align}
We seek to find operations on these equations that keep these equations linear and don’t change the solution. First, the order that we wrote them down doesn’t matter and we could swap these equations as in:
\begin{align*}
-2x+3y-z \amp =4 \\
x+2y+3z \amp =6
\end{align*}
The second possible operation is to multiply a single equation by a constant. For example, if we multiply (1.3.4) by 2, we get the system:
\begin{align*}
2x+4y+6z \amp =12 \\
-2x+3y-z \amp =4
\end{align*}
The third operation is that we can add two equations and the replace one of the equations with the sum. For example adding (1.3.4) and (1.3.5) and putting the sum in the 2nd row results in
\begin{align*}
x+2y+3z \amp =6 \\
-x+5y+2z \amp =10
\end{align*}
A more common operation is to combine the last two operations and that is to multiply an equation by a constant and add to another. If we multiply (1.3.4) by 2 and add to (1.3.5) we get the system:
\begin{align*}
x+2y+3z \amp =6 \\
7y + 5z \amp = 16
\end{align*}
Definition 1.3.7. Elementary Row Operations.
The three operations
-
Two equations of the linear system are swapped,
-
An equation is multiplied by a nonzero number,
-
An equation is replaced by the sum of itself and a multiple of another equation,
are called the elementary row operations of a linear system.
Subsubsection 1.3.2.1 Gauss’s Method
The following example shows how to use the elementary row operations seen above to solve a linear system with a technique called Gauss’s Method.
\begin{align*}
x -2y + 3z \amp = 6, \\
2x + 2y\phantom{+3z} \amp = 6, \\
-3x \phantom{+2y}+\phantom{3} z \amp = 0.
\end{align*}
If one equation had only one variable, it would be quite easy to find the solution to that equation. The following steps will result in such a system. For example, if the first equation is multiplied by \(-2\) and added to the second equation and the second equation is replaced (which we denote with \(-2R_1+R_2 \rightarrow R_2\)), then the above equations are replaced with
\begin{align*}
\amp \amp x -2y + 3z \amp = 6, \\
-2R_1+R_2 \rightarrow R_2\qquad\amp \amp 6 y-6z \amp = -6, \\
\amp \amp -3x \phantom{+2y}+\phantom{3} z \amp = 0.
\end{align*}
Next, we’d like to get rid of the \(x\) term in the 3rd equation. We can do that by multiplying the first equation by 3 and adding to the 3rd and writing down this operation as well we get:
\begin{align*}
\amp \amp x -2y + \phantom{1}3z \amp = 6, \\
3R_1+R_3 \rightarrow R_3\quad \amp \amp 6 y-\phantom{1}6z \amp = -6, \\
\amp \amp -6y+10z \amp = 18.
\end{align*}
Next we will eliminate the \(y\) term in the 3rd equation. We can do that by adding equations 2 and 3 and putting the result in equation 3.
\begin{align}
\amp \amp x -2y + 3z \amp = 6, \notag\\
R_2+R_3 \rightarrow R_3\quad \amp \amp 6 y-6z \amp = -6 \tag{1.3.6}\\
\amp \amp 4z \amp = 12. \notag
\end{align}
At this point we can solve for \(z\) in the third equation of (1.3.6) to get \(z=3\text{.}\) From this, plug in \(z=3\) into the second equation of (1.3.6) to get
\begin{align*}
6y -6(3) \amp = -6 \\
6y \amp = 12 \\
y \amp = 2
\end{align*}
\begin{align*}
x-2(2)+3(3)\amp = 6 \\
x-4+9\amp = 6 \\
x \amp = 1
\end{align*}
therefore, \(x=1\text{.}\) The point \((1,2,3)\) is a solution to linear system. Because this is the only point that satisfies all equations, this point is unique. We will also use the terminology triple to describe \((1,2,3)\text{.}\)
Theorem 1.3.8. Gauss’s Method.
If a linear system (\(A\)) is changed into a second linear system (\(B\)) by one of the elementary row operations then linear systems (\(A\)) and (\(B\)) have the same set of solutions.
Proof.
We will consider only the first operation in this proof. Let’s assume that we swap equations \(i\) and \(j\text{,}\) thus system (\(A\)),
\begin{align*}
a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n \amp = b_1 , \\
a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n \amp = b_2, \\
\vdots \qquad \qquad \amp \vdots \\
a_{i,1} x_1 + a_{i,2} x_2 + \cdots + a_{i,n} x_n \amp = b_i, \\
\vdots \qquad \qquad \amp \vdots \\
a_{j,1} x_1 + a_{j,2} x_2 + \cdots + a_{j,n} x_n \amp = b_j, \\
\vdots \qquad \qquad \amp \vdots \\
a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n \amp = b_m,
\end{align*}
is transformed to
\begin{align*}
a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n \amp = b_1 , \\
a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n \amp = b_2, \\
\vdots \qquad \qquad \amp \vdots \\
a_{j,1} x_1 + a_{j,2} x_2 + \cdots + a_{j,n} x_n \amp = b_j, \\
\vdots \qquad \qquad \amp \vdots \\
a_{i,1} x_1 + a_{i,2} x_2 + \cdots + a_{i,n} x_n \amp = b_i, \\
\vdots \qquad \qquad \amp \vdots \\
a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n \amp = b_m,
\end{align*}
Let \((s_1,s_2, \ldots, s_n)\) be a solution of (\(A\)) if it exists and note it may be one of many \(n\)-tuples in the solution. Thus it satisfies each equation of linear system (\(A\)). Since the exact same equations are in (\(B\)) in just a different order, \((s_1,s_2,\ldots,s_n)\) is a solution to (\(B\)). If there is more than one \(n\)-tuple in the solution to (\(A\)), repeat this for every one. If there is no solution to (\(A\)), then there will be no solution to (\(B\)) since it is the same set of equations.
Proof of #2 and #3 above are quite similar and are not shown.
Note 1.3.9.
Although Gauss’ Method is very flexible, generally, one tries to eliminate all \(x_1\) terms in all equations below equation 1, \(x_2\) terms in all equations below equation 2 and so on.
Subsection 1.3.3 Matrices
When we solved a linear system above, you probably noticed that the variables didn’t play much of a role, the coefficients changed and the variables stayed in the same place as we solved for them. Because of this, we will adopt that technique to only works with the coefficients. We first define a matrix that we will use to solve linear systems for the rest of this book.
Definition 1.3.10.
An \(m\) by \(n\) matrix is a rectangular grid of numbers with \(m\) rows and \(n\) columns. The size of a matrix is the pair of number \(m\) and \(n\) and is typically written \(m\) by \(n\) or \(m \times n\text{.}\) Each number of the matrix is called the entry or element.
Example 1.3.11. Matrices.
The following are examples of matrices:
\begin{equation*}
\begin{bmatrix} 1 \amp 2 \amp 3 \\ 4 \amp 5 \amp 6 \end{bmatrix} \qquad \begin{bmatrix} \pi \amp 2 \\ -1 \amp 4 \\ 2.5 \amp 7/3 \\ -11 \amp 1000 \end{bmatrix} \qquad \begin{bmatrix} 2 \\ 4 \\ 6 \\ 8 \\ 9 \end{bmatrix} \qquad \begin{bmatrix} 8 \amp -3 \amp 2 \end{bmatrix}
\end{equation*}
A common notation for a matrix is to use upper case letters (and often bold), for example \(A\text{,}\) \(B\) and \(C\) are common matrices. The entry or element in the \(i\)th row and \(j\)th column of \(A\) is \(a_{i,j}\text{.}\) Also, the set of all \(m\) by \(n\) matrices is denoted \({\cal M}_{m \times n}\text{.}\)
Definition 1.3.12.
A matrix with only 1 row is called a row vector. A matrix with only 1 column is called a column vector. The size of a vector is the number of rows (for a column vector) or the number of columns (for a row vector).
The 3rd matrix in Example 1.3.11 above is a column vector of size 5. The 4th matrix is a row vector of size 3. Vectors are very important and will see them throughout this book.
Subsection 1.3.4 Matrices and Linear Systems
Let’s look at the following linear system.
\begin{align*}
x + 2y \amp = 7, \\
4x -3 y \amp = 6.
\end{align*}
We will write the coefficients of the variables and the right hand side in a matrix called an an augmented coefficient matrix. The following is this matrix for the linear system above.
\begin{equation*}
\left[ \begin{array}{rr|r} 1 \amp 2 \amp 7 \\ 4 \amp -3 \amp 6 \\ \end{array} \right]
\end{equation*}
and the two rows of the matrix represent the two equations. The first column represents the coefficient of the \(x\) variable, and the second column represents the coefficient of the \(y\) variable. The last column is the right hand sides of the linear system, and the vertical line occurs where the equal sign is in the equations.
Example 1.3.13. Linear System as an Augmented Matrix.
Write down the following linear system as an augmented matrix:
\begin{align*}
3x -2 y + z \amp = 11, \\
2x + 4y -3z \amp = 2, \\
-4x + y + 4z \amp = 0.
\end{align*}
And the next example shows how to rewrite a matrix as a linear system.
Example 1.3.14. Augmented Matrix as a Linear System.
Write down the following augmented matrix as a linear system:
\begin{equation*}
\left[ \begin{array}{rrr|r} 3 \amp 0 \amp -1 \amp 7 \\ -2 \amp 1 \amp 5 \amp 6 \\ 0 \amp 3 \amp 4 \amp 8 \\ \end{array} \right]
\end{equation*}
Solution.
In this case, we are doing the opposite of the step above. That is, take a matrix and find the linear system.
Since the matrix has 4 columns, there are 3 variables (the last column is the right hand side). Let’s use \(x\text{,}\) \(y\) and \(z\text{.}\)
\begin{align*}
3x + 0 y - z \amp = 7 \\
-2x + y + 5z \amp = 6 \\
0x + 3y + 4 z \amp = 8
\end{align*}
Subsection 1.3.5 Row Operations and Matrices
We can perform the same row operations that we have seen above on matrices.
- Row Swap
- Multiply by a number
- Multiply by a number and add to another
- \(cR_i + R_j\) multiplies row \(i\) by \(c\) and adds to row \(j\text{.}\) The notation \(cR_i + R_j \to R_j\) is also used.
In the next section, we will formalize the solving of linear system using matrices, however, the last example here reproduces the same solution technique for the example in Subsubsection 1.3.2.1.
Example 1.3.15.
Solve the linear system
\begin{align*}
x -2y + 3z \amp = 6, \\
2x + 2y\phantom{+3z} \amp = 6, \\
-3x \phantom{+2y}+\phantom{3} z \amp = 0.
\end{align*}
by first writing as an augmented coefficient matrix and then performing elementary row operations on the matrix.
Solution.
First, the augmented coefficient matrix is
\begin{equation*}
\left[\begin{array}{rrr|r} 1 \amp -2 \amp 3 \amp 6 \\ 2 \amp 2 \amp 0 \amp 6 \\ -3 \amp 0 \amp 1 \amp 0 \end{array}\right]
\end{equation*}
Now perform the same elementary row operations as above. We first seek to change the second row, first column to a 0
\begin{equation*}
-2 R_1 + R_2 \to R_2 \qquad \left[\begin{array}{rrr|r} 1 \amp -2 \amp 3 \amp 6 \\ 0 \amp 6 \amp -6 \amp -6 \\ -3 \amp 0 \amp 1 \amp 0 \end{array}\right]
\end{equation*}
and notice that this is the matrix representation of the second step in the solution listed in Subsubsection 1.3.2.1. Next, we seek to change the 3rd row, first column from \(-3\) to a 0.
\begin{equation*}
3 R_1 + R_3 \to R_3 \qquad \left[\begin{array}{rrr|r} 1 \amp -2 \amp 3 \amp 6 \\ 0 \amp 6 \amp -6 \amp -6 \\ 0 \amp -6 \amp 10 \amp 18 \end{array}\right]
\end{equation*}
And since we seek to get only a single variable in the third row, only one more step is needed.
\begin{equation*}
R_2 + R_3 \to R_3 \qquad \left[\begin{array}{rrr|r} 1 \amp -2 \amp 3 \amp 6 \\ 0 \amp 6 \amp -6 \amp -6 \\ 0 \amp 0 \amp 4 \amp 12 \end{array}\right]
\end{equation*}
At this point, if we return the augmented matrix to a set of equations, we get
\begin{align*}
x - 2y + 3z \amp = 6 \\
6y - 6z \amp = -6\\
4z \amp = 12
\end{align*}
and we can get the same solution using the same steps as above to get \(z=3, y=2, x=1\) .
We will see in the next section that actually if we continue working with the matrix, we can more easily find the solution as well as find solutions for a broader range of linear systems.
Example 1.3.16.
Solve
\begin{equation}
\left[\begin{array}{rrr|r} -4 \amp 1 \amp -2 \amp 5\\ 3 \amp -1 \amp 0 \amp 2\\ 1 \amp 0 \amp -3 \amp -3\\ \end{array} \right]\tag{1.3.7}
\end{equation}
using Gauss-Jordan Elimination
Solution.
If this is done "by hand", one would probably swap rows 1 and 4 to get a 1 in the upper left, however let’s skip and get a 1 there by dividing through by \(-4\text{,}\) then eliminate the rest of the column:
\begin{equation*}
\begin{array}{r} -\frac{1}{4} R_1 \to R_1, \\ -3 R_1 + R_2 \to R_2, \\ -R_1 + R_3 \to R_3 \end{array} \qquad \left[\begin{array}{rrr|r} 1 \amp -1/4 \amp 1/2 \amp -5/4\\ 0 \amp -1/4 \amp -3/2 \amp 23/4\\ 0 \amp 1/4 \amp -7/2 \amp -7/4\\ \end{array} \right]
\end{equation*}
Typically we now want to get a 1 in the 2nd row, 2nd column of the matrix and can be done by multiplying row 2 by \(-4\) and then eliminating the rest of the column with
\begin{equation*}
\begin{array}{r} -4 R_2 \to R_2, \\ \frac{1}{4} R_2 + R_1 \to R_1, \\ -\frac{1}{4} R_2 + R_3 \to R_3, \end{array} \qquad \left[\begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp -7\\ 0 \amp 1 \amp 6 \amp -23\\ 0 \amp 0 \amp -5 \amp 4\\ \end{array} \right]
\end{equation*}
Lastly, we will make row 3, column 3 a 1 and then use this to eliminate the rest of the 3rd column with
\begin{equation}
\begin{array}{r} -\frac{1}{5} R_3 \to R_3, \\ -2 R_3 + R_1 \to R_1, \\ -6 R_3 + R_2 \to R_2, \\ \end{array} \qquad \left[\begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp -27/5\\ 0 \amp 1 \amp 0 \amp -91/5\\ 0 \amp 0 \amp 1 \amp -4/5\\ \end{array} \right]\tag{1.3.8}
\end{equation}
And this reveals the solution is the vector \(\begin{bmatrix} -27/5 \amp -91/5 \amp -4/5 \end{bmatrix}^{\intercal}\)
Checkpoint 1.3.17.
Put the linear system from (1.3.1) in a augmented coefficient matrix and use row operations to put the matrix in reduced row-echelon form.
Solution.
First, ensure that all of the variables are on the left of the equations in (1.3.1) and the constants on the right. This can be written as the augmented coefficient matrix,
\begin{equation*}
\left[\begin{array}{rrrrr|r} -1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 250 \\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350 \\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700 \\ 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 600 \end{array}\right]
\end{equation*}
Row operations are now performed
\begin{align*}
-R_1 \to R_1 \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp -1 \amp -1 \amp -250\\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 600\\ \end{array} \right] \\
R_2 \leftrightarrow R_3 \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp -1 \amp -1 \amp -250\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350\\ 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 600\\ \end{array} \right] \\
-R_2 + R_4 \to R_4 \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp -1 \amp -1 \amp -250\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350\\ 0 \amp 0 \amp 1 \amp 0 \amp -1 \amp -100\\ \end{array} \right] \\
-R_3 + R_4 \to R_4 \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp -1 \amp -1 \amp -250\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350\\ 0 \amp 0 \amp 0 \amp -1 \amp -1 \amp -450\\ \end{array} \right] \\
-R_4 \to R_4 \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp -1 \amp -1 \amp -250\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 350\\ 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 450\\ \end{array} \right] \\
\begin{array}{r} R_4 + R_1 \to R_1, \\ -R_4 + R_3\to R_3, \end{array} \qquad \amp \left[\begin{array}{rrrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 200\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 700\\ 0 \amp 0 \amp 1 \amp 0 \amp -1 \amp -100\\ 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 450\\ \end{array} \right]
\end{align*}
Remark 1.3.18. A fourth operation.
Another handy row operation is that of replacing a row with linear combination of itself and another row. In general this is
\begin{equation*}
c_i R_i + c_j R_j \rightarrow R_j
\end{equation*}
Since this is a combination of two row operations together, we will use it, however, not consider it a separate (fourth) row operation.
Subsection 1.3.6 Matrix Pivots
The technique of getting a 1 somewhere in a column and 0’s elsewhere is known as performing a matrix pivot. In fact, this is what was done in Example 1.3.16 and is the standard step in performing Gauss-Jordan Elimination in the goal to get a matrix in reduced row-echelon form.
If we desire a 1 at row \(i\) in column \(j\text{,}\) then the following row operations will produce this 1 and zeros throughout the remainder of the column. Let the matrix have coefficients \(a_{i,j}\text{.}\)
-
The step\begin{equation*} \frac{1}{a_{i,j}} R_i \to R_i \end{equation*}
-
The step\begin{equation*} - a_{k,j} R_i + R_k \to R_k \qquad \text{for $k \neq i$} \end{equation*}will zero out the rest of the column. This is called the elimination step .
If we look at Example 1.3.16, then these steps succeeded in producing the desired structure, however, notice that it introduces fractions and always will if the pivot is not a 1. If we adapt the steps above, we can perform a pivot that keeps fractions at bay.
1
Realistic matrices will often have non integer entries, so this technique does not work in general, however it does make operations on integer matrices easier to do—and there are a number of realistic matrices contain only integers.
Algorithm 1.3.19. Fraction Free Pivot.
If the matrix \(A\) has only integer entries, then the following will perform a fraction-free pivot at row \(i\text{,}\) column \(j\text{,}\) which will eliminate a column, but not produce a 1 at the pivot point. The result will be a matrix with all integer entries.
Let \(a_{i,j}\) be the coefficient of a \(m \times n\) matrix (and an integer). If \(a_{i,j} \lt 0\text{,}\) then perform:
\begin{equation*}
- R_i \to R_i.
\end{equation*}
Then the following row operations
\begin{equation*}
-a_{k,j} R_i + a_{i,j} R_k \to R_k \qquad \text{for $k=1, \ldots m$, $k \neq i$}
\end{equation*}
will eliminate column \(j\text{.}\)
Lastly, let \(d\) be the positive integer that is the \((i,j)\) entry. The other rows will be multiples of \(d\) and the row operation
\begin{equation*}
\frac{1}{d} R_k \to R_k \qquad \text{for $i \neq k$}
\end{equation*}
and any other pivots will now have a entry of \(d\text{.}\)
The following example applies this algorithm to a previously solved linear system.
Example 1.3.20.
Solution.
The first step use the matrix pivot in Algorithm 1.3.19 to perform a matrix pivot on row 1, column 1:
\begin{equation*}
\begin{array}{r} -3R_1-4R_2 \to R_2 \\ -R_1-4R_3 \to R_3 \\ -R_1 \to R_1 \end{array} \qquad \left[\begin{array}{rrr|r} 4 \amp -1 \amp 2 \amp -5\\ 0 \amp 1 \amp 6 \amp -23\\ 0 \amp -1 \amp 14 \amp 7\\ \end{array} \right]
\end{equation*}
Next, let’s perform a pivot about row 2, column 2.
\begin{equation*}
\begin{array}{r} R_2 + R_1 \to R_1 \\ R_2 + R_3 \to R_3 \\ \end{array} \qquad \left[\begin{array}{rrr|r} 4 \amp 0 \amp 8 \amp -28\\ 0 \amp 1 \amp 6 \amp -23\\ 0 \amp 0 \amp -20 \amp -16\\ \end{array} \right]
\end{equation*}
The first and third rows are both multiples of \(4\text{,}\) the previous pivot. If we perform:
\begin{equation*}
\begin{array}{r} \frac{1}{4} R_1 \to R_1, \\ \frac{1}{4} R_3 \to R_3 \end{array} \qquad \left[\begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp -7\\ 0 \amp 1 \amp 6 \amp -23\\ 0 \amp 0 \amp 5 \amp -4\\ \end{array} \right]
\end{equation*}
Lastly, let’s perform another FF pivot on row 3, column 3:
\begin{equation*}
\begin{array}{r} -6R_3 + 5R_2 \to R_2 \\ -2R_3 + 5R_1 \to R_1 \\ \end{array} \qquad \left[\begin{array}{rrr|r} 5 \amp 0 \amp 0 \amp -27\\ 0 \amp 5 \amp 0 \amp -91\\ 0 \amp 0 \amp 5 \amp -4\\ \end{array} \right]
\end{equation*}
And compare this matrix to that in the final reduced-row echelon form of (1.3.8) which if each row of the matrix above is multiplied through by \(1/5\text{,}\) then (1.3.8) is created. The solution can be read from the matrix as the left hand side divided by \(d\text{,}\) in this case 5.This solution is
\begin{equation*}
\boldsymbol{x} = \frac{1}{5}\begin{bmatrix} -27 \amp -91 \amp -4 \end{bmatrix}^{\intercal}
\end{equation*}
and note that this is the same solution as in Example 1.3.16 and in many ways is nicer in that all of the entries of the matrix are integers.
In this course, we will perform matrix pivots, but not in a way to put the matrix in Reduced Row Echelon Form. Instead, the matrices we use will have more variables than rows, resulting in free variables and depending on different conditions, we will use different free variables. Let’s look at another example:
Example 1.3.21.
Let the following matrix have variables \(x_1, x_2, \ldots, x_6\text{.}\) Solve the matrix for \(x_1,x_3\) and \(x_6\) and have free variables \(x_2, x_4\) and \(x_5\text{.}\) Use the Fraction-Free pivots in the solve.
\begin{equation*}
\left[\begin{array}{rrrrrr|r} 3 \amp 1 \amp 0 \amp 0 \amp 2 \amp -7 \amp 11\\ -2 \amp 0 \amp 3 \amp 1 \amp -3 \amp 0 \amp 15\\ 1 \amp 1 \amp 0 \amp 0 \amp 2 \amp -2 \amp 13\\ \end{array} \right]
\end{equation*}
Solution.
If we are trying to solve for \(x_1\text{,}\) then we can perform a pivot about an element in column 1. Let’s pivot about row 1, column 1,
\begin{equation*}
\begin{array}{r} -2R_1 - 3R_2 \to R_2,\\ R_1 -3R_3 \to R_3 \end{array} \qquad \left[\begin{array}{rrrrrr|r} 3 \amp 1 \amp 0 \amp 0 \amp 2 \amp -7 \amp 11\\ 0 \amp -2 \amp -9 \amp -3 \amp 5 \amp 14 \amp -67\\ 0 \amp -2 \amp 0 \amp 0 \amp -4 \amp -1 \amp -28\\ \end{array} \right]
\end{equation*}
Next, we are looking to solve for \(x_3\) and since row 1 gives a solution for \(x_1\text{,}\) we don’t want to mess that up and instead will choose row 2 to perform a pivot, so pivot about row 2, column 3:
\begin{equation*}
\begin{array}{r} 0R_2 + 9R_1 \to R_1 \\ 0R_2 + 9R_3 \to R_3 \end{array} \qquad \left[\begin{array}{rrrrrr|r} 27 \amp 9 \amp 0 \amp 0 \amp 18 \amp -63 \amp 99\\ 0 \amp -2 \amp -9 \amp -3 \amp 5 \amp 14 \amp -67\\ 0 \amp -18 \amp 0 \amp 0 \amp -36 \amp -9 \amp -252\\ \end{array} \right]
\end{equation*}
Note that we didn’t really need to do any steps here since the form was correctly. However, for consistency between steps, we did this anyway.
Now, we perform some cleanup. First, let’s make the 2nd row, 2nd column positive. and then since the first and 3rd rows are multiples of 3, the previous value of \(d\text{,}\) we will multiply through by \(1/3\text{.}\)
\begin{equation*}
\begin{array}{r} \frac{1}{3} R_1 \to R_1, \\\frac{1}{3} R_3 \to R_3, \end{array} \qquad \left[\begin{array}{rrrrrr|r} 9 \amp 3 \amp 0 \amp 0 \amp 6 \amp -21 \amp 33\\ 0 \amp 2 \amp 9 \amp 3 \amp -5 \amp -14 \amp 67\\ 0 \amp -6 \amp 0 \amp 0 \amp -12 \amp -3 \amp -84\\ \end{array} \right]
\end{equation*}
Lastly, we want to solve for \(x_6\text{,}\) so we will pivot about row 3, column 6 with the following row operations
\begin{equation*}
\begin{array}{r} -21R_3 + 3R_1 \to R1, \\ -14R_3 + 3R_2 \to R_2 \end{array} \qquad \left[\begin{array}{rrrrrr|r} 27 \amp 135 \amp 0 \amp 0 \amp 270 \amp 0 \amp 1863\\ 0 \amp 90 \amp 27 \amp 9 \amp 153 \amp 0 \amp 1377\\ 0 \amp -6 \amp 0 \amp 0 \amp -12 \amp -3 \amp -84\\ \end{array} \right]
\end{equation*}
And again with some cleanup to the pivot in row 3, column 6 to be \(+3\) and the pivots at row 1, column 1 and row 2, column 2 to also be \(3\text{.}\)
\begin{equation*}
\begin{array}{r} -R_3 \to R_3 \\ -\frac{1}{9}R_2 \to R_2 \\ -\frac{1}{9} R_1 \to R_1 \end{array} \qquad \left[\begin{array}{rrrrrr|r} 3 \amp 15 \amp 0 \amp 0 \amp 30 \amp 0 \amp 207\\ 0 \amp 10 \amp 3 \amp 1 \amp 17 \amp 0 \amp 153\\ 0 \amp 6 \amp 0 \amp 0 \amp 12 \amp 3 \amp 84\\ \end{array} \right]
\end{equation*}
We can actually write down the equation that this matrix represents as
\begin{align*}
3 x_1 + 15 x_2 + 30 x_5 \amp = 207\\
10x_2 + 3x_3 + x_4 + 17x_5 \amp = 153 \\
6 x_2 + 12x_5 + 3x_6 \amp = 84
\end{align*}
\begin{align*}
x_1 \amp = \frac{1}{3}(207 -15 x_2 - 30 x_5)\\
x_2 \amp = \frac{1}{3}(153 -10x_2 - x_4 - 17 x_5) \\
x_6 \amp = \frac{1}{3}(84 - 6x_2 +2x_4-3x_5)
\end{align*}
And note that the three variables on the right hand side are free variables. This example will be similar to matrices in this class and understanding this example will get you far in understanding the matrices using here.
As we will see in this class, the matrices presented here are quite small, and clearly take a lot of operations to perform and the slightly arithmetic error results in the wrong answer. Once you have the idea under your belt, you should move onto using software to do these operations and we will show how to do this in the next section.
Subsection 1.3.7 Geometry of Linear Systems of 2 variables
If we consider only linear systems with two variables, then each equation is just a line, which we can graph on a set of axes. We are going to examine the geometry of linear systems of two variables.
First, we are going to look at three linear systems that each have different types of solutions. We can see the solutions by looking at the graphs.
-
The graph of each line in the linear system\begin{equation} \begin{aligned} x + 2 y \amp = 5, \\ 2x - 3 y \amp = -4, \end{aligned}\tag{1.3.9} \end{equation}is
Figure 1.3.22. Plot of two intersecting lines The solution of the system is the point at which they cross. In this case it looks like the point \((1,2)\) or \(x=1\) and \(y=2\text{.}\) This is an example where there is only one solution (or a unique solution). -
If we graph the lines in the linear system\begin{equation} \begin{aligned} 3x + 7 y \amp= 10, \\ 6 x + 14 y \amp= 5, \end{aligned}\tag{1.3.10} \end{equation}we get
Figure 1.3.23. Plot of two parallel lines As you can see, it doesn’t appear that the lines cross anywhere. In fact, they don’t because the lines are parallel. This is an example of a linear system with no solution. -
The linear system\begin{equation} \begin{aligned} x + 2 y = 5, \\ 2x + 4 y = 10, \end{aligned}\tag{1.3.11} \end{equation}has the following graph for each line
Figure 1.3.24. A plot of two equivalent lines It appears that there is only one line. This is because both lines have the same graph. Each point on the line is a solution to the linear system and since there are an infinite number of such points, this is an example of a linear system with infinite number of solutions.
You can see if you have two lines, each with two variables, the example in (1.3.9) is what happens if the two slopes are different. In this case, there is one (or a unique) solution.
In the other two cases as in equations (1.3.10) and (1.3.11), both sets of lines have the same slope. In the case of (1.3.10) the lines have different \(y\)-intercepts, and therefore the lines are parallel and thus there is no solution to the linear system. In the case of (1.3.11), both the slope and \(y\)-intercepts are equal, so the lines are equal and thus any point on the line is a solution, and this system has an infinite number of solutions.
