# Proof of existence of LU-decomposition

I have a question concerning an existence proof of the $$LU$$-decomposition. The proof is as follows:

If $$E_{ij}$$ denotes the matrix with $$1$$ at row $$i$$, column $$j$$ and zeros elsewhere then I let $$P$$ denote permutation matrices

$$P = \sum_{i=1}^{n}E_{i\sigma(i)}$$

where $$\sigma$$ is a permutation of $$\{1,2,\dotsc,n\}$$ and $$L$$ denote lower triangular matrices of the form

$$L = (I+cE_{ij})$$

where $$i\geq j$$.

Let $$A$$ be a square matrix then we can perform Gaussian elemination by first permutating and then eleminating with $$L$$:

$$\dotsc L_3L_2L_1P_1A$$

for the first row. Continuing this pattern we obtain something of the form

$$L_kP_mL_{k-1}L_{k-2}P_{m-1}\dotsc L_{3}L_{2}L_{1}P_1A = U$$

where $$U$$ is an upper triangular matrix. Now the crucial step which I have trouble believing in is that the author of the proof claims that we can gather all permutations together, obtaining the structure: lower triangle multiplied with permutation. To do this the author claims that $$PL = L'P$$ for $$L$$, $$L'$$ lower triangular and $$P$$ a permutation matrix in general. But this is not the case?

$$P^TLP = \sum_{l=1}^{n}E_{\sigma(l)l}(I+cE_{ij})\sum_{k=1}^{n}E_{k\sigma(k)} = I+cE_{\sigma(i)\sigma(j)}.$$

Why $$(I+cE_{ij})P = P(I+cE_{\sigma(i)\sigma(j)})$$ and now $$i\geq j$$ does not in general imply that $$\sigma(i)\geq \sigma(j)$$ for an arbitrary permutation $$\sigma.$$ We want to write $$LPA = U$$ for some lower triangular matrix $$L$$ and then inverting to obtain $$PA = L'U$$ where $$L'$$ is lower triangular but I dont see how this method works? If I am correct that the proof is false how could it be saved?

• I think if you look closely you'll see that (for example) $P_2$ is a permutation fixing $1$ and so will moved to the right of the elementary operations $L+E_{1,j}$ without any problem. – ancientmathematician Dec 27 '18 at 11:10