Page 164 - Matrices theory and applications

problem My = 0. From the analysis done in the previous section, ker M is
nothing but the range of I m −M M. Therefore, we may state the following
proposition:
†
Proposition 8.4.2 The system (8.2) is solvable if and only if b = MM b.
†
When it is solvable, its general solution is x = M b+(I m −M M)z,where
m
†
z ranges over CC . Finally, the special solution x 0 := M b is the one of
least Hermitian norm. † † 8.5. Exercises 147
There remains to prove that x 0 has the smallest norm among the solu-
tions. That comes from the Pythagorean theorem and from the fact that
R(M )= R(M M)= (ker M) .
†
⊥
†
8.5 Exercises
1. Assume that there exists an algorithm for multiplying two N × N
matrices with entries in a noncommutative ring by means of K
multiplications and L additions. Show that the complexity of the
α
multiplication in M n (k)is O(n ), with α =log K/ log N.
2. What is the complexity of Choleski factorization?
3. Let M ∈ SPD n be also tridiagonal. What is the structure of L in
the Choleski factorization? More generally, what is the structure of
L when m ij =0 for |i − j| >r?
4. (continuation of exercise 3)
For i ≤ n,denoteby φ(i) the smallest index j such that m ij =0.
In Choleski factorization, show that l ij =0 for every pair (i, j)such
that j< φ(i).

5. In the QR factorization, show that the map M → (Q, R) is continuous
on GL n (CC).

6. Let H be an n × n Hermitian matrix, that blockwise reads

A B ∗
H = .
B C
Assume that A ∈ HPD n−k (1 ≤ k ≤ n − 1).
Find a matrix T of the form

0
I n−k
T =
· I k
such that THT is block-diagonal. Deduce that if W ∈ H k ,then
∗

0 0
H −
0 W