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.