Search for a tool
LU Decomposition

Tool to calculate and understand LU decomposition, an efficient method for solving systems of linear equations by factoring via triangular matrices.

Results

LU Decomposition -

Tag(s) : Matrix

Share
dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Feedback and suggestions are welcome so that dCode offers the best 'LU Decomposition' tool for free! Thank you!

# LU Decomposition

## LE Decomposition of a Matrix

 Result Format Automatic Selection Exact Value (when possible) Approximate Numerical Value Scientific Notation

### What is LU Decomposition? (Definition)

LU decomposition is a technique for factoring a square matrix $M$ into two triangular matrices: a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $M = L.U$.

The $L$ matrix has 1s on its diagonal and non-zero elements below the diagonal, while the $U$ matrix has non-zero elements above the diagonal and on the diagonal.

This method facilitates the resolution of systems of linear equations (algebra) and certain calculations such as the matrix determinant or matrix inversion.

### How to calculate an LU Decomposition?

One method to find the LU decomposition of a matrix is to solve linear equations.

Example: Factorize in $L.U$ the matrix $$M = \begin{bmatrix} 1 & 2 \\ 3 & 5 \end{bmatrix} = L \cdot U = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$$ The corresponding equations are: \begin{aligned} 1 \cdot u_{11} + 0 \cdot 0 &= 1 \\ 1 \cdot u_{12} + 0 \cdot u_{22} &= 2 \\ l_{21} \cdot u_{11} + 1 \cdot 0 &= 3 \\ l_{21} \cdot u_{12} + 1 \cdot u_{22} &= 5 \end{aligned} The resolution gives: $$L = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \quad U = \begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}$$

### What are the conditions for using LU Decomposition?

To use LU decomposition, the matrix must be a square matrix (same number of rows and columns).

The matrix (or one of its row permutations) must be invertible. Some matrices may require row permutations to enable factorization, giving rise to LU decomposition with pivoting.

Example: If $M_{11} = 0$ then as $M_{11} = l_{11} \cdot u_{11}$, either $l_{11}$ or $u_{11}$ must be zero, which implies that $L$ or $U$ is a singular (non-invertible) matrix. It is then necessary to permute the rows of $M$ so that the first element of the permuted matrix is non-zero.

### What is pivoting in LU Decomposition?

Pivoting in LU decomposition consists of permuting the rows of matrix A to avoid zeros on the main diagonal of matrix U.

If pivoting is required, dCode reports the permutation matrix $P$ and the resulting modified matrix $P.M$. The matrices $L$ and $U$ found are such that $L.U = P.M$

## Source code

dCode retains ownership of the "LU Decomposition" source code. Except explicit open source licence (indicated Creative Commons / free), the "LU Decomposition" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "LU Decomposition" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "LU Decomposition" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.

## Cite dCode

The copy-paste of the page "LU Decomposition" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
LU Decomposition on dCode.fr [online website], retrieved on 2024-07-18, https://www.dcode.fr/matrix-lu-decomposition

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!