8Numerical linear algebra
IB Numerical Analysis
8.3 A = LU for special A
There is one thing we haven’t figured out yet. Can we just look at the matrix
A
,
and then determine whether it has an LU factorization (that does not involve
permutations)? To answer this, we start with some definitions.
Definition
(Leading principal submatrix)
.
The leading principal submatrices
A
k
∈ R
k×k
for k = 1, ··· , n of A ∈ R
n×n
are
(A
k
)
ij
= A
ij
, i, j = 1, ··· , k.
In other words, we take the first k rows and columns of A.
Theorem.
A sufficient condition for the existence for both the existence and
uniqueness of A = LU is that det(A
k
) 6= 0 for k = 1, ··· , n − 1.
Note that we don’t need
A
to be non-singular. This is equivalent to the
restriction
A
(k−1)
kk
6
= 0 for
k
= 1
, ··· , n −
1. Also, this is a sufficient condition,
not a necessary one.
Proof. Straightforward induction.
We extend this result a bit:
Theorem.
If
det
(
A
k
)
6
= 0 for all
k
= 1
, ··· , n
, then
A ∈ R
n×n
has a unique
factorization of the form
A = LD
ˆ
U,
where
D
is non-singular diagonal matrix, and both
L
and
ˆ
U
are unit triangular.
Proof.
From the previous theorem,
A
=
LU
exists. Since
A
is non-singular,
U
is non-singular. So we can write this as
U = D
ˆ
U,
where D consists of the diagonals of U and
ˆ
U = D
−1
U is unit.
This is not hard, but is rather convenient. In particular, it allows us to
factorize symmetric matrices in a nice way.
Theorem.
Let
A ∈ R
n×n
be non-singular and
det
(
A
k
)
6
= 0 for all
k
= 1
, ··· , n
.
Then there is a unique “symmetric” factorization
A = LDL
T
,
with L unit lower triangular and D diagonal and non-singular.
Proof. From the previous theorem, we can factorize A uniquely as
A = LD
ˆ
U.
We take the transpose to obtain
A = A
T
=
ˆ
U
T
DL
T
.
This is a factorization of the form “unit lower”-“diagonal”-“unit upper”. By
uniqueness, we must have
ˆ
U = L
T
. So done.
We just looked at a special type of matrices, the symmetric matrices. We
look at another type of matrices:
Definition
(Positive definite matrix)
.
A matrix
A ∈ R
n×n
is positive-definite if
x
T
Ax > 0
for x 6= 0 ∈ R
n
.
Theorem.
Let
A ∈ R
n×n
be a positive-definite matrix. Then
det
(
A
k
)
6
= 0 for
all k = 1, ··· , n.
Proof.
First consider
k
=
n
. To show
A
is non-singular, it suffices to show that
Ax
=
0
implies
x
=
0
. But we can multiply the equation by
x
T
to obtain
x
T
Ax = 0. By positive-definiteness, we must have x = 0. So done.
Now suppose
A
k
y
=
0
for
k < n
and
y
=
R
k
. Then
y
T
A
k
y
= 0. We
invent a new
x ∈ R
n
by taking
y
and pad it with zeros. Then
x
T
Ax
= 0. By
positive-definiteness, we know x = 0. Then in particular y = 0.
We are going to use this to prove the most important result in this section.
We are going to consider matrices that are symmetric and positive-definite.
Theorem.
A symmetric matrix
A ∈ R
n×n
is positive-definite iff we can factor
it as
A = LDL
T
,
where L is unit lower triangular, D is diagonal and D
kk
> 0.
Proof. First suppose such a factorization exists, then
x
T
Ax = x
T
LDL
T
x = (L
T
x)
T
D(L
T
x).
We let
y
=
L
T
x
. Note that
y
=
0
if and only if
x
=
0
, since
L
is invertible. So
x
T
Ax = y
T
Dy =
n
X
k=1
y
2
k
D
kk
> 0
if y 6= 0.
Now if
A
is positive definite, it has an LU factorization, and since
A
is
symmetric, we can write it as
A = LDL
T
,
where
L
is unit lower triangular and
D
is diagonal. Now we have to show
D
kk
>
0. We define
y
k
such that
L
T
y
k
=
e
k
, which exist, since
L
is invertible.
Then clearly y
k
6= 0. Then we have
D
kk
= e
T
k
De
k
= y
T
k
LDL
T
y
k
= y
T
k
Ay
k
> 0.
So done.
This is a practical check for symmetric
A
being positive definite. We can
perform this LU factorization, and then check whether the diagonal has positive
entries.
Definition
(Cholesky factorization)
.
The Cholesky factorization of a symmetric
positive-definite matrix A is a factorization of the form
A = LDL
T
,
with L unit lower triangular and D a positive-definite diagonal matrix.
There is another way of doing this. We let
D
1/2
be the “square root” of
D
,
by taking the positive square root of the diagonal entries of D. Then we have
A = LDL
T
= LD
1/2
D
1/2
L
T
= (LD
1/2
)(LD
1/2
)
T
= GG
T
,
where
G
is lower triangular with
G
kk
>
0. This is another way of presenting this
result.
Finally, we look at the LU factorization of band matrices.
Definition
(Band matrix)
.
A band matrix of band width
r
is a matrix
A
such
that A
ij
6= 0 implies |i −j| ≤ r.
For example, a band matrix of band width 0 is a diagonal matrix; a band
matrix of band width 1 is a tridiagonal matrix.
The result is
Proposition.
If a band matrix
A
has band width
r
and an LU factorization
A = LU, then L and U are both band matrices of width r.
Proof. Straightforward verification.