If we think of matrices as multi-dimensional generalizations of numbers, we may draw useful analogies between numbers and matrices. Not least of these is an analogy between positive numbers and positive definite matrices. Just as we can take square roots of positive numbers, so can we take “square roots” of positive definite matrices. Positive Definite
Matrices
These definitions may seem abstruse, but they lead to an intuitively appealing result. A symmetric matrix x is:
It is useful to think of positive definite matrices as analogous to positive numbers and positive semidefinite matrices as analogous to nonnegative numbers. The essential difference between semidefinite matrices and their definite analogues is that the former can be singular whereas the latter cannot. This follows because a matrix is singular if and only if it has a 0 eigenvalue. Matrix “Square Roots”
Cholesky Factorization
A Cholesky factorization takes the form
By inspection,
Our Cholesky matrix is
The above example illustrates a Cholesky algorithm, which generalizes for higher dimensional matrices. Our algorithm entails two types of calculations: 1. Calculating diagonal elements
2. Calculating off-diagonal elements
For a positive definite matrix h, all
diagonal elements
The same algorithm applies for singular positive
semidefinite matrices h, but the result is not generally
called a Cholesky matrix. This is just an issue of terminology. When the
algorithm is applied to the singular h, at least one
diagonal elements
Consider the matrix
Performing the first four steps of our algorithm above, we obtain
In the fifth step, we multiply the second row of g by the third column of g' to obtain
We already know
which provides us with no means of determining
For the element
We can leave g in this form, or we can
delete the second column, which contains only 0’s. The resulting 3
If a matrix h is not positive semidefinite, our Cholesky algorithm will, at some point, attempt to take a square root of a negative number and fail. Accordingly, the Cholesky algorithm is a means of testing if a matrix is positive semidefinite. Computational Issues
Things are more complicated if arithmetic is performed with rounding, as is done on a computer. Off-diagonal elements are obtained by dividing by diagonal elements. If a diagonal element is close to 0, any roundoff error may be magnified in such a division. For example, if a diagonal element should be .00000001, but roundoff error causes it to be calculated as .00000002, division by this number will yield an off-diagonal element that is half of what it should be. An algorithm is said to be unstable if roundoff error can be magnified in this way or if it can cause the algorithm to fail. The Cholesky algorithm is unstable for singular positive semidefinite matrices h. It is also unstable for positive definite matrices h that have one or more eigenvalues close to 0.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
> 0 for all row vectors b
0; 
0 for all row vectors b; 
0 for all row vectors b; 
for some real square matrix k, which we may think of as a
matrix square root of h. The matrix k is not
unique, so multiple factorizations of a given matrix h are
possible. This is analogous to the fact that square roots of positive
numbers are not unique either. If h is nonsingular (positive
definite), k will be nonsingular. If h is
singular, k will be singular. 
where g is a lower triangular matrix. Solving for g
is straightforward. Suppose we wish to factor the positive definite matrix
Also by inspection,
Since we already have
,
we conclude
.
Proceeding in this manner, we obtain a matrix g in 6 steps:
(steps 1, 4, and 6) entails taking a square root. 
,
i > j, (steps 2, 3, and 5) entails dividing some number by
the last-calculated diagonal element. 
equals 0, we can obtain g as we did in our example. If some
other diagonal element
will be indeterminate. We can set such indeterminate values equal to any
value within an interval [–a, a], for some a
,
so we have 
.
It is indeterminate, so we set it equal to a variable x and proceed
with the algorithm. We obtain 
to be real, we can set x equal to any value in the interval [–3,3].
The interval of acceptable values for indeterminate components will vary,
but it will always include 0. For this reason, it is standard practice to
set all indeterminate values equal to 0. With this selection, we obtain
2
matrix provides a valid factorization of h since 
Identify
all factorizations of the following matrices that are obtainable
with the Cholesky algorithm. Take
only positive square roots when selecting nonzero diagonal
elements
