3.6. The \(LU\) decomposition

As we have seen, one way to solve a linear system \(A\vect{x}=\vect{b}\) is to row reduce it to echelon form and then use back substitution. See for instance Example 2.1.8.
In this section we will learn how to solve an \(m\times n\) linear system \(A\mathbf{x}=\mathbf{b}\) by decomposing (or factorising) a matrix into a product of two ‘special’ matrices \(L\) and \(U\). This is called an \(LU\)-decomposition of the matrix \(A\).

Example 3.6.1

Consider the system \(A\mathbf{x} = \mathbf{b}\) where

\[\begin{split} A = \begin{bmatrix} 1 & 1 & -1 \\ 2 & 4 & -3 \\ 1 & -1 & -3 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 2 \\ 1 \\8 \end{bmatrix} = LU. \end{split}\]

To start with, the matrix \(A\) can be factorized as

\[\begin{split} A = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & -1 \\ 0 & 2 & -1 \\ 0 & 0 & 3 \end{bmatrix}. \end{split}\]

We will see how this helps to solve the system in an efficient way.

With this factorisation we can solve the system in two steps, using both backward and forward substitution. In fact, the matrix \(U\) is an echelon matrix equivalent to \(A\). To solve the equation \(LU\vect{x} = L(U\vect{x}) =\vect{b}\) we can introduce the auxiliary vector \(\vect{y}\) via

\[ \vect{y} = U\vect{x}. \]

We then first solve

(3.6.1)\[ L\vect{y} = \vect{b}\]

and after that we find \(\mathbf{x}\) by solving

\[ U\vect{x} = \tilde{\vect{y}}, \]

for the solution \( \tilde{\vect{y}}\) of system (3.6.1). For this solution \( \tilde{\vect{x}}\) we then have

\[ A \tilde{\vect{x}} = L\,U\, \tilde{\vect{x}} = L(U\tilde{\vect{x}})= L\tilde{\vect{y}} = \vect{b}. \]

We illustrate matters with the linear system of example Example 3.6.1

Example 3.6.2

The system \(A\vect{x} = \vect{b}\) of Example 3.6.1 can be written as

\[\begin{split} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 6 \\ 0 & 0 & 4 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\8 \end{bmatrix}. \end{split}\]

By setting \(\mathbf{y} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 6 \\ 0 & 0 & 4 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \\ x_3 \end{bmatrix}\) we have

\[\begin{split} \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -1 & 1 \end{bmatrix} \begin{bmatrix} y_1\\y_2\\y_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 8 \end{bmatrix}, \quad \text{i.e.,}\,\, \left\{\begin{array}{ccccccc} y_1 & & & & &=& 2 \\ 2y_1 &+& y_2 & & &=& 1 \\ y_1 &-& y_2 &+& y_3 &=& 8. \end{array} \right.\end{split}\]

With forward substitution we can find the solution:

\[\begin{split} \begin{array}{ll} y_1 = 2 & \Longrightarrow \quad y_2 = 1 - 2y_1 = -3 \\ & \Longrightarrow \quad y_3 = 8 - y_1 + y_2 = 3 \quad \Longrightarrow \quad \begin{bmatrix} y_1\\y_2\\y_3 \end{bmatrix} = \begin{bmatrix} 2 \\ -3 \\ 3 \end{bmatrix} \end{array} \end{split}\]

Next we solve

\[\begin{split} \begin{bmatrix} 1 & 1 & -1 \\ 0 & 2 & -1 \\ 0 & 0 & -3 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ -3 \\ 3 \end{bmatrix}, \end{split}\]

by back substitution. This gives the solution

\[\begin{split} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 3\\ -2 \\ -1 \end{bmatrix}, \end{split}\]

which is the solution to our original system. Since the factorisation was given, we did not have to solve the system from scratch by trying to find an echelon form.

Here is one to try for yourself.

Grasple Exercise 3.6.1

To solve a system \(LU\vect{x} = \vect{b}\).

Show/Hide Content

There are several methods for factorising matrices. The factorisations that we will see in this section use direct methods. Direct methods are methods that produce the exact factorisations in a finite number of steps.

In the next subsection we will address the questions of whether an \(LU\) decomposition always exists and if so, how to construct it. With an extra condition on \(L\) the decomposition, if it exists, will be unique. In the case where an \(LU\) decomposition does not exist we can instead consider the slightly more general \(PLU\) decomposition. In the remainder of the section we will consider the generalization to non-square matrices and we will analyze to which extent the \((P)LU\) decomposition gives an efficiency boost.

3.6.1. \(LU\) decomposition of a square matrix

Definition 3.6.1

Let \(A\) be an \(n\times n\) matrix. An \(LU\) decomposition of \(A\) is a factorization of the type

\[ A=LU \]

where \(L\) is an \(n\times n\) lower triangular matrix with \(1\)s on the diagonal, and \(U\) an \(n\times n\) upper triangular matrix. So,

\[\begin{split} L= \begin{bmatrix} 1\\ l_{21} & 1 \\ l_{31} & l_{32} & \ddots \\ \vdots & \vdots & \ddots & \ddots\\ l_{n1} & l_{n2} & \cdots & l_{n(n-1)} & 1 \end{bmatrix} , \quad U= \begin{bmatrix} u_{11} & u_{12} & u_{13} & \cdots &u_{1n} \\ & u_{22} & u_{23} & \cdots & u_{2n} \\ & & u_{33} & \cdots & u_{3n} \\ & & & \ddots & \vdots \\ & & & & u_{nn} \end{bmatrix}. \end{split}\]

For convenience we have used blanks for zeros.

The next proposition captures the main interest of the \(LU\) decomposition, as is already illustrated in Example 3.6.2

Algorithm 3.6.1

Suppose that \(A=LU\), so that a linear system of equations \(A\mathbf{x}=\mathbf{b}\) can be written as \(LU\mathbf{x}=\mathbf{b}\). Then, by setting \(\mathbf{y} = U\mathbf{x}\), we can solve the linear system in two steps.

1. Solve the system \(L\mathbf{y}=\mathbf{b}\) and find \(\mathbf{y}\).

2. Solve the system \(U\mathbf{x}=\mathbf{y}\) to find \(\mathbf{x}\).

The solution of the second system is then a solution of the system \(A\mathbf{x}=\mathbf{b}\).

The next proposition tells us which matrices do have an \(LU\) decomposition.

Proposition 3.6.1

A matrix \(A\) can be written as \(A = LU\), with \(L\) and \(U\) as described in Definition 3.6.1 if and only it can be row reduced to an echelon matrix with only additions of multiples of rows to rows below it. We will call this a top-down row reduction.

Instead of a giving a formal proof, we will illustrate matters first with an example. In this example you will see how an \(LU\)-decomposition of a matrix is found via a top-down row reduction that keeps track of the row operations involved.

Example 3.6.3

We consider the matrix

\[\begin{split} A= \begin{bmatrix} 3 & 1 & -2 \\ 2 & 4 & 1 \\ 1 & 2 & 1 \end{bmatrix} . \end{split}\]

To find an \(LU\) decomposition we will work towards an echelon form in the top-down direction. In addition, we will keep track of the actions we perform. For the first step,

\[\begin{split}\left[\begin{array}{rrr}3 & 1 & -2\\2 & 4 & 1\\1 & 2 & 1\end{array} \right] \begin{array}{l} [R_1] \\ {[R_2-2/3R_1]} \\ {[R_3-1/3R_1]} \\ \end{array} \quad\sim\quad \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} = A_2. \end{split}\]

