Applications of LU-decomposition

You've delved into the intricate world of LU decomposition, a fundamental technique in linear algebra, and mastered the art of decomposing a matrix into lower and upper triangular forms. Now, it's time to harness the power of this knowledge.

We'll uncover its role in solving complex linear systems with ease, unlocking the secrets of matrix inverses, and simplifying the daunting task of calculating determinants. This will equip you with the tools to efficiently tackle real-world problems, making it a skill worth mastering in your mathematical arsenal.

Solving Linear Systems

LU-Decomposition breaks down the process of solving a system of linear equations into two distinct steps: constructing the lower triangular matrix L and the upper triangular matrix U. This separation simplifies the overall procedure, by reducing the complexity of solving linear systems.

Let's illustrate this with an example. You are given three equations, which together form $Ax=b$: $$2x + 3y + z = 8 \\ 4x + 7y + 5z = 20 \\ 2x + 5y + 2z = 10$$The first step in LU-Decomposition is to construct a coefficient matrix $A$ of this system and construct the equation $A = LU$: $$A = \begin{pmatrix} 2 & 3 & 1 \\ 4 & 7 & 5 \\ 2 & 5 & 2 \end{pmatrix} = LU = \begin{pmatrix} 1 & 0 & 0 \\ ? & 1 & 0 \\ ? & ? & 1 \end{pmatrix} \begin{pmatrix} ? & ? & ? \\ 0 & ? & ? \\ 0 & 0 & ? \end{pmatrix}$$After applying the previously learned steps to calculate both $L$ and $U$, the resulting equation looks as follows: $$\begin{pmatrix} 2 & 3 & 1 \\ 4 & 7 & 5 \\ 2 & 5 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 3 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & -5 \end{pmatrix}$$To better understand why we need $L$ and $U$, take a closer look at the equation $Ax=b$ we want to solve. Replacing $A$ with $LU$ results in $LUx = b$. Let's introduce a substitution to make it easier to understand: $y = Ux$. Now we can rewrite the equation as $Ly=b$. We have essentially separated the equation into two steps:

1. First, we solve $Ly=b$ for using forward substitution to find the vector $y$.
   Using the values in $L$, being the lower triangular matrix obtained from LU-Decomposition: $$\begin{align*} L_{11} * y_1 + L_{12} * y_2 + L_{13} * y_3 = b_1 \quad \to \quad 1* y_1 + 0 * y_2 +0* y_3 = 8 \quad \Leftrightarrow \quad y_1 &= 8 \\ L_{21} * y_1 + L_{22} * y_2 + L_{23} * y_3 = b_2 \quad \to \quad 2* 8 + 1 * y_2 +0* y_3 = 20 \quad \Leftrightarrow \quad y_2 &= 4 \\ L_{31} * y_1 + L_{32} * y_2 + L_{33} * y_3 = b_3 \quad \to \quad 1 * 8 + 2 * 4 +1* y_3 = 10 \quad \Leftrightarrow \quad y_3 &= -6 \end{align*}$$
2. Now that we have found the vector $y$, we can solve for the vector $x$ in the equation $Ux = y$, where $U$ is the upper triangular matrix. For this, recall the values of y. Note that we use backward substitution, due to $U$ being a upper triangular Matrix: $$\begin{align*} U_{31} * x_1 + U_{32} * x_2 + U_{33} * x_3 = y_3 \quad \to \quad 0 * x_1 + 0 * x_2 - 5 * x_3 = -6 \quad \Leftrightarrow \quad x_3 &= 1.2 \\ U_{21} * x_1 + U_{22} * x_2 + U_{23} * x_3 = y_2 \quad \to \quad 0 * x_1 + 1 * x_2 + 3 * 1.2 = 4 \quad \Leftrightarrow \quad x_2 &= 0.4 \\ U_{11} * x_1 + U_{12} * x_2 + U_{13} * x_3 = y_1 \quad \to \quad 2 * x_1 + 3 * 0.4 + 1 * 1.2 = 8 \quad \Leftrightarrow \quad x_1 &= 2.8 \end{align*}$$

