8Numerical linear algebra
IB Numerical Analysis
8.1 Triangular matrices
While matrices in general and big and scary, triangular matrices tend to be much
nicer.
Definition
(Triangular matrix)
.
A matrix
A
is upper triangular if
A
ij
= 0
whenever
i > j
. It is lower triangular if
A
ij
= 0 whenever
i < j
. We usually
denote upper triangular matrices as U and lower triangular matrices as L.
We can visualize these matrices as follows:
L U
Why are triangular matrices nice? First of all, it is easy to find the determinants
of triangular matrices. We have
det(L) =
n
Y
i=1
L
ii
, det(U) =
n
Y
i=1
U
11
.
In particular, a triangular matrix is non-singular if and only if it has no zero
entries in its diagonal.
How do we solve equations involving triangular matrices? Suppose we have
a lower triangular matrix equation
L
11
0 ··· 0
L
12
L
22
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
L
1n
L
2n
··· L
nn
x
1
x
2
.
.
.
x
n
=
b
1
b
2
.
.
.
b
n
,
or, more visually, we have
=
There is nothing to solve in the first line. We can immediately write down the
value of
x
1
. Substituting this into the second line, we can then solve for
x
2
. In
general, we have
x
i
=
1
L
ii
b
i
−
i−1
X
j=1
L
ij
x
j
.
This is known as forward substitution.
For upper triangular matrices, we can do a similar thing, but we have to
solve from the bottom instead. We have
x
i
=
1
U
ii
b
i
−
n
X
j=1+i
U
ij
x
j
.
This is known as backwards substitution.
This can be used to find the inverse of matrices as well. The solution to
Lx
j
=
e
j
is the
j
th column of
L
−1
. It is then easy to see from this that the
inverse of a lower triangular matrix is also lower triangular.
Similarly, the columns of
U
−1
are given by solving
Ux
j
=
e
i
, and we see that
U
−1
is also upper triangular.
It is helpful to analyse how many operations it takes to compute this. If we
look carefully, solving Lx = b or Ux = b this way requires O(n
2
) operations.