The numbers \(2/3\) and \(1/3\) are called multipliers.

A second row reduction step, involving the multiplier \(1/2\), leads to an echelon/upper triangular matrix.

\[\begin{split}\left[\begin{array}{rrr}3 & 1 & -2\\0 &{10}/{3}&{7}/{3}\\0 &{5}/{3}&{5}/{3}\end{array} \right] \begin{array}{l} [R_1] \\ {[R_2]} \\ {[R_3-1/2R_2]} \\ \end{array}\sim \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & 0 & {1}/{2} \end{bmatrix} = A_3. \end{split}\]

We can effectuate these row operations by matrix multiplications.

\[\begin{split} F_1A = \begin{bmatrix} 1 & 0 & 0 \\ -2/3 & 1 & 0 \\ -1/3 & 0 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 2 & 4 & 1 \\ 1 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} = A_2. \end{split}\]

In the same way the second row reduction step can be described by

\[\begin{split} F_2A_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1/2 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} = \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & 0 & {1}/{2} \end{bmatrix} = A_3.\end{split}\]

The echelon matrix \(A_3\) can act as our upper triangular matrix \(U\), and the above computations can be summarized as

\[\begin{split} U = A_3 = F_2F_1A = FA = \begin{bmatrix} 1 & 0 & 0 \\ -2/3 & 1 & 0 \\ 0 & -1/2 & 1 \end{bmatrix} A, \end{split}\]

where \(F = F_2F_1\).

We conclude that

\[\begin{split} A = F^{-1} U = \begin{bmatrix} 1 & 0 & 0 \\ 2/3 & 1 & 0 \\ 1/3 & 1/2 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & 0 & {1}/{2} \end{bmatrix}\end{split}\]

which is indeed a product of a lower triangular matrix \(L\) (with 1’s on its diagonal) and an upper triangular matrix \(U\).

The above procedure shows how in principle an \(LU\) decomposition can be computed. However, writing down the explicit elementary like matrices \(F_i\), computing their product \(F\), and finding the inverse of \(F\) is unnecessary. Look at the matrix \(L = F^{-1}\) we found! The entries below the diagonal are exactly the numbers \(2/3\), \(1/3\) and \(1/2\) we called the multipliers. The following algorithm describes this ‘shortcut’ to find an \(LU\) decomposition.

Algorithm 3.6.2

Suppose the \(n\times n\) matrix \(A\) can be row reduced top-down to the echelon matrix \(U\). If the numbers \(m_{jk}\) denote the multiples of the \(k\)th row that are subtracted from the rows below it in the \(k\)th step (so \(1 \leq k < j \leq n\)),   then

\[\begin{split} A = LU, \quad \text{for} \,\, L = \begin{bmatrix} 1\\ m_{21} & 1 \\ m_{31} & m_{32} & \ddots \\ \vdots & \vdots & \ddots & \ddots\\ m_{n1} & m_{n2} & \cdots & m_{n,n-1} & 1 \end{bmatrix}. \end{split}\]

Another look at Example 3.6.3 explains why the detour via the matrices \(F_i\) and the inverse of their product can be skipped, as is expressed in the above algorithm.

Example 3.6.4

For the matrix \(A= \begin{bmatrix} 3 & 1 & -2 \\ 2 & 4 & 1 \\ 1 & 2 & 1 \end{bmatrix}\).