Therefore, the solution to the system of equations is:

$$\begin{align*} x1 &= 2.8 \quad \quad \quad \quad \quad 2*2.8 + 3*0.4 + 1 * 1.2 = 8 \\ x2 &= 0.4 \quad \implies \quad 4 * 2.8 + 7 * 0.4 + 5 * 1.2 = 20 \\ x3 &= 1.2 \quad \quad \quad \quad \quad 2 * 2.8 + 5 * 0.3 + 2 * 1.2 = 10 \end{align*}$$

Matrix Inversion

LU-Decomposition is also used for matrix inversion, which is crucial in various fields like computer graphics and optimization.

To find the inverse of a matrix $A$ , we can exploit the properties of LU-Decomposition. The key insight is that matrix inversion becomes much simpler when working with triangular matrices like $L$ and $U$:

Now we need to complete two concrete steps:

• Calculating the inverse of $U$ using Gaussian elimination$$in \space \mathbb{R}^3: \begin{pmatrix} U_{11} & U_{12} & U_{13} &|& 1 & 0 & 0 \\ 0 & U_{22} & U_{23} &|& 0 & 1 & 0 \\ 0 & 0 & U_{33} &|& 0 & 0 & 1 \end{pmatrix} \Longrightarrow \begin{pmatrix} 1 & 0 & 0 &|& ? & ? & ? \\ 0 & 1 & 0 &|& ? & ? & ? \\ 0 & 0 & 1 &|& ? & ? & ? \end{pmatrix}$$
• Calculating the inverse of $L$ similarly$$in \space \mathbb{R}^3: \begin{pmatrix} 1 & 0 & 0 &|& 1 & 0 & 0 \\ L_{21} & 1 & 0 &|& 0 & 1 & 0 \\ L_{31} & L_{32} & 1 &|& 0 & 0 & 1 \end{pmatrix} \Longrightarrow \begin{pmatrix} 1 & 0 & 0 &|& ? & ? & ? \\ 0 & 1 & 0 &|& ? & ? & ? \\ 0 & 0 & 1 &|& ? & ? & ? \end{pmatrix}$$

This process becomes incredibly straightforward due to $U$ and $L$ being triangular matrices:

1. Divide/Multiply the row containing only one entry to receive $(1 \space 0 \space 0)$.
2. Subtract a multiple of the constructed row from the other ones to bring the corresponding values down to $0$.
3. Repeat until the Identity matrix $I$ is constructed.

The last step remaining is to multiply both inverses together to receive $A^{-1}$. Voila!

Determinant Calculation

LU-Decomposition aids in calculating determinants of matrices, which are essential in linear algebra and calculus.

Since $L$ is a lower triangular matrix and $U$ is an upper triangular matrix, calculating the determinants of $L$ and $U$ is straightforward:

1. Determinant of $L$ : The determinant of a lower triangular matrix is the product of its diagonal elements. For $L$, this means simply multiplying the elements on its main diagonal: $det(L) = L_{11} * L_{22} * ... * L_{nn}$

2. Determinant of $U$ : Similarly, the determinant of an upper triangular matrix is the product of its diagonal elements: $det(U) = U_{11} * U_{22} * ... * U_{nn}$

Multiplying the determinants of both $L$ and $U$ will result in the determinant of $A$.

Conclusion

In conclusion, LU decomposition is a powerful technique with numerous practical applications that you can greatly benefit from:

• Simplifies the solution of complex linear systems by separating $Ax=b$ into $Ly=b$ and $Ux=y$.
• Facilitates the computation of matrix inverses through splitting the tedious Gaussian elimination process into small, quick pieces.
• Streamlines the determination of matrix determinants by abusing the simpleness of calculating the determinant of a triangular matrix.

Mastering LU decomposition empowers you to tackle real-world mathematical challenges with confidence, making it an invaluable addition to your skill set.