Lecture 2: Elimination with matrices

讲座摘要（lecture summary）

Method of Elimination

Elimination is the technique most commonly used by computer software to solve systems of linear equations. It finds a solution $x$ to $Ax = b$ whenever the matrix $A$ is invertible. In the example used in class,

$$A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \quad \text{and} \quad \bm{b} = \begin{bmatrix} 1 \\ 12 \\ 2 \end{bmatrix}$$

The number $1$ in the upper left corner of A is called the first pivot. We recopy the first row, then multiply the numbers in it by an appropriate value (in this case $3$) and subtract those values from the numbers in the second row. The first number in the second row becomes $0$. We have thus eliminated the $3$ in row $2$ column $1$.

The next step is to perform another elimination to get a $0$ in row $3$ column $1$; here this is already the case.

The second pivot is the value $2$ which now appears in row $2$ column $2$. We find a multiplier (in this case $2$) by which we multiply the second row to eliminate the $4$ in row $3$ column $2$. The third pivot is then the $5$ now in row $3$ column $3$.

We started with an invertible matrix $A$ and ended with an upper triangular matrix $U$; the lower left portion of $U$ is filled with zeros. Pivots $1, 2, 5$ are on $2$ the diagonal of $U$.

$$A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \to U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$

We repeat the multiplications and subtractions with the vector $\bm{b} = \begin{bmatrix} 1 \\ 12 \\ 2 \end{bmatrix}$

For example, we multiply the $2$ in the first position by $3$ and subtract from $12$ to get $6$ in the second position. When calculating by hand we can do this efficiently by augmenting the matrix $A$, appending the vector b as a fourth or final column. The method of elimination transforms the equation $Ax = b$ into a new equation $U\bm{x} = \bm{c}$. In the example above, $U =\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$ comes from $A$ and $\bm{c} = \begin{bmatrix} 2 \\ 6 \\ -10 \end{bmatrix}$ comes from $\bm{b}$.

The equation $U\bm{x} = \bm{c}$ is easy to solve by back substitution; in our example, $z = −2, y = 1$ and $x = 2$. This is also a solution to the original system $A\bm{x} = \bm{b}$.

The determinant of $U$ is the product of the pivots. We will see this again.

Pivots may not be $0$. If there is a zero in the pivot position, we must exchange that row with one below to get a non-zero value in the pivot position.

If there is a zero in the pivot position and no non-zero value below it, then the matrix $A$ is not invertible. Elimination can not be used to find a unique solution to the system of equations – it doesn’t exist.

Elimination Matrices

The product of a matrix ($3 \times 3$) and a column vector ($3 \times 1$) is a column vector ($3 \times 1$) that is a linear combination of the columns of the matrix.

The product of a row ($3 \times 1$) and a matrix ($3 \times 3$) is a row ($1 \times 3$) that is a linear combination of the rows of the matrix.

We can subtract $3$ times row $1$ of matrix $A$ from row $2$ of $A$ by calculating the matrix product:

$$\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$

The elimination matrix used to eliminate the entry in row $m$ column $n$ is denoted $E_{mn}$. The calculation above took us from $A$ to $E_{21}A$. The three elimination steps leading to $U$ were: $E_{32}(E_{31}(E_{21}A)) = U$, where $E_{31} = I$. Thus $E_{32}(E_{21}A) = U$.

Matrix multiplication is associative, so we can also write $(E_{32}E_{21})A = U$. The product $E_{32}E_{21}$ tells us how to get from $A$ to $U$. The inverse of the matrix $E_{32}E_{21}$ tells us how to get from $U$ to $A$.

If we solve $U\bm{x} = EA\bm{x} = E\bm{b}$, then it is also true that $Ax = b$. This is why the method of elimination works: all steps can be reversed.

A permutation matrix exchanges two rows of a matrix; for example,

$$p = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

The first and second rows of the matrix $PA$ are the second and first rows of the matrix $A$. The matrix $P$ is constructed by exchanging rows of the identity matrix.

To exchange the columns of a matrix, multiply on the right (as in $AP$) by a permutation matrix.

Note that matrix multiplication is not commutative: $PA \ne AP$.

Inverses

We have a matrix:

$$E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

which subtracts $3$ times row $1$ from row $2$. To “undo” this operation we must add $3$ times row $1$ to row $2$ using the inverse matrix:

$$E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

In fact, $E_{21}^{-1}E_{21} = I$.

Problems and Solutions（习题及答案）

Problem 2.1: In the two-by-two system of linear equations below, what multiple of the first equation should be subtracted from the second equation when using the method of elimination? Convert this system of equations to matrix form, apply elimination (what are the pivots?), and use back substitution to find a solution. Try to check your work before looking up the answer.

$$\begin{array}{rl} 2x + 3y & = 5 \\ 6x + 15y & = 12 \end{array}$$

Solution

One subtracts $\bm{3}$ times the first equation from the second equation in order to eliminate the $6x$.

To convert to matrix form, use the general format $A\bm{x} = \bm{b}$:

$$\begin{array}{rl} 2x + 3y & = 5 \\ 6x + 15y & = 12 \end{array} \to \begin{bmatrix} 2 & 3 \\ 6 & 15 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 5 \\ 12 \end{bmatrix}$$

We then apply elimination on matrix $A$. Using the first pivot (the number $2$ in the upper left corner of $A$), we subtract three times the first row from the second row to get:

$$A = \begin{bmatrix} 2 & 3 \\ 6 & 15 \end{bmatrix} \to U = A = \begin{bmatrix} 2 & 3 \\ 0 & 6 \end{bmatrix}$$

where $U$ is an upper triangular matrix with pivots $2$ and $6$. Doing the same to the right side $b = (5, 12)$ gives a new equation of the form $U\bm{x} = \bm{c}$ :

$$\begin{bmatrix} 2 & 3 \\ 0 & 6 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 5 \\ -3 \end{bmatrix}$$

To solve our new equation, we use back substitution:

$$6y = -3 \to \boxed{y = -\frac{1}{2}}$$

and

$$2x + 3y =5 \to 2x +3 \Big( -\frac{1}{2}\Big) = 5 \to 2x = 5 + \frac{3}{2} = \frac{13}{2} \to \boxed{x = \frac{13}{4}}$$

We know that our solution fulfills the first equation; let’s make sure that our values fulfill the second equation as a check on our work:

$$6x + 15y = 6\Big(\frac{13}{4}\Big) + 15\Big(\frac{-1}{2}\Big) = \frac{78 - 30}{4} = 12 \quad \checkmark$$

Problem 2.2: (2.3 #29. Introduction to Linear Algebra: Strang) Find the triangular matrix $E$ that reduces “Pascal’s matrix” to a smaller Pascal:

$$E\begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix*} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \end{bmatrix}$$

Which matrix $M$ (multiplying several $E$’s) reduces Pascal all the way to $I$?

Solution

The matrix is $E =\begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*}$

One can eliminate the second column with the matrix

$$\begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*}$$

and the third column with the matrix

$$\begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*}$$

Multiplying these together, we get

$$M = \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix*} = \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1 \end{bmatrix*}$$

Since $M$ reduces the Pascal matrix to $I, M$ must be the inverse matrix!