Back to the on-screen lesson ·
Row operations as left multiplication, the inverse of an elementary matrix, forward elimination as a product, and solving many systems from one factorisation.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write the elementary matrix of any row operation and its inverse, explain why left multiplication acts on rows while right multiplication acts on columns, read the $L$ of a factorisation straight off the multipliers an elimination used, rebuild $A$ from $L$ and $U$ to check a factorisation, solve a triangular system by forward or back substitution, say why one factorisation serves many right-hand sides, and state when a permutation is needed and what $PA = LU$ means.
Gauss-Jordan works because reducing $A$ to $I$ and applying the same operations to $I$ produces $A^{-1}$. That claim was made and not proved. The proof is one idea — a row operation is a matrix — and once it is in place it also produces the factorisation that real software uses to solve systems.
An elementary matrix is what the identity becomes after one row operation. A matrix is unit lower triangular when it is lower triangular with ones on the diagonal; $L$ is always of this kind. $U$ is the upper triangular matrix forward elimination leaves behind. A permutation matrix $P$ is the identity with its rows reordered. Forward substitution solves a lower triangular system downwards; back substitution solves an upper triangular one upwards.
Take any row operation, do it to the identity, and call the result $E$. Then for every conformable $A$, $EA$ is $A$ with that same operation done to it.
That is not a coincidence to be checked case by case; it is the row-by-row reading of a product from lesson 6. Row $i$ of $EA$ is row $i$ of $E$ times the whole of $B$ — that is, the combination of the rows of $A$ that row $i$ of $E$ prescribes. Row $i$ of the identity prescribes just row $i$, and an elementary matrix changes exactly one of those prescriptions.
The three operations give three shapes:
| Operation | $E$ | $E^{-1}$ |
|---|---|---|
| swap rows $i$ and $j$ | $I$ with those rows swapped | itself |
| multiply row $i$ by $k \ne 0$ | $I$ with $k$ in place $(i,i)$ | $I$ with $1/k$ there |
| add $k$ times row $j$ to row $i$ | $I$ with $k$ in place $(i,j)$ | $I$ with $-k$ there |
Every elementary matrix is invertible, and its inverse is elementary. Of course: every row operation can be undone by a row operation.
Now run forward elimination, using only the third kind. It produces $E_m \cdots E_2E_1A = U$, upper triangular. Move the elementary matrices to the other side:
$$A = E_1^{-1}E_2^{-1}\cdots E_m^{-1}U = LU.$$
And $L$, that product of inverse elementary matrices, turns out to be unit lower triangular with the multipliers themselves in the places they were used. No further computation: eliminate, write each multiplier down where it came from, and the factorisation has been assembled along the way.
Another way: picture
Think of elimination as a stack of instructions carried out on $A$. Each instruction is a card, and $E$ is the card written out as a matrix. To get back to $A$ from $U$ you take the cards off the top of the stack in reverse order, doing the opposite of each — which is exactly what the product $E_1^{-1}E_2^{-1}\cdots E_m^{-1}$ says, read from the right. $L$ is the whole stack, undone, collapsed into one array; and because the operations were all downward, the array comes out lower triangular.
Another way: steps
Eliminating on an $n \times n$ matrix costs roughly $n^{3}/3$ multiplications. A triangular solve costs about $n^{2}$. For $n = 1000$ that is a ratio of about three hundred to one.
A system with one right-hand side does not care: eliminate on $[A \mid b]$ and be done. But a great many real problems present the same $A$ with right-hand side after right-hand side — a structure under many different loads, a circuit under many different inputs, a time-stepping scheme where every step solves with the same matrix. Factor once at $n^{3}/3$, then pay $2n^{2}$ per right-hand side, and the hundredth solve is essentially free.
This is also the reason not to compute $A^{-1}$. $A^{-1}b$ costs $n^{2}$ per right-hand side too, and produces the same answers, but computing $A^{-1}$ in the first place costs about three times the factorisation and is less accurate. The factorisation dominates it on both counts, which is why library routines return $L$, $U$ and a permutation, and not an inverse.
And $L$ and $U$ fit in the space $A$ occupied: $U$ on and above the diagonal, the multipliers of $L$ below it, the ones on $L$'s diagonal not stored because they are always ones.
Forward elimination as described breaks if a pivot position holds a zero: you cannot clear a column using a row whose leading entry is $0$. The repair is a row swap, and once a swap has been used the product of the inverse elementary matrices is no longer triangular.
The fix is to collect the swaps separately. Every reduction of a square matrix can be arranged as
$$PA = LU,$$
with $P$ a permutation matrix recording which rows ended up where. Solving is barely changed: $Ax = b$ becomes $PAx = Pb$, so reorder the entries of $b$ to match and then do the same two triangular solves.
In practice a swap is made even when the pivot is merely small rather than zero, because dividing by a small number magnifies every error already present. Choosing the largest available entry in the column as the pivot is called partial pivoting, and it is what every serious implementation does. The mathematics is unchanged; the arithmetic is far better behaved.
$L$ holds the multipliers, not their negatives. Elimination subtracts $k$ times a row; the elementary matrix that does it has $-k$ in it; and $L$ is built from the inverses, which put the $+k$ back. If a sign is troubling you, multiply $LU$ out and see which choice returns $A$.
Left multiplication acts on rows; right multiplication acts on columns. $EA$ does the row operation. $AE$ does the corresponding column operation, which is a different thing and not what elimination wants.
$A = LU$, not $UL$. Reversing the factors gives a different matrix, as multiplying any small example out shows at once.
Not every matrix has an $LU$ without a permutation. $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ has none: the first pivot position is zero and no downward operation can fix it. That is what $P$ is for, and it is not an optional refinement.
Having $L$ and $U$ is not having the solution. The factorisation is a rewriting of $A$; the answer still needs the two substitutions, and they have to be done in the right order.
$A = \begin{pmatrix} 2 & 4 \\ 6 & 3 \end{pmatrix}$. Row $2$ minus $3$ times row $1$ clears the corner; the multiplier is $3$.
Write the multiplier down as you use it.
$U = \begin{pmatrix} 2 & 4 \\ 0 & -9 \end{pmatrix}$ and $L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}$.
The multiplier goes in row $2$, column $1$, unnegated.
Check: $LU = \begin{pmatrix} 2 & 4 \\ 6 & 12 - 9 \end{pmatrix} = \begin{pmatrix} 2 & 4 \\ 6 & 3 \end{pmatrix}$, which is $A$.
Multiplying back costs nothing and settles the signs.
Using the $L$ and $U$ above with $b = \begin{pmatrix} 2 \\ 15 \end{pmatrix}$: forward substitution gives $y_1 = 2$ and $3(2) + y_2 = 15$, so $y_2 = 9$.
Down through $L$.
Back substitution in $Ux = y$: $-9x_2 = 9$ so $x_2 = -1$, then $2x_1 + 4(-1) = 2$ so $x_1 = 3$.
Up through $U$.
Now $b = \begin{pmatrix} 6 \\ 9 \end{pmatrix}$: $y = (6, -9)$, then $x_2 = 1$ and $x_1 = 1$. The elimination was not repeated, and it never will be for this $A$.
The second answer cost a fraction of the first.
Read what $E$ does: $EA$ is $A$ with $4$ times row $1$ subtracted from row $2$.
Translate the matrix back into an instruction.
Undoing that means adding $4$ times row $1$ to row $2$.
The opposite operation, not the opposite matrix.
So $E^{-1} = \begin{pmatrix} 1 & 0 \\ 4 & 1 \end{pmatrix}$ — the same matrix with the multiplier's sign changed, and it is the kind of factor $L$ is built from.
Write the $3 \times 3$ matrix $E$ for which $EA$ is $A$ with $5$ times row $1$ added to row $3$, for every $3 \times 3$ matrix $A$.
This task has no paper form; do it on a device.
Each of these operations on the rows of a $2 \times 2$ matrix is carried out by multiplying on the left by one of the matrices. Match them up.
| $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ | $\begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix}$ | $\begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}$ | |
|---|---|---|---|
| Swap row $1$ and row $2$ | |||
| Multiply row $2$ by $3$ | |||
| Add $3$ times row $1$ to row $2$ |
Forward elimination on a $3 \times 3$ matrix $A$ used, in order: row $2$ minus $2$ times row $1$; row $3$ minus $2$ times row $1$; row $3$ minus $3$ times row $2$. Write the $L$ of $A = LU$.
This task has no paper form; do it on a device.
Solve $Ly = b$ for the third entry of $y$, where $L = \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 4 & 1 & 1 \end{pmatrix}$ and $b = \begin{pmatrix} 3 \\ 6 \\ 5 \end{pmatrix}$.
Answer:
The same matrix $A$ has to be used with $4$ different right-hand sides. Put the stages of the work into the order they are carried out.
Number the steps in order (write the number in the box):
A factorisation $A = LU$ has $L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}$ and $U = \begin{pmatrix} 3 & 3 \\ 0 & 3 \end{pmatrix}$. Write $A$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Write the $3 \times 3$ matrix $E$ for which $EA$ is $A$ with $2$ times row $1$ added to row $3$, for every $3 \times 3$ matrix $A$.
This task has no paper form; do it on a device.
You can build and invert elementary matrices, produce $L$ and $U$ from an elimination, and use them to solve repeatedly. Say in your own words why $L$ carries the multipliers rather than their negatives. Next: the single number that decides whether any square matrix is invertible.
10. Your turn: what is the inverse of $E = \begin{pmatrix} 1 & 0 \\ -4 & 1 \end{pmatrix}$?, step 3
Which is exactly why $L$ carries the multipliers unnegated.