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?

  • $\begingroup$ 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. $\endgroup$ – ancientmathematician Dec 27 '18 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.