Teorem 1 (Trappedekomposisjon) For enhver matrise A finnes en permutasjonsmatrise P, en nedre triangulær matrise L med enere på diagonalen, og en matrise U på trappeform slik at P A = LU.

Bevis: Dette vises ved induksjon på antall søyler i A. Hvis A har bare en søyle, er A allerede på trappeform, så vi kan skrive P = I, L = I og U = A.

Anta nå at teoremet holder for matriser A med n søyler (dette kaller vi induksjonshypotesen) og la A ha n + 1 søyler.

Hvis første søyle i A har bare nuller, skriver vi A = [0 Ã] der den første nullen står for første søyle i A og Ã har n søyler. Ved induksjonshypotesen kan vi skrive en trappedekomposisjon P Ã = LŨ, men da er P A = P [0 Ã] = [0 P Ã] = [0 LŨ] = LU der U = [0 Ũ] er på trappeform.

Litt vanskeligere blir det om første søyle i A ikke har bare nuller. Velg et rekkenummer i slik at a_{i1} ≠ 0, og la P_{1} være permutasjonsmatrisen som bytter om rekkene 1 og i, slik at P_{1}A har a_{i1} ≠ 0 i øverste venstre hjørne. Bruk denne til å eliminere alle andre elementer i første søyle: Det vil at vi kan finne en matrise L_{1} slik at P_{1}A = L_{1}U_{1} der

L_{1} = [\begin{matrix}1 & 0 & … & 0 \\ l_{21} & 1 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ l_{m1} & 0 & … & 1 \end{matrix}] = [\begin{matrix}1 & 0 \\ ℓ & I \end{matrix}] , U_{1} = [\begin{matrix}a_{i1} & a_{i2} & … & a_{in} \\ 0 & ∗ & … & ∗ \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & ∗ & … & ∗ \end{matrix}] = [\begin{matrix}a_{i1} & u \\ 0 & Ã \end{matrix}]

(Om vi fjerner første rad og søyle i U_{1}, står vi igjen med matrisen fylt med ∗ … ∗, som vi kaller Ã. u er en rekkevektor, og 0 i annen rekke er en søylevektor. På samme måte er ℓ en søylevektor. Jeg skriver flere 2 × 2-matriser nedenfor, der i virkeligheten nederste høyre hjørne er en matrise, øverste venstre hjørne er skalar, og de to andre elementene er vektorer slik at dimensjonene passer).

Ved induksjonshypotesen anvendt på Ã kan vi skrive trappedekomposisjonen P̃Ã = L̃Ũ. Setter vi

P = [\begin{matrix}1 & 0 \\ 0 & P̃ \end{matrix}] P_{1}, L̃_{1} = [\begin{matrix}1 & 0 \\ 0 & P̃ \end{matrix}] L_{1} [\begin{matrix}1 & 0 \\ 0 & P̃^{T} \end{matrix}]

så blir

P A = L̃_{1} [\begin{matrix}a_{i1} & u \\ 0 & P̃Ã \end{matrix}] = L̃_{1} [\begin{matrix}a_{i1} & u \\ 0 & L̃Ũ \end{matrix}] = LU

der

L = L̃_{1} [\begin{matrix}1 & 0 \\ 0 & L̃ \end{matrix}] , U = [\begin{matrix}a_{i1} & u \\ 0 & Ũ \end{matrix}]

Det gjenstår å sjekke at L og U virkelig har de rette formene, men det overlater vi til leseren. □