Linear Algebra: VI Triangular Matrices and LU Decomposition

Triangular Matrices and LU Decomposition


A square matrix $A$ is called upper triangular if:


$$ a_{ij} = 0 \quad \text{for all } i > j $$

A square matrix $A$ is called lower triangular if:


$$ a_{ij} = 0 \quad \text{for all } i < j $$

Upper and lower triangular $n \times n$ square matrices both contain at least


$$ \frac{n(n-1)}{2} $$

Zeros and


$$ \frac{n(n+1)}{2} $$

Other entries.


The identity matrix $I$ is both upper triangular and lower triangular. Scaling elementary matrices and their products are also both upper and lower triangular. Shearing elementary matrices are either upper triangular or lower triangular but never both. Swapping elementary matrices are neither upper nor lower triangular.


If $A$ and $B$ are upper triangular $n \times n$ square matrices, then $AB$ is also upper triangular.


Indeed, for $i > j$:


$$ (ab)_{ij} = \sum_{k=1}^n a_{ik} b_{kj} $$

If $i > k$, then $a_{ik} = 0$. If $k \ge i$, then $k > j$, so $b_{kj} = 0$. Hence every term in the sum is zero, and therefore:


$$ (ab)_{ij} = 0 \quad \text{for all } i > j $$

Thus, $AB$ is upper triangular.


Similarly, if $A$ and $B$ are lower triangular, then $AB$ is also lower triangular.


The sum of upper triangular matrices is upper triangular, and the sum of lower triangular matrices is lower triangular. The scalar multiple of an upper triangular matrix is upper triangular, and the scalar multiple of an lower triangular matrix is lower triangular.


If $A$ is upper triangular, then $A^\top$ is lower triangular since:


$$ a_{ij} = 0 \text{ for } i > j \quad \Rightarrow \quad a_{ji} = 0 \text{ for } j > i $$

Similarly, if $A$ is lower triangular, then $A^\top$ is upper triangular.


Recall that if $A$ is invertible, then $PA$ where $P$ is a permutation matrix can be efficiently written as the product of $n^2$ elementary matrices using Gauss--Jordan elimination.

Then $\frac{n(n-1)}{2}$ of these matrices are lower triangular shearing elementary matrices or identity matrices so that $L = E_1 \cdots E_{\frac{n(n-1)}{2}}$ is lower triangular with diagonal entries that are all $1$:

$$l_{ii} = 1$$
Also $\frac{n(n+1)}{2}$ of these matrices are upper triangular shearing elementary matrices, scaling elementary matrices, or identity matrices so that $U = E^*_1 \cdots E^*_{\frac{n(n+1)}{2}}$ is upper triangular.

Therefore, if $A$ is invertible, then $PA$ can be decomposed into a product of a lower triangular matrix and an upper triangular matrix:

$$ PA = E_1 \cdots E_{n^2} $$
$$ = E_1 \cdots E_{\frac{n(n-1)}{2}} \cdot E^*_1 \cdots E^*_{\frac{n(n+1)}{2}} $$
$$ = LU $$
If $n$ by $n$ square matrix $U$ is invertible and upper triangular, then $U^{-1}$ is upper triangular.

In general, we write $U = E_1 \cdots E_{\frac{n(n+1)}{2}}$. It follows that

$$ U^{-1} = (E_{\frac{n(n+1)}{2}})^{-1} \cdots (E_1)^{-1} $$
Where each inverse elementary matrix $(E_i)^{-1}$ is upper triangular. So $U^{-1}$ is upper triangular.

If $n$ by $n$ square matrix $L$ is invertible and lower triangular, then $L^{-1}$ is lower triangular.

In general, we write $L = E_1 \cdots E_{\frac{n(n+1)}{2}}$. It follows that

$$ L^{-1} = (E_{\frac{n(n+1)}{2}})^{-1} \cdots (E_1)^{-1} $$
Where each inverse elementary matrix $(E_i)^{-1}$ is lower triangular. So $L^{-1}$ is lower triangular.

In general, the determinant of an $n$ by $n$ square upper triangular matrix is the product of its diagonal entries.

We write $U = E_1 \cdots E_{\frac{n(n+1)}{2}}$. Each elementary matrix is either $\frac{n(n-1)}{2}$ upper triangular shearing elementary matrices where $\det(E) = 1$ or $n$ scaling elementary matrices where $\det(E) = u_{ii}$ for $i \in \{1,\ldots,n\}$. Therefore,

$$ \det(U) = u_{11} \cdots u_{nn} $$

In general, the determinant of a $n$ by $n$ square lower triangular matrix is the product of its diagonal entries.

We write $L = E_1 \cdots E_{\frac{n(n+1)}{2}}$. Each elementary matrix is either $\frac{n(n-1)}{2}$ lower triangular shearing elementary matrices where $\det(E) = 1$ or $n$ scaling elementary matrices where $\det(E) = l_{ii}$ for $i \in \{1,\ldots,n\}$. Therefore,

$$ \det(L) = l_{11} \cdots l_{nn} $$
In $LU$ decomposition, $l_{ii} = 1$. Therefore, $\det(L)=1$. Thus,

$$\det(A) = \det(L) \det(U) = 1 \cdot \det(U) = \det(U)$$
Which means that the determinant of $A$ is the product of the diagonal entries of $U$ / the pivots of $A$.

Consider the equation $A \vec{x} = \vec{b}$. If $A = LU$ with lower triangular matrix $L$ and upper triangular matrix $U$, then

$$ LU \vec{x} = \vec{b} $$
Let $\vec{y} = U \vec{x}$. Then
$$ L \vec{y} = \vec{b} $$
Which can be solved for $\vec{y}$ using forward substitution since $L$ is lower triangular. This means that the first row equation can be solved for $y_1$, then the second row equation can be solved for $y_2$, continuing until the last row equation can be solved for $y_n$.

The other equation
$$ U \vec{x} = \vec{y} $$
Can be solved for $\vec{x}$ using backward substitution since $U$ is upper triangular. This means that the last row can be solved for $x_n$, then the preceding row can be solved for $x_{n-1}$, continuing until the first row can be solved for $x_1$.

Comments

Post a Comment

Popular posts from this blog

Linear Algebra: III Square and Inverse Matrices

Square and Inverse Matrices An $n$ by $n$ square matrix has the same number of rows and columns: $$ A = \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{bmatrix} $$ If $A$ is an $n$ by $n$ square matrix and $\vec{x} \in \mathbb{R}^n$, then the product $A\vec{x}$ is also a vector in $\mathbb{R}^n$, defining a linear transformation $T: \mathbb{R}^n \to \mathbb{R}^n$. The identity matrix $I$ is an $n$ by $n$ square matrix with 1s on the main diagonal and 0s elsewhere: $$ I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} $$ It satisfies: $$ AI = IA = A $$ The inverse of a square matrix $A$, denoted $A^{-1}$, is a matrix such that: $$ A A^{-1} = A^{-1} A = I $$ Which may not exist. If $A^{-1}$ exists, then $A$ is called invertible . If $A$ and $B$ are inve...
Read more

Linear Algebra: VII Orthonormal Matrices

Orthonormal Matrices A square $n$ by $n$ matrix $Q$ is called orthonormal if: $$ QQ^\top = Q^\top Q = I $$ $$ Q^{-1} = Q^\top $$ The columns $\vec{q}_1, \ldots, \vec{q}_n$ of $Q$ (and the rows) form an orthonormal basis of $\mathbb{R}^n$: $$ \vec{q}_i^\top \vec{q}_j = 0 \text{ if } i \neq j, \quad \|\vec{q}_i\| = 1 $$ An orthonormal matrix preserves inner products / dot products: $$ (Q\vec{x})^\top(Q\vec{y}) = \vec{x}^\top Q^\top Q \vec{y} = \vec{x}^\top I \vec{y} = \vec{x}^\top \vec{y} $$ An orthonormal matrix also preserves magnitude: $$ \|Q\vec{x}\|^2 = (Q\vec{x})^\top Q\vec{x} = \vec{x}^\top Q^\top Q \vec{x} = \vec{x}^\top I \vec{x} = \vec{x}^\top \vec{x} = \|\vec{x}\|^2 $$ So an orthonormal matrix preserves angles between vectors: $$ \cos{\theta} = \frac{(Q\vec{x})^\top(Q\vec{y})}{\|Q\vec{x}\|\|Q\vec{y}\|} = \frac{\vec{x}^\top \vec{y}}{\|\vec{x}\|\|\vec{y}\|} $$ There are two special types of orthogonal matrices. First, a...
Read more