The ‘trick’ is not to work with the matrices \(F_1\) and \(F_2\), but with their inverses.

The first row reduction step

\[\begin{split} F_1A = \begin{bmatrix} 1 & 0 & 0 \\ -2/3 & 1 & 0 \\ -1/3 & 0 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 2 & 4 & 1 \\ 1 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} = A_2. \end{split}\]

can be rewritten as

\[\begin{split} A = F_1^{-1}A_2 = L_1A_2 = \begin{bmatrix} 1 & 0 & 0 \\ 2/3 & 1 & 0 \\ 1/3 & 0 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} \end{split}\]

Likewise the second row reduction step

\[\begin{split} F_2A_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1/2 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix} = \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & 0 & {1}/{2} \end{bmatrix} \end{split}\]

can be can be represented as

\[\begin{split} A_2 = F_2^{-1}A_3 = L_2U = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1/2 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & {5}/{3} & {5}/{3} \end{bmatrix}.\end{split}\]

Combining the two equations gives

\[\begin{split} A = L_2L_1U = LU = \begin{bmatrix} 1 & 0 & 0 \\ 2/3 & 1 & 0 \\ 1/3 & 1/2 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 & -2 \\ 0 & {10}/{3} & {7}/{3} \\ 0 & 0 & {1}/{2} \end{bmatrix}. \end{split}\]

We see the multipliers nicely fall into place!

Here is an example where we apply the algorithm applied without further ado to a \(4 \times 4\) matrix.

Example 3.6.5

We use the \(LU\)-algorithm to the matrix \(A = \begin{bmatrix} 2 & 1 & -2 & 3 \\ 2 & -3 & -4 & 7 \\ -4 & 0 & -2 & -5 \\ -6 & -1 & 8 & -8 \end{bmatrix}.\)

We row reduce the matrix \(A\) top-down, diligently registering the multipliers. Recall that the multiplier \(m_{jk}\) is defined as the multiple of row \(k\) that is subtracted from row \(j\) in the \(k\)-th step of the reduction process.

Here we go:

\[\begin{split} \left[\begin{array}{rrrr} 2 & 1 & -2 & 3 \\ 2 & -3 & -4 & 7 \\ -4 & 0 & -2 & -5 \\ 6 & 1 & -8 & 8\end{array} \right] \begin{array}{l} [R_1] \\ {[R_2-\class{red}{1}R_1]} \\ {[R_3-\class{red}{(-2)}R_1]} \\ {[R_4-\class{red}{3}R_1]} \\ \end{array} \sim \left[\begin{array}{rrrr} 2 & 1 & -2 & 3 \\ 0 & -4 & -2 & 4 \\ 0 & 2 & 2 & 1 \\ 0 & -2 & -2 &-1\end{array} \right] \begin{array}{l} [R_1] \\ [R_2] \\ {[R_3-\class{blue}{(-1/2)}R_2]} \\ {[R_4-\class{blue}{1/2}R_2]} \\ \end{array} \end{split}\]

\[\begin{split} \sim \left[\begin{array}{rrrr} 2 & 1 & -2 & 3 \\ 0 & -4 & -2 & 4 \\ 0 & 0 & -3 & 3 \\ 0 & 0 & -1 & -3 \end{array} \right] \begin{array}{l} [R_1] \\ [R_2] \\ {[R_3]} \\ {[R_4-\class{green}{1/3}R_2]} \\ \end{array} \,\,=\,\, \left[\begin{array}{rrrr} 2 & 1 & -2 & 3 \\ 0 & -4 & -2 & 4 \\ 0 & 0 & -3 & 3 \\ 0 & 0 & 0 & -4 \end{array} \right] \,\,\sim\,\, U. \end{split}\]

Putting every multiplier in its right place gives

\[\begin{split} L = \left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ \class{red}{1} & 1 & 0 & 0 \\ \class{red}{-2} & \class{blue}{-1/2} & 1 & 0 \\ \class{red}{3} & \class{blue}{1/2} & \class{green}{1/3} & 1 \end{array} \right]. \end{split}\]

Example 3.6.6

For the matrix \(A= \begin{bmatrix} 1 & 2 & 1 \\ 4 & 8 & 6 \\ 2 & 5 & 4 \end{bmatrix}\) the procedure breaks down at the second step.

\[\begin{split} \begin{bmatrix} 1 & 2 & 1 \\ 4 & 8 & 6 \\ 2 & 5 & 7 \end{bmatrix} \begin{array}{l} [R_1] \\ {[R_2-4R_1]} \\ {[R_3-2R_1]} \end{array} \quad \sim \quad \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 2 \\ 0 & 1 & 5 \end{bmatrix}. \end{split}\]

The next step towards an echelon matrix needs a row swap. But then the lower triangular structure of \(L\) will be broken. In Subsection 3.6.2 we will study what we can do in such a situation.

Here’s one to try for yourself.

Grasple Exercise 3.6.2

To compute the \(LU\)-decomposition of a 3x3 matrix \(A\).

Show/Hide Content

People that are not satisfied with two examples to show that Algorithm 3.6.2 works can have a look at the following (informal) proof of Proposition 3.6.1. It will also prove the statement that the existence of a \(LU\) decomposition of a matrix \(A\) implies that the matrix \(A\) can be row reduced top-down to a matrix in echelon form.

Proof of Proposition 3.6.1

Suppose \(A\) is an \(n\times n\) matrix that can be row reduced top down to an echelon matrix \(U\) matrix (which will then be an upper triangular). We can row reduce \(A\) from top to bottom, where we use the same form as in Example 3.6.4. For instance the first two steps are

\[\begin{split} A = \begin{bmatrix} a_{11} & a_{12}& a_{13} & \ldots& a_{1n} \\ a_{21} & a_{22}& a_{23} & \ldots& a_{2n} \\ a_{31} & a_{32}& a_{33} & \ldots& a_{3n} \\ \vdots & \vdots& \vdots& & \vdots \\ a_{n1} & a_{n2}& a_{n3}& \ldots& a_{nn} \end{bmatrix} = L_1A_2 = \begin{bmatrix} 1 & \\ m_{21} & 1 \\ m_{31} & 0 & 1 \\ \vdots & \vdots& & \ddots \\ m_{n1} & 0 & \ldots& & 1 \end{bmatrix}A_1 \end{split}\]

where \(A_2\) will be of the form

\[\begin{split} A_2 = \begin{bmatrix} a_{11} & a_{12} & a_{13} & \ldots & a_{1n} \\ 0 & \tilde{a}_{22} & \tilde{a}_{23} & \ldots &\tilde{a}_{2n} \\ 0 & \tilde{a}_{32} & \tilde{a}_{33} & \ldots &\tilde{a}_{3n} \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & \tilde{a}_{n2} & \tilde{a}_{n3} & \ldots &\tilde{a}_{nn} \\ \end{bmatrix}. \end{split}\]

On the next step will lead to

\[\begin{split} A_2 = L_2A_3 = \begin{bmatrix} 1 & \\ 0 & 1 & \\ 0 &m_{32} & 1 \\ \vdots & \vdots& & \ddots \\ 0 & m_{n2} & 0 & \ldots& & 1 \end{bmatrix}A_3, \end{split}\]

where \(A_3\) will be of the form

\[\begin{split} A_2 = \begin{bmatrix} a_{11} & a_{12} & a_{13} & \ldots & a_{1n} \\ 0 & \tilde{a}_{22} & \ast & \ldots & \ast \\ 0 & 0 & {a}^{\ast}_{33} & \ldots &\ast \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & \ast & \ldots &\ast \\ \end{bmatrix}. \end{split}\]

We thus end up with a product

\[ A = L_{n-1}L_{n-2}\cdots L_2L_1\,U = L\,U, \]

where each matrix \(L_k\) is a matrix containing the multipliers of the \(k\)th step in the proces.

The crucial thing is that in the product \(L_{n-1}L_{n-2}\cdots L_2L_1\) in this order the multipliers do not ‘interact’. For instance, for \(n = 4\), we would get

(3.6.2)\[ \begin{align}\begin{aligned}\begin{split} \begin{array}{l} L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ m_{21} & 1 & 0 & 0 \\ m_{31} & 0 & 1 & 0 \\ m_{41} & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & m_{32} & 1 & 0 \\ 0 & m_{42} & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & m_{43} & 1 \end{bmatrix} = \\ = \begin{bmatrix} 1 & 0 & 0 & 0 \\ m_{21} & 1 & 0 & 0 \\ m_{31} & 0 & 1 & 0 \\ m_{41} & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & m_{32} & 1 & 0 \\ 0 & m_{42} & m_{43} & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ m_{21} & 1 & 0 & 0 \\ m_{31} & m_{32} & 1 & 0 \\ m_{41} & m_{42} & m_{43} & 1 \end{bmatrix}. \end{array} \end{split}\\The pattern is clear, we skip the technical details to prove it for $n\times n$ matrices. \\ To prove the converse, assume that $A$ has an $LU$ decomposition, i.e.,\\\begin{split} $$ A = LU = \left[\begin{array}{rrrrr} 1 & & & \\ \ell_{11} & 1 & & \\ \ell_{21} & \ell_{32} & 1 & \\ \vdots & \vdots & \vdots & \ddots & \\ \ell_{n1} & \ell_{n2}& \ell_{n3} & \cdots & 1 \\ \end{array} \right] \begin{bmatrix} u_{11} & u_{12} & u_{13} & \cdots &u_{1n} \\ & u_{22} & u_{23} & \cdots & u_{2n} \\ & & u_{33} & \cdots & u_{3n} \\ & & & \ddots & \vdots \\ & & & & u_{nn} \end{bmatrix}. $$\end{split}\\By {prf:ref}`Prop:LUdecomp:L-properties` the inverse of $L$ has the same structure as $L$, i.e.,\\\begin{split}$$ \left[\begin{array}{rrrrr} 1 & & & \\ \ell^{\ast}_{11} & 1 & & \\ \ell^{\ast}_{21} & \ell^{\ast}_{32} & 1 & \\ \vdots & \vdots & \vdots & \ddots & \\ \ell^{\ast}_{n1} & \ell^{\ast}_{n2}& \ell^{\ast}_{n3} & \cdots & 1 \\ \end{array} \right]. $$ \end{split}\\As in the proof of the first half ({eq}`Eq:LUdecomp:multipliers`), $L^{-1}$ can be factorized as \\\begin{split}$$ L_1L_3\cdots L_{n-1} = \left[\begin{array}{rrrrr} 1 & & & \\ \ell^{\ast}_{11} & 1 & & \\ \ell^{\ast}_{21} & 0 & 1 & \\ \vdots & \vdots & \vdots & \ddots & \\ \ell^{\ast}_{n1} & 0 & 0 & \cdots & 1 \\ \end{array} \right] \left[\begin{array}{rrrrr} 1 & & & \\ 0 & 1 & & \\ 0 & \ell^{\ast}_{32} & 1 & \\ \vdots & \vdots & \vdots & \ddots & \\ 0 & \ell^{\ast}_{n2}& 0 & \cdots & 1 \\ \end{array} \right] \cdots \left[\begin{array}{rrrrr} 1 & & & \\ 0 & 1 & & \\ 0 & 0 & 1 & \\ \vdots & \vdots & \vdots & \ddots & \\ 0 & 0 & \cdots & \ell^{\ast}_{n-1,n} & 1 \\ \end{array} \right] $$\end{split}\\Pre-multiplication of a matrix $M$ with one of the matrices $L_k$ amounts to adding multiples of the $k$th row of $M$ to the lower rows. So the product $L_2L_3\cdots L_n$ is a series of top-down operations, and\\$$ L_2L_3\cdots L_n\, A = U $$\\amounts to a top-down row reduction of $A$ to the upper triangular matrix $U$.\end{aligned}\end{align} \]

At the end of this section we will analyze whether an \(LU\) decomposition if it exists, is unique. To answer that question we need the following properties of lower as well as upper triangular matrices.

Proposition 3.6.2

Suppose \(A\) and \(B\) are lower triangular matrices with \(1\)s on their diagonals. Then the following properties hold.

1. \(AB\) is also a lower triangular matrix with \(1\)s on its diagonal.

2. \(A^{-1}\) is also a lower triangular matrix with \(1\)s on its diagonal.

In both properties ‘lower’ can be replaced by ‘upper’.

There are several ways to prove Proposition 3.6.2. The best would be to think of a proof yourself, but you can also have a peek at the exposition below.

Proof of Proposition 3.6.2

1. Suppose \(A\) and \(B\) are lower triangular matrices with \(1\)s on their diagonals.

   One way to prove that \(AB\) also has these properties is to use the column-row expansion of the product. (Cf. Exercise 3.2.8.)
   Let \(\vect{a}_k\) be the \(k\)th column of \(A\), and \(\vect{b}^{(k)}\) the \(k\)th row of \(B\). Then

   \[\begin{split} \vect{a}_k = \begin{bmatrix}0 \\ \vdots \\ 0 \\ a_{kk} \\ \vdots \\ a_{nk} \end{bmatrix} \quad \text{and} \quad \vect{b}_{(k)} = \begin{bmatrix}b_{k1} & \cdots & b_{kk} & 0 & \cdots & 0 \end{bmatrix}, \end{split}\]

   where moreover \(a_{kk} = b_{kk} = 1\). So the \(k\)th term in the column-row expansion of \(AB\) becomes

   \[\begin{split} \begin{array}{rcl} \vect{a}_k\vect{b}^{(k)} &=& \begin{bmatrix}b_{k1}\vect{a}_k & b_{k2}\vect{a}_k & \cdots & b_{kk}\vect{a}_k & \vect{0} & \cdots & \vect{0}\end{bmatrix} \\ &=& \begin{bmatrix} 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ a_{kk}b_{k1} & a_{kk}b_{k2} & \cdots & a_{kk}b_{kk} & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ a_{nk}b_{k1} & a_{nk}b_{k2} & \cdots & a_{nk}b_{kk} & 0 & \cdots & 0 \end{bmatrix} \end{array}. \end{split}\]

   This is a lower triangular matrix, with a \(1\) on position \((k,k)\) and for the rest \(0\)s on the diagonal. Adding these \(n\) column-row products gives a matrix of the required form.

2. Next suppose that \(A\) is an upper triangular matrix with \(1\)s on the diagonal. If we apply the algorithm of Proposition 3.4.7 to find the inverse using the augmented matrix

   \[\begin{split} [\,A | I \,] = \left[\begin{array}{ccccc|ccccc} 1 & 0 & 0 & \cdots & 0 & 1 & 0 & 0 & \cdots & 0 \\ a_{21} & 1 & 0 & \cdots & 0 & 0 & 1 & 0 & \cdots & 0 \\ a_{31} & a_{32} & 1 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 \\ \vdots &\vdots & & \ddots & 0 & \vdots & \vdots & & \ddots & 0 \\ a_{n1} &a_{n2} & a_{n3} & \cdots & 1 & 0 & 0 & 0 & \cdots & 1 \end{array} \right], \end{split}\]

   to row reduce \(A\) to \(I\) we only need to subtract multiples of rows from rows below it. Thus in the matrix to the right of the bar, where the identity matrix is transformed into the inverse matrix of \(A\), the triangular structure with \(1\)s on the diagonal remains.

The uniqueness issue is not of major importance, but for completeness’ sake we phrase it in a proposition, followed by a possible argument to prove it.

Proposition 3.6.3

For an invertible matrix \(A\), if it has an \(LU\)-decomposition, it will be unique.

Proof of Proposition 3.6.3.

Suppose \(A\) is an invertible matrix with two \(LU\) decompositions

\[ A = L_1U_1, \quad A = L_2U_2. \]

We then have to show that

\[ L_1=L_2 \quad \text{and} \quad U_1 = U_2. \]

Since \(A\) is invertible, the matrices \(L_1, L_2, U_1, U_2\) are also invertible.
From

\[ L_1U_1 = L_2U_2 \]

it follows that

(3.6.3)\[ L_2^{-1}L_1 = U_2U_1^{-1}.\]

From Proposition 3.6.2 we know that \(L_2^{-1}\) is a lower triangular matrix with \(1\)s on the diagonal, and that the product \(L_2^{-1}L_1\) is also of this form. At the same time the product \(U_2U_1^{-1}\) must be an upper triangular matrix with \(1\)s on its diagonal. Then (3.6.3) implies that

\[ L_2^{-1}L_1 = U_2U_1^{-1} = I, \]

from which the identities

\[ L_1 = L_2, \quad U_1 = U_2 \]

immediately follow.

Lastly we give an example to show that the uniqueness may fail for a singular matrix.

Example 3.6.7

For the matrix \(A = \begin{bmatrix} 1 & 1 & 1 \\ 2 & 2 & 2 \\ 3 & 3 & 3 \end{bmatrix}\) it holds that

\[\begin{split} A = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & a & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \end{split}\]

where the parameter \(a\) is free to choose.

3.6.2. Generalization to non-square matrices and \(PLU\) decomposition

In this section we describe what can be said regarding \(LU\) decompositions for non-square matrices, and present a ‘workaround’ for matrices for which there is no top-down row reduction to echelon form.

We start with an example to show that not much changes if we apply Algorithm 3.6.2 to non-square matrices.

Example 3.6.8

The matrix \(A\) is given by

\[\begin{split} A = \begin{bmatrix} 1 & 3 & 1 & -1 \\ -1 & 1 & 1 & 2 \\ 2 & -2 & -1 & 3 \end{bmatrix}. \end{split}\]

We can row reduce \(A\) top-down to an echelon matrix:

\[\begin{split} \begin{array}{rcl} \begin{bmatrix} 1 & 3 & 1 & -1 \\ -1 & 1 & 1 & 2 \\ 2 & -2 & -1 & 3 \end{bmatrix} \begin{array}{l} [R_1] \\ {[R_2-\class{blue}{(-1)}R_1]} \\ {[R_3-\class{blue}{2}R_1]} \\ \end{array} & \sim & \begin{bmatrix} 1 & 3 & 1 & -1 \\ 0 & 4 & 2 & 1 \\ 0 & -8 & -3 & 5 \end{bmatrix} \begin{array}{l} [R_1] \\ {[R_2]} \\ {[R_3-\class{blue}{(-2)}R_2]} \\ \end{array}\\ &\sim& \begin{bmatrix} 1 & 3 & 1 & -1 \\ 0 & 4 & 2 & 1 \\ 0 & 0 & 1 & 7 \end{bmatrix}. \end{array} \end{split}\]

We then have

\[\begin{split} A = LU = \begin{bmatrix} 1 & 0 & 0 \\ \class{blue}{-1} & 1 & 0 \\ \class{blue}{2} & \class{blue}{-2} & 1 \end{bmatrix} \begin{bmatrix} 1 & 3 & 1 & -1 \\ 0 & 4 & 2 & 1 \\ 0 & 0 & 1 & 7 \end{bmatrix}. \end{split}\]

If we want to solve an equation like

\[ A\vect{x}= \vect{b}, \]

we can use the same two-step procedure as in Example 3.6.2.

For instance, to solve the system

\[\begin{split} LU\vect{x} = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 3 & 1 & -1 \\ 0 & 4 & 2 & 1 \\ 0 & 0 & 1 & 7 \end{bmatrix}\vect{x} = \begin{bmatrix}2 \\ -2 \\ 5 \end{bmatrix} \end{split}\]

we can first solve

\[\begin{split} L\vect{y} = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -2 & 1 \end{bmatrix}\vect{y} = \begin{bmatrix}2 \\ -2 \\ 5 \end{bmatrix}. \end{split}\]

Using forward substitution we find the solution

\[\begin{split} \tilde{\vect{y}} = \begin{bmatrix}2 \\ 0 \\ 1 \end{bmatrix} \end{split}\]

and then the system

\[\begin{split} U\vect{x} = \begin{bmatrix} 1 & 3 & 1 & -1 \\ 0 & 4 & 2 & 1 \\ 0 & 0 & 1 & 7\end{bmatrix}\vect{x} = \begin{bmatrix}2 \\ 0 \\ 1 \end{bmatrix} \end{split}\]

gives the solution(s)

\[\begin{split} \vect{x} = \begin{bmatrix} \tfrac52 -\tfrac{7}{4}x_4\\ -\tfrac12 +\tfrac{13}{4}x_4\\ 1 - 7x_4\\ x_4 \end{bmatrix}, \quad x_4 \,\, \text{free.} \end{split}\]

The generalization of Proposition 3.6.1 to non-square matrices is captured in the next proposition.

Proposition 3.6.4

An \(m\times n\) matrix \(A\), with \(m \leq n\) can be written as \(A = LU\), with \(L\) an \(m\times m\) upper triangular matrix with \(1\)s on its diagonal and \(U\) an echelon matrix if and only if \(A\) can be row reduced top-down to the echelon matrix \(U\).
Moreover, if the rows of \(A\) are linearly independent the matrices \(L\) and \(U\) are unique.

A similar proposition holds for \(m \times n\) matrices with \(m > n\). However, in this case the systems \(A\vect{x} = \vect{b}\) are inconsistent for most vectors \(\vect{b}\), and then other techniques come into play (e.g., see Section 7.4.2).

In the remainder of this subsection we address the next best thing we can do in case a matrix does not have an \(LU\) decomposition.

Example 3.6.9

Let us return to Example 3.6.6 where the matrix \(A\) cannot be written as \(LU\). We copy from there

\[\begin{split} A \,=\, \begin{bmatrix} 1 & 2 & 1 \\ 4 & 8 & 6 \\ 2 & 5 & 7 \end{bmatrix} \begin{array}{l} [R_1] \\ {[R_2-4R_1]} \\ {[R_3-2R_1]} \end{array} \quad \sim \quad \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 2 \\ 0 & 1 & 5 \end{bmatrix}. \end{split}\]

We need a row swap to bring the last matrix to echelon form. The key idea is to perform all the row exchanges first and then add multiples of rows (top-down) to other rows to obtain an echelon form. Here the one row exchange is captured by the matrix

\[\begin{split} P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}. \end{split}\]

We get

\[\begin{split} PA \,=\, \begin{bmatrix} 1 & 2 & 1 \\ 2 & 5 & 7 \\ 4 & 8 & 6 \end{bmatrix} \,\, = \,\, \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 0 & 1 \end{bmatrix}\, \begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 5 \\ 0 & 0 & 2 \end{bmatrix}. \end{split}\]

This is what we will call a PLU decomposition.

Note that first subtracting row 1 four times from row 2 and two times from row 3, followed by exchanging row 2 and row 3 leads to the same echelon matrix as first swapping row 2 and 3 and then subtracting row 1 two times from row 2 and four times from row 3.

Definition 3.6.2

A permutation matrix is an \(n \times n\) matrix \(P\) with only entries \(0\) and \(1\) in such a way that each row and each column contain exactly one \(1\).

Example 3.6.10

Two \(4\times 4\) permutation matrices are

(3.6.4)\[\begin{split} P_1 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \quad \text{and} \quad P_2 = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}\end{split}\]

Note that for an arbitrary \(4 \times 4\) matrix \(A\) we have

\[\begin{split} P_1 A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \class{blue}{0} & \class{blue}{0} & \class{blue}{0} & \class{blue}{1} \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ \class{blue}{a_{41}} & \class{blue}{a_{42}} & \class{blue}{a_{43}} & \class{blue}{a_{44}} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ \class{blue}{a_{41}} & \class{blue}{a_{42}} & \class{blue}{a_{43}} & \class{blue}{a_{44}} \\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} \end{split}\]

and

\[\begin{split} P_2 A = \begin{bmatrix} \class{blue}{0} & \class{blue}{1} & \class{blue}{0} & \class{blue}{0} \\ \class{red}{0} & \class{red}{0} & \class{red}{1} & \class{red}{0} \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ \class{blue}{a_{21}} & \class{blue}{a_{22}} & \class{blue}{a_{23}} & \class{blue}{a_{24}} \\ \class{red}{a_{31}} & \class{red}{a_{32}} & \class{red}{a_{33}} & \class{red}{a_{34}} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{bmatrix} = \begin{bmatrix} \class{blue}{a_{21}} & \class{blue}{a_{22}} & \class{blue}{a_{23}} & \class{blue}{a_{24}} \\ \class{red}{a_{31}} & \class{red}{a_{32}} & \class{red}{a_{33}} & \class{red}{a_{34}} \\ a_{41} & a_{42} & a_{43} & a_{44} \\a_{11} & a_{12} & a_{13} & a_{14} \end{bmatrix} \end{split}\]

In general (pre-)multiplication of a matrix \(A\) with any permutation matrix reorders the rows of \(A\).

The following properties of permutation matrices come in handy.

Proposition 3.6.5

1. The product of two \(n\times n\) permutation matrices is again a permutation matrix.

2. The inverse of a permutation matrix is its transpose. Thus, \(P^{-1} = P^T\).

The following example provides some illustrations. And the interested reader may open the proof below it.

Example 3.6.11

For the matrices \(P_1\) and \(P_2\) from (3.6.4) we have

\[\begin{split} P_1P_2 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{split}\]

and

\[\begin{split} P_2^TP_2 = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}. \end{split}\]

Note that from the second identity it follows that \(P_2^{-1} = P_2^T\).

Proof of Proposition 3.6.5

1. The product of two \(n\times n\) permutation matrices is again a permutation matrix.

   Suppose \(P_1\) and \(P_2\) are permutation matrices. With the product \(P_1P_2\) the rows of \(P_2\) are reordered, and that leaves the properties a \(1\) in each row, a \(1\) in each column, all other entries equal to \(0\), intact.

