# ML Wiki

## $LU$ Factorization

This is the simplest factorization that can be seen as a by-product of Gaussian Elimination

When we do elimination, we have some elimination matrices:

• $E_1 \cdots E_k A = U$, where $E_1 \cdots E_k$ are elimination matrices for each elimination step
• Let $E = E_1 \cdots E_k$

### $LU$

• $E_1 \cdots E_k \ A = U$
• or $EA = U$
• let $L = E^{-1}$, so we have $A = LU$
• $U$ is upper-triangular by construction - because we eliminate all elements down the main diagonal
• $L$ is lower-triangular

$L$

• $L = E^{-1} = (E_1 \cdots E_k)^{-1} = E_k^{-1} \cdots E_1^{-1}$
• $E_i$ have zeros up the diagonal, so when we inverse them, they become lower-diagonal
• when we multiply a bunch of lower-diagonal matrices, we get a lower-diagonal matrix

Types of $LU$ decomposition:

• It's possible to have ones on the main diagonal of either $L$ or $U$
• Doolittle decomposition - the diagonal entries of $L$ are ones
• Crout decomposition - the diagonal entries of $U$ are ones

### $PLU$ Decomposition and Pivoting

• To avoid division by small numbers, we permute rows during the eliminations such that the largest element is the pivot
• We can express row permutation with the permutation matrix P
• Then $PA$ is $A$ with permuted rows, so we have $E \, (PA) = U$
• So the decomposition becomes $PA = LU$

### $LDU$

We can go further:

• and obtain factorization $A = LU = LDU^*$, where $D$ is diagonal
• I.e. we factorize $U = DU^*$
• this way both $L$ and $U$ will have ones on their diagonals - if $L$ had ones and $U$ didn't

## Matrix Inversion with LU Decomposition

To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$

• Let's decompose $A = LU$, so we have: $LUX = I$
• Now let $UX = Y$ and thus $LY = I$
• This gives us two systems:
• first solve $LY = I$ - it's easy because $L$ is lower-triangular, so we just do the forward pass and obtain $Y$
• then we solve $UX = Y$ - it's also easy because $U$ is upper-triangular
• after that we get $X$ which is our inverse
• if we need pivoting, then:
• we solve $PAX = PI = P$
• since $PA = LU$, we have $LUX = P$
• then we solve $LY = P$ and $UX = Y$