Find the permutation matrix $P$, the lower triangular matrix $L$ and the upper triangular matrix $U$ such that $$ PA=LU $$
Given $$ A= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ -2 & -3 & -4 & -5 & -6 & -7 \\ 3 & 7 & 11 & 16 & 21 & 27 \\ -4 & -5 & -5 & -5 & -5 & -5 \end{pmatrix}$$
I came this far
$$ U = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}$$
and
$$ L= \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 0 \\ -4 & 3 & 0 & 1 \end{pmatrix}$$
The last step I have to make is to change the fourth row with the third one but I do not know exactly how to change the entries in the lower triangular matrix L. Can anyone explain what exactly I have to switch in L?
Best Answer
Long answer: think of the result of forward elimination as being a matrix equation of the form $U=E_r P_r E_{r-1} P_{r-1} \dots E_1 P_1 A$ where $E_i$ are "elimination" matrices (clearing out the column below the $i$th pivot in the usual way) and $P_i$ are either permutation matrices that move the $i$th pivot into the $i$th row or else the identity (if you didn't do an exchange in that step). Elimination matrices are lower triangular, and stay that way when multiplied together. But when permutation matrices get included, they stop being lower triangular.
So now you generally want to invert that product of $E_i P_i$ to isolate $A$. If you keep them all together, the inverse won't be lower triangular, which in $PA=LU$ you want it to be. So what you do instead is you rewrite the product $E_r P_r \dots E_1 P_1$, so that all the permutation matrices are on the right and all elimination matrices are on the left. To do that, it suffices to figure out how to write $PE$ as $E' P'$.
This can be done with $P'=P$ and $E'=P E P^{-1} = P E P^T$, as is easy to check: $E' P'=P E P^{-1} P=PE$. This $E'$ taking this form is an instance of a common situation in algebra, where conjugation is used to apply an operation "in the context" of another, invertible operation having been applied already.
By doing that over and over again, you can move all the permutation matrices over to the right. The result looks like this:
$$U=E_r (P_r E_{r-1}^T P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T) \\ \cdot P_r \cdot \dots \cdot P_1 \cdot A.$$
So now
$$L^{-1}=E_r (P_r E_{r-1} P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T)$$
What does this mean in a nutshell? It means that to get the correct $L^{-1}$, you have to move the nontrivial entries in your "computed $L^{-1}$" based on all the row exchanges that you did after those entries were computed. Inverting $L^{-1}$ at the end still works the same (you just flip the sign on the nontrivial entries).
Thus in your example, the effect of swapping rows $3$ and $4$ is that you update $L$ by exchanging the roles of indices $3$ and $4$, resulting in:
$$L=\begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 3 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix}.$$
Note that this is not the same as just exchanging row $3$ with row $4$.
After that you're done, in this particular example, but if you weren't, then you would not exchange $3$ with $4$ in subsequent steps.
Short answer: Your final matrix $P$ achieves all the row exchanges you did. To get $L$, each time you do a row exchange that would be achieved by multiplying on the left by a permutation matrix $P$, you replace your current $L$ with $P L P^T$, which means that you perform that permutation both on the rows and on the columns of your current $L$ (but not on the final $L$).