Page 159 - Matrices theory and applications

8. Matrix Factorizations
142
Proposition 8.1.4 The complexity of the multiplication of n× n matrices
α
is O(n ),with α =log 7/ log 2 = 2.807 ... More precisely,
147
log 7
n
.
P n ≤
log 2
2
The exponent α can be improved, at the cost of greater complication and a
larger constant c α . The best exponent known in 1997, due to Coppersmith
and Winograd [11], is α =2.376 ... A rather complete analysis can be
found in the bookbyP.B¨urgisser, M. Clausen, and M. A. Shokrollahi [7].
Here is Strassen’s formula [33]. Let M, N ∈ M 2 (A), with

a b x y
M = , N = .
c d z t
One first forms the expressions x 1 =(a + d)(x + t), x 2 =(c + d)x, x 3 =
a(y−t), x 4 = d(z−x), x 5 =(a+b)t, x 6 =(c−a)(x+y), x 7 =(b−d)(z+t).
Then one computes the product

x 1 + x 4 − x 5 + x 7 x 3 + x 5
MN = .
x 2 + x 4 x 1 − x 2 + x 3 + x 6
8.2 Choleski Factorization
In this section k = IR, and we consider symmetric positive definite matrices.
Theorem 8.2.1 Let M ∈ SPD n . Then there exists a unique lower trian-
gular matrix L ∈ M n (IR), with strictly positive diagonal entries, satisfying
T
M = LL .
Proof
Let us begin with uniqueness. If L 1 and L 2 have the properties stated
T
above, then I n = LL ,for L = L −1 L 1 , which still has the same form. In
2
other words, L = L −T , where both sides are triangular matrices, but of
opposite types (lower and upper). The equality shows that L is actually
2
diagonal, with L = I n . Since its diagonal is positive, we obtain L = I n ;
that is, L 2 = L 1.
We shall give two constructions of L.
First method. The matrix M (p) is positive definite (test the quadratic
p
form induced by M on the linear subspace IR ×{0}). The lead-
ing principal minors of M are thus nonzero and there exists an LU
factorization M = L 0U 0 .Let D be the diagonal of U 0 , which is in-
vertible. Then U 0 = DU 1 , where the diagonal entries of U 1 equal
T
T
1. By transposition, we have M = U D 0 L . From uniqueness of
1 0
T
the LU factorization, we deduce U 1 = L T and M = L 0DL .Then
√ 0 0
L = DL 0 satisfies the conditions of the theorem. Observe that
T
D> 0 because D = PMP ,with P = L −1 .
0