\(\newcommand{\augmatrix}[2]{\left(\begin{array}{@{}#1 |c@{}} #2 \end{array}\right)} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section2.3Elimination using Matrices

SubsectionThe Assignment

  • Read section 2.3 of Strang.
  • Watch a video from the YouTube series Essence of Linear Algebra by user 3Blue1Brown.
  • Read the discussion below and work out the exercises.

SubsectionLearning Goals

Before class, a student should be able to:

  • Translate a system of linear equations into the form of an augmented matrix and back.
  • Perform the forward pass elimination process to an augmented matrix.
  • Multiply a pair of square matrices having the same size.
  • Identify the matrix which performs the operation “add a multiple of row i to row j.”
  • Identify the matrix which performs the operation “swap the places of row i and row j.”

Some time after class, a student should be able to:

  • Use the steps from a forward pass elimination step to write a correct equation of the form \begin{equation*} E_{\bullet}E_{\bullet}\cdots E_{\bullet} (A\ |\ b) = (U\ |\ b') \end{equation*} where \(U\) is an upper triangular matrix.

SubsectionDiscussion: Elimination and Using Matrices as “Transformations”

Let us focus (for now) on square systems of equations, where the number of unknowns is equal to the number of equations.

SubsubsectionThe Four Ways to Write a System

Recall that there are three equivalent ways to write the typical linear algebra problem: (1) a system of linear equations to be solved simultaneously, (2) an equation expressing some linear combination of vectors with unknown coefficients as equal to another vector, and (3) a matrix equation.

Here is an example: This system of linear equations \begin{equation*} \left\{ \begin{array}{rrrrrrr} & &3y &+ &2z &= &8 \\ x &- & y &+ & z &= &-1 \\ 3 x &+ &2y &+ &3z &= &1 \end{array}\right. \end{equation*} is equivalent to this equation using a linear combination of vectors \begin{equation*} x \begin{pmatrix} 0 \\ 1 \\ 3 \end{pmatrix} + y \begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix} + z \begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} \end{equation*} and both of those are equivalent to this matrix equation \begin{equation*} \begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 3 &2 &3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} . \end{equation*}

Each of these viewpoints has its advantages when talking about the geometry of linear algebra. But one way that things steadily improve as you move down the page is in the amount of notational baggage. From each version to the next, we lose repetitive bits of symbol that one can just remember from context. Often, this is taken one step further! We now throw away the unknowns, the equal signs and some of the parentheses surrounding the matrices and vectors, and just write an augmented matrix. \begin{equation*} \augmatrix{ccc}{ 0 &3 &2 &8\\ 1 &-1 &1 &-1\\ 3 &2 &3 &1 } \end{equation*} This is the minimum fuss way to keep track of all the information you need to solve the original system.

SubsubsectionRepresenting Elimination with Matrices

The process of elimination starts by performing operations on the system of equations. In the example above, one simplification we can make is to add \(-3\) times equation (ii) to equation (iii).

Then the new system looks like this: \begin{equation*} \left\{ \begin{array}{rrrrrrr} & &3y &+ &2z &= &8 \\ x &- & y &+ & z &= &-1 \\ & &5y & & &= &4 \end{array}\right. \end{equation*} Let's translate that into the linear combination format: \begin{equation*} x \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} + y \begin{pmatrix} 3 \\ -1 \\ 5 \end{pmatrix} + z \begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 4 \end{pmatrix} . \end{equation*} What has happened to each of the vectors? Well, in each case, we have added \(-3\) times the second component to the third component. We have seen that one way to change vectors into other vectors is by (left-)multiplying them by matrices. Could we be so lucky that the operation “add \(-3\) times the second component to the third component” is representable by a matrix operation? YES. It is not hard to check that the matrix we need is \begin{equation*} E = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} . \end{equation*} In fact, let's check it now for each of the four vectors we have in our system: \begin{equation*} E \begin{pmatrix} 0 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \end{equation*} and \begin{equation*} E \begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} \begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix} = \begin{pmatrix} 3 \\ -1 \\ 5 \end{pmatrix} \end{equation*} and \begin{equation*} E \begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} \begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix} \end{equation*} and \begin{equation*} E \begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} \begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 4 \end{pmatrix}. \end{equation*}

Ha Ha! It all checks out. Those are the four vectors from our second system. This means that we can even use a simple subsitution to rewrite things. (It is not obvious at the moment why this is helpful. Hang on a bit.) \begin{equation*} x\cdot E\begin{pmatrix} 0 \\ 1 \\ 3 \end{pmatrix} + y\cdot E\begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix} + z\cdot E\begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix} = E\begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} \end{equation*} Still, it sure would be nice if we had a compact way to write that down.

SubsubsectionMatrix Multiplication

We make a compact way to write down that last equation by defining an operation of multiplying two matrices. If \(E\) and \(A\) are two matrices, we define their matrix product to be a new matrix as follows:

First, write \(A\) as a collection of columns \(v_i\) \begin{equation*} A = \begin{pmatrix} v_1 &v_2 &v_3 \end{pmatrix} \end{equation*} and then we declare that \(EA\) is the matrix made up of the columns \(Ev_i\) in the corresponding order. \begin{equation*} EA = \begin{pmatrix} Ev_1 &Ev_2 &Ev_3 \end{pmatrix} \end{equation*}

By way of example, we have already considered the matrices \begin{equation*} E = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix} \quad \text{ and } \quad A = \begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 3 &2 &3 \end{pmatrix}. \end{equation*} You should check that their product is now \begin{equation*} EA = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &-3 &1 \end{pmatrix}\begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 3 &2 &3 \end{pmatrix} = \begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 0 &5 &0 \end{pmatrix} \end{equation*}

Finally, let's see how this influences our last two forms of the equations. The matrix form of our system was \(Ax = v\) where \(A\) is as above, and the vectors are \(v = \left(\begin{smallmatrix} 8 \\ -1 \\ 1 \end{smallmatrix}\right)\) and \(x = \left( \begin{smallmatrix} x \\ y \\ z \end{smallmatrix}\right)\). The neat part is that our new definition of matrix multiplication means that our elimination step transformed the equation \begin{equation*} Ax = v \quad \text{ or }\quad \begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 3 &2 &3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 1 \end{pmatrix} \end{equation*} into the newer equation \begin{equation*} (EA) x = Ev \quad \text{ or } \quad \begin{pmatrix} 0 &3 &2 \\ 1 &-1 &1 \\ 0 &5 &0 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 8 \\ -1 \\ 4 \end{pmatrix}. \end{equation*}

The same thing works for the augmented matrix. The augmented matrix form is really just writing down \begin{equation*} \augmatrix{c}{A &v } =\augmatrix{ccc}{ 0 &3 &2 &8\\ 1 &-1 &1 &-1\\ 3 &2 &3 &1 } \end{equation*} and the elimination step changes this into \begin{equation*} \augmatrix{c}{EA &Ev} = \augmatrix{ccc}{ 0 &3 &2 &8 \\ 1 &-1 &1 &-1 \\ 0 &5 &0 &4 }. \end{equation*}

SubsubsectionMatrices as Transformations

Take a moment and reflect on the key transition in what happens above. The most important thing that made it all work was that a matrix (the elimination matrix \(E\)) was used to perform some sort of operation on vectors.

This is a key property of matrices. The matrix \(E\) defines a kind of function. For every vector \(w\) with three components, we can compute exactly one new vector \(Ew\), still with three components. This means that \(E\) defines a function from the set of \(3\)-vectors to the set of \(3\)-vectors.

SubsectionSageMath and Matrix Multiplication

SageMath has built-in matrix multiplication. You do the obvious thing and it works.

You can check that it works with the way we defined matrix multiplication as a linear combination of vectors, too.

First, we define the column vectors by pulling out the entries from B and arranging them. To be sure, we ask Sage to display them as columns.

Now we can pile these rows into a matrix and then use the transpose to put them in columns.

And we can double check everything by asking Sage if these things are equal.

This kind of test can be useful for checking our work! The discussion above has this multiplication:

Ta-Da!!!

SubsectionExercises

Task34

In the main example above \begin{equation*} \left\{ \begin{array}{rrrrrrr} & &3y &+ &2z &= &8 \\ x &- & y &+ & z &= &-1 \\ 3x &+ &2y &+ &3z &= &1 \end{array} \right. \end{equation*} we would rather have our first pivot in the upper left corner (i.e. the first row should have a non-zero coefficient for \(x\)). This can be achieved by swapping the positions of rows (i) and (ii).

Find a matrix \(P_{12}\) so that multiplying by \(P_{12}\) on the left performs the corresponding row switching operation on the augmented matrix \begin{equation*} \augmatrix{ccc}{ 0 &3 &2 &8 \\ 1 &-1 &1 &-1 \\ 3 &2 &3 &1} \end{equation*}

Task35

Consider the system \begin{equation*} \left\{ \begin{array}{rrrrr} 6x &- &y &= &14 \\ 97x &- &16y &= &2/3 \\ \end{array} \right. \end{equation*}

  1. Write this system in the other three forms: (1) an equation involving a linear combination of vectors; (2) an equation involving a \(2\times 2\) matrix; (3) an augmented matrix.
  2. Perform an elimination step on the system from the last exercise to put the sytem in triangular form. You should get two pivots.
  3. Write the new system in each of our four forms.

Task36

Still working with the same system of equations, use SageMath to make two column picture plots:

  • One showing the three relevant column vectors from the original system.
  • One showing the three relevant column vectors from the system after the elimination step.

You may find it helpful to look through the Sage examples in previous sections of this workbook.

Task37

One more time, stay with the same system of equations. Use SageMath to make two row picture plots:

  • One showing the two relevant lines in the original system.
  • One showing the two relevant lines from the system after the elimination step.

You may find it helpful to look through the SageMath examples in previous sections of this workbook.

Task38

Consider this system of three equations in three unknowns: \begin{equation*} \left\{ \begin{array}{rrrrrrr} -x &+ &\frac{2}{3} y &+ &z &= &1 \\ x &+ & 6y &+ &z &= &1 \\ 3x & & &+ &3z&= &1 \\ \end{array}\right. \end{equation*} Perform the elimination steps to transform this system into a triangular one.

Write down the corresponding matrices you use to perform each of these steps on the augmented matrix version of this system.

Task39

Still working with the system of equations from the last task, use SageMath to make two column picture plots:

  • One showing the four relevant column vectors from the original system.
  • One showing the four relevant column vectors from the system after the elimination step.

You may find it helpful to look through the Sage examples in previous sections of this workbook.

Task40

One more time, stay with the system of equations from previous two tasks. Use Sage to make two row picture plots:

  • One showing the two relevant lines in the original system.
  • One showing the two relevant lines from the system after the elimination step.

You may find it helpful to look through the Sage examples in previous sections of this workbook.