2. The inverse of a permutation matrix is its transpose. Thus, \(P^{-1} = P^T\).

   In a product \(A^TA\), the entry on position \((i,j)\) is the inner product of the \(i\)th column of \(A\) with the \(j\)th column of \(A\). (Cf., Exercise 3.2.4.) Since the \(n\) columns of \(A\) are the \(n\) columns \(\vect{e}_j\) of the identity matrix (in some order), and

   \[\begin{split} \vect{e}_i\ip\vect{e}_j = \left\{\begin{array}{l} 1, \,\,\text{if}\,\, i = j\\ 0, \,\,\text{if}\,\, i \neq j, \end{array} \right. \end{split}\]

   the result immediately follows.

Theorem 3.6.1 (Existence of a \(PLU\) Decomposition)

Suppose that \(A\) is an \(m\times n\) matrix with real coefficients, and let \(m \leq n\). Then there exist a permutation matrix \(P\), an upper triangular matrix \(L\) and an echelon matrix \(U\) such that

\[ PA = LU. \]

Remark 3.6.1

As was mentioned before, the key idea is to perform the row exchanges first. These can be put together in the permutation matrix \(P\). The algorithm to actually find the \(LU\) decomposition of \(PA\) without doing the whole row reduction process for \(PA\) all over again is rather intricate, and in our view belongs to a course of numerical linear algebra. There it will be explained that it may also be preferable to work towards a \(PLU\) decomposition instead of an \(LU\) decomposition in cases where theoretically it is not absolutely necessary. For numerical reasons, having to do with finite accuracy when representing real numbers in computers, it may be better to choose the pivots in another order than just top-down.

In the following example the matrix does have a proper \(LU\) decomposition, but we will row reduce it in another order than top-down to echelon form. It is a tiny example to illustrate that it is possible to deduce a \(PLU\) decomposition from it when we keep record of both the multipliers and the positions of the pivots.

Example 3.6.12

We will row reduce the matrix \( A= \begin{bmatrix}2&4&3 \\ 1&2&3\\1&3&2 \end{bmatrix}\) in an alternative order than top-down and extricate a \(PLU\) decomposition from it.

\[\begin{split} \left[\begin{array}{rrr}2&4&3 \\ 1&2&3\\ \fbox{1}&3&2 \end{array} \right] \begin{array}{l} [R_1-\class{blue}{2}R_3] \\ {[R_2-\class{blue}{1}R_3]} \\ {[R_3]} \\ \end{array} \sim \left[\begin{array}{rrr}0&\fbox{$-2$}&-1 \\ 0 & -1 &1 \\ 1&3&2\end{array} \right] \begin{array}{l} [R_1] \\ {[R_2-\class{red}{\frac12}R_1]} \\ {[R_3]} \\ \end{array} \sim \left[\begin{array}{rrr}0&-2&-1 \\ 0 & 0 &\frac32 \\ 1&3&2\end{array} \right]. \end{split}\]

If we put together the matrices that describe the row operations we get

(3.6.5)\[\begin{split} A = \begin{bmatrix}2&\fbox{4}&3 \\ 1&2&\fbox{3}\\ \fbox{1}&3&2\end{bmatrix} = \begin{bmatrix} 1 & 0 & \class{blue}{2} \\ \class{red}{\frac12} &1 & \class{blue}{1} \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 0 & -2 & -1 \\ 0 & 0 &\frac32 \\1 & 3 & 2\end{bmatrix} = \tilde{L}\tilde{U}.\end{split}\]

If we would have started from

\[\begin{split} \begin{bmatrix} 1&3&2 \\2&4&3 \\ 1&2&3\end{bmatrix} = PA = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{bmatrix} \begin{bmatrix} 2&4&3 \\ 1&2&3\\1&3&2 \end{bmatrix} \end{split}\]

using the same pivots would have arrived at

\[\begin{split} \begin{bmatrix} 1&3&2 \\2&4&3 \\ 1&2&3\end{bmatrix} \sim \begin{bmatrix} 1&3&2 \\0&-2&-1 \\ 0&-1&1\end{bmatrix} \sim \begin{bmatrix} 1&3&2 \\0&-2&-1 \\ 0&0&\frac32\end{bmatrix}, \end{split}\]

so

\[\begin{split} PA = \begin{bmatrix} 1&3&2 \\2&4&3 \\ 1&2&3\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\\class{blue}{2} & 1 & 0 \\ \class{blue}{1} & \class{red}{\frac12} & 1\end{bmatrix} \begin{bmatrix} 1&3&2 \\0&-2&-1 \\ 0&0&\frac32\end{bmatrix} = LU. \end{split}\]

The matrix \(P\) is the inverse of (so also the transpose of) the matrix that describes the positions of the pivots as in Equation (3.6.5). It asks for some careful analysis how to reconstruct \(L\) from \(\tilde{L}\).

3.6.3. Efficiency Issues

To be filled in later.

3.6.4. Grasple Exercises

Grasple Exercise 3.6.3

To identify triangular matrices.

Show/Hide Content

Grasple Exercise 3.6.4

To compute the \(LU\)-decomposition of a 2x2 matrix \(A\).

Show/Hide Content

Grasple Exercise 3.6.5

To compute the \(LU\)-decomposition of a 3x3 matrix \(A\).

Show/Hide Content

Grasple Exercise 3.6.6

To compute the \(LU\)-decomposition of a 3x3 matrix \(A\) and use it to solve \(A\vect{x} = \vect{b}\).

Show/Hide Content

Grasple Exercise 3.6.7

To compute the \(LU\)-decomposition of a 3x3 matrix \(A\) and use it to solve \(A\vect{x} = \vect{b}\).

Show/Hide Content

Grasple Exercise 3.6.8

To decide solving \(A\vect{x} = \vect{b}\) via (given) \(A=LU\) or (given) \(A^{-1}\).

Show/Hide Content

Grasple Exercise 3.6.9

To compute \(A^{-1}\) using \(A = LU\).

Show/Hide Content

Grasple Exercise 3.6.10

Explorative exercise about the \(LDU\)-decomposition

Show/Hide Content

Grasple Exercise 3.6.11

To compute the \(LU\)-decomposition of 3x4 matrix \(A\) and use it to solve \(A\vect{x} = \vect{b}\).

Show/Hide Content

Grasple Exercise 3.6.12

To compute a \(PLU\)-decomposition of a 3x3 matrix.

Show/Hide Content

Grasple Exercise 3.6.13

To solve a system \(A\vect{x} = \vect{b}\) using \( PA = LU\).

Show/Hide Content