# Decompose $A$ as $A = LPU$,

, where $A \in Gl_ n \left( \mathbb{R^n} \right)$, $L$ is lower triangular, $U$ is upper triangular with diagonal elements of $1$, and $P$ is a permutation matrix.

It is fairly easy to decompose any invertible such $A$ as $PA = LU$ (1) (more or less Gaussian elimination with pivoting). But what is a constructive proof to get the above decomposition? The usual way I prove (1) is applying elementary matrices to the left of the pivoted $PA$, and this would (would it?) change $PA$, not only $A$ (if it only changed $A$, we could commute $P$).

This is an exercise in Artin, 2nd edition, 2nd chapter, M* exercises.

Thanks.

-

There's a variant of Gaussian elimination where you don't move the pivots until after you have cleared entries below the pivot. For example, in the $2 \times 2$ case, if you have $$A = \begin{pmatrix} 0 & 2 \\ 1 & 4 \end{pmatrix},$$ the first step in Gaussian elimination would be to swap the two rows. But in the variant, you only do 'L' moves first. In each column, the entry you choose to become the pivot is the same as in Gaussian elimination (the highest non-zero entry that does not occur in the row of a previous pivot), but you don't move it. You can still clear all the entries below a leading 1, so that after you finish the forward phase (minus row swapping), you can swap rows to get to row echelon form. This gives $PLA = U$, so multiplying on the left by $P^{-1}$, then $L^{-1}$ decomposes $A$ into $PLU$ form.

To illustrate with $A$, $$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} 0 & 2 \\ 1 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}$$ so $$A = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}.$$

(Of course, in this example, there's a simpler $PU$ decomposition, but the general algorithm hinted at above works in general.)

-
Thank you, Michael. I see your idea, but so far don't see how it works - your example is appreciated and easy enough, but the general case. 1, why would it be enough to clear out only the elements below the largest; 2, is it still guaranteed to even work (are all these l-triangular if we refer to a non-diagonal element)? I am boarding a plane, and will come back to it later. Any further attempts to help me see appreciated obviously. :) –  gnometorule Jan 30 '13 at 18:30
The basic idea is that every row echelon matrix is upper triangular. So your goal to get an LPU decomposition is to do "L row operations" (add a higher row to a lower row) and then row swaps to get to the row echelon form. Imagine doing all of the Gaussian elimination steps EXCEPT never swapping rows (and you may as well not bother to scale rows since you don't need the diagonal entries of $U$ to be $1$'s). You need to argue that you can do so in such a way that at the end, each of the pivot columns has only non-zero entries in the pivot row and possibly in rows containing previosu pivots. –  Michael Joyce Jan 30 '13 at 20:36
Then you need to argue that when you swap the rows so that the pivots descend as you read from left to right, the resulting matrix ends up having zero entries to the left and below every pivot. Then, up to scaling the rows, the matrix is row echelon, and so in partiuclar is upper triangular. –  Michael Joyce Jan 30 '13 at 20:40
Thanks, Michael. This got me thinking along the right lines, and I think I scribbled the solution down on my connecting flight. I plan on posting it as a complete answer, and if I don't hear anything else brilliant back, eventually accepting your answer as it'd be silly to accept my own. It's a bit lengthy, and want to make it look pretty. –  gnometorule Jan 31 '13 at 2:06
posted how I fully formalized it, in case you're curious...:) –  gnometorule Jan 31 '13 at 21:15

To not distract from the argument, we put some definitions at the end. They are mostly standard.

Note: The usual way to perform Gauss-Elimination on an $A \in Gl_n \left(\mathbb{R^n}\right)$ is to write it as $E_{n-1}P_{n-1} \dots E_2P_2E_1P_1A = U$, for some $E_i \in E$, $P_i\in P$. Our goal is to write it as $$P_{n-1}E_{n-1} \dots P_2E_2P_1E_1A = U \textrm{ (1)}$$ If we succeed, let $$E_{n-1}^{'} := P_1^{-1} \dots P_{n-2}^{-1} E_{n-1} P_{n-2} \dots P_1,$$ $$E_{n-k}^{'} := P_1^{-1} \dots P_{n-k-1}^{-1} E_{n-k} P_{n-k-1} \dots P_1.$$ Then:

$$(1) \Leftrightarrow P_{n-1} \dots P_2P_1E_{n-1}^{'} \dots E_2^{'} E_1^{'}A = U$$ $$\Leftrightarrow : \tilde{P} \tilde{L} A = U$$ $$\Leftrightarrow : A = \bar{L} \bar{P} U,$$ which was to be shown.

To show (1), we will need the following

$\underline{Lemma \textrm{ 3}:}$ Let $M := \begin{pmatrix} A & B \\ 0 & D \end{pmatrix}, A, B, D$ block matrices of suitable dimension. Then $\operatorname{det}(M) = \operatorname{det}(A) \cdot \operatorname{det}(D),$

which is a standard result about determinants.

$\underline{Proposition:}$ If $A \in Gl_n(\mathbb{R})$, there exist $U$ (some upper triangular matrix), $E_i \in E$, and $P_i \in P$ such that $$P_{n-1}E_{n-1} \dots P_2E_2P_1E_1A = U \textrm{ (1)}$$

$\underline{Proof:}$ (by induction on $k, k = 1 \dots n-1$, steps of the modified Gauss algorithm)

$k = 1:$
If $a_{11} \neq 0$, write $A_1 := Id \cdot E_1 A =: P_1 E_1 A$ for some $E_1$, and $$A_1 = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ 0 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\[0.25cm] 0 & a_{n2} & \cdots & a_{nn} \\ \end{pmatrix}$$ If $a_{11} = 0$, there is an $a_{j1} > 0$ (as $A \in GL_n(\mathbb{R})$). Pick the smallest such $j$. Then $A$ is of form: $$A = \begin{pmatrix} 0 & a_{12} & \cdots & a_{1n} \\ \vdots & \vdots & & \vdots \\[0.25cm] 0 & a_{j-1,2} & \cdots & a_{j-1,n} \\ a_{j1} & a_{j2} & \cdots & a_{jn} \\ a_{j+1,1} & a_{j+1,2} & \cdots & a_{j+1,n} \\ \vdots & \vdots & & \vdots \\[0.25cm] a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}$$ Applying an appropriate $E_1$, $$E_1A = \begin{pmatrix} 0 & a_{12} & \cdots & a_{1n} \\ \vdots & \vdots & & \vdots \\[0.25cm] 0 & a_{j-1,2} & \cdots & a_{j-1,n} \\ a_{j1} & a_{j2} & \cdots & a_{jn} \\ 0 & \tilde{a}_{j+1,2} & \cdots & \tilde{a}_{j+1,n} \\ \vdots & \vdots & & \vdots \\[0.25cm] 0 & \tilde{a}_{n2} & \cdots & \tilde{a}_{nn} \end{pmatrix},$$ so $P_{1j}E_1A =: P_1E_1A = A_1$, where
$$A_1 = \begin{pmatrix} a_{j1} & a_{j2} & \cdots & a_{jn} \\ 0 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\[0.25cm] 0 & \tilde{a}_{n2} & \cdots & \tilde{a}_{nn} \\ \end{pmatrix}.$$

$k$ to $k+1$: Note that $P_kE_k \dots P_2E_2P_1E_2A = A_k = \begin{pmatrix} U_k & B \\ 0 & D \\ \end{pmatrix}$, with $U_k$ upper triangular, and $D \in M^{n-k, n-k}$, by induction assumption. As $\operatorname{det}(A_k) = \operatorname{det}(U_k) \cdot \operatorname{det}(D)$ by Lemma 3, and $\operatorname{det}(U_k) \neq 0$ by induction assumption, and $\operatorname{det}(A_k) = \operatorname{det}(A) \prod_{i=1}^{k} \operatorname{det}(P_i) \operatorname{det}(E_i) \neq 0$ (as all factors are), we also have $\operatorname{det}(D) \neq 0$. Hence, there is a non-zero element among $\{ a_{k+1,k+1} \dots a_{n,k+1} \}$. But then, arguing exactly as for $k=1$ (note the $0$ in the lower left of $A_k$), we can find $P_{k+1}, E_{k+1}$ such that $$P_{k+1}E_{k+1} \dots P_2E_2P_1E_2A = A_k = \begin{pmatrix} U_{k+1} & \tilde{B} \\ 0 & \tilde{D} \\ \end{pmatrix}, D \in M^{n-k-1,n-k-1},$$ which was to be shown.

Note: $U$ is not unit-upper triangular, as originally claimed. However, it only takes a simple modification of the above proof to instead get a unit-upper triangular matrix $U$.

$\underline{Definitions}$

Let $L, U \in GL_n(\mathbb{R})$, $U$ be upper triangular, and $L$ lower triangular. Let $P_{ij}$ be the elementary matrix permuting rows $i$ and $j$ when used in multiplication from the left. Let $E_{ij}$ be an elementary matrix that, when applied from the left, adds $c$ times row $j$ to row $i$, where $i > j$, and $c$ is some constant.

$\underline{Lemma \textrm{ 1:}}$ $P_{ij}, E_{ij} \in Gl_n( \mathbb{R} )$, with their inverses being of the same type.

$\underline{Proof:}$ Obvious.

Let $E_i := \prod_{k=1}^{h} E_{i,j_k}$, and $E$ be the space of such lower triangular matrices, $P$ be the space of permutation matrices.

$\underline{Lemma \textrm{ 2:}}$ Let $L := \prod_{i=1}^{n} E_i$. Then $L, L^{-1} \in Gl_n( \mathbb{R})$ are lower triangular.

$\underline{Proof:}$ Obvious.

-
This looks like it is a good approach. I noticed what appears to an error in a smal detail: I don't think your claim on the line that begins $(1) \Leftrightarrow P_{n-1} \cdots$ is correct. I think you want $E'_{n-1} = P_1^{-1} \cdots P_{n-2}^{-1} E_{n-1} P_{n-2} \cdots P_1$ (and similarly for the other $E'_{n-i}$ to get the correct cancellation. –  Michael Joyce Feb 1 '13 at 20:37
I think you're right: I texed this up wrong (also, to be very precise, the last –  gnometorule Feb 1 '13 at 20:53
Matrix with $a_{ij}$ entries needs tildes on the last row). I'll have a look from computer (this is phone), and will correct this later today. Thanks for taking the time to read! –  gnometorule Feb 1 '13 at 20:55
I mean in the second last step you let $\tilde{L}=E_{n-1}' \ldots E_{1}'$. So I think you want each $E'$ to be lower triangular. But it is possible that they are not. Did you know other ways of proof? Thanks! –  Neo Nov 19 '13 at 4:11
They are though. Do you have Artin's book? At the bottom of proof I have it as an obvious lemma. So the proof works as is. I think it would help you most to carefully look at the def in book, and multiply a few, so it should become clear. –  gnometorule Nov 19 '13 at 13:47