Page 154 - Matrices theory and applications

Another example of easily invertible matrices is the orthogonal matrices:
T
If Q ∈ O n (or Q ∈ U n ), then Qx = y amounts to x = Q y (or x = Q y),
2
which is computed in O(n )operations.
The techniques described below are often called direct solving methods.
8.1 The LU Factorization 8.1. The LU Factorization ∗ 137
Definition 8.1.1 Let M ∈ GL n (k),where k is a field. We say that M
admits an LU factorization if there exist in GL n (k) two matrices L (lower
triangular with 1’s on the diagonal) and U (upper triangular) such that
M = LU.
Remarks:
• The diagonal entries of U are not equal to 1 in general. The LU
factorization is thus asymmetric with respect to L and U.

• The letters L and U recall the shape of the matrices: L for lower and
U for upper.

• If there exists an LU factorization (which is unique, as we shall see
below), then it can be computed by induction on the size of the
matrix. The algorithm is provided in the proof of the next theorem.
Indeed, if N (p) denotes the matrix extracted from N by keeping only
the first p rows and columns, we have easily
M (p) = L (p) U (p) ,

where the matrices L (p) and U (p) have the required properties.
Definition 8.1.2 The leading principal minors of M are the determinants
of the matrices M (p) ,for 1 ≤ p ≤ n.
Theorem 8.1.1 The matrix M ∈ GL n (k) admits an LU factorization if
and only if its leading principal minors are nonzero. When this condition
is fulfilled, the LU factorization is unique.
Proof
−1

Let us begin with uniqueness: If LU = L U ,then(L ) L = U U −1 ,
which reads L = U ,where L and U are triangular of opposite types,

the diagonal entries of L being 1’s. We deduce L = U = I n ;that is,

L = L, U = U.

We next assume that M admits an LU factorization. Then det M (p) =
det L (p) det U (p) = u jj , which is nonzero because U is invertible.
1≤j≤p
We prove the converse (the existence of an LU factorization) by induction
onthesizeofthe matrices. It is clear if n = 1. Otherwise, let us assume
that the statement is true up to the order n − 1and let M ∈ GL n (k)be