Page 155 - Matrices theory and applications

8. Matrix Factorizations
138
given, with nonzero leading principal minors. We look for L and U in the
blockwise form

L

0

L =
T
1
u
X
with L ,U ∈ M n−1 (k), etc. We likewise obtain the description

, U = U 0 Y ,
M R
M = T .
S m
Multiplying blockwise, we obtain the equations
T
T

L U = M , L Y = R, (U ) X = S, u = m − X Y.

By assumption, the leading principal minors of M are nonzero. The induc-

tion hypothesis guarantees the existence of the factorization M = L U .

Then Y and X are the unique solutions of (triangular) Cramer systems.
Finally, u is explicitly given.
Let us now compute the number of operations needed in the computation
of L and U. We pass from a factorization in GL n−1 (k) to a factorization in
GL n (k) by means of the computations of X ((n − 1)(n − 2) operations), Y
2
((n−1) operations) and u (2(n−1) operations), for a total of (n−1)(2n−1)
operations. Finally, the computation ex nihilo of an LU factorization costs
P(n)operations, where P is a polynomial of degree three, with P(X)=
3
2X /3+ ··· .
3
2
Proposition 8.1.1 The LU factorization is computable in 2 n + O(n )
3
operations.
3
2
One says that the complexity of the LU factorization is n .
3
Remark: When all leading principal minors but the last (det M)are
nonzero, the proof above furnishes a factorization M = LU,in which U is
not invertible; that is, u nn =0.
8.1.1 Block Factorization
One can likewise perform a blockwise LU factorization. If n = p 1 + ··· + p r
with p j ≥ 1, the matrices L and U will be block-triangular. The diagonal
blocks are square, of respective sizes p 1 ,... ,p r .Those of L are of the form
, while those of U are invertible. A necessary and sufficient condition
I p j
for such a factorization to exist is that the leading principal minors of M,
of orders p 1 + ··· + p j (j ≤ r), be nonzero. As above, it is not necessary
that the last minor det M be nonzero. Such a factorization is useful for the
resolution of the linear system MX = b if the diagonal blocks of U are
√
easily inverted, for instance if their sizes are small enough (say p j ≈ n).
An interesting application of block factorization is the computation of
the determinant by the Schur complement formula: