\documentclass[11pt]{article}


\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in



\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\input epsf
\usepackage [usenames,dvipsnames]{color}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\pa}{\partial}
\renewcommand{\P}{\mathcal P}
\newcommand{\cL}{\mathcal L}
\renewcommand{\O}{\Omega}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}
\usepackage{graphicx}
\usepackage{tikz}
\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}


\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}



\title{Cholesky Factorization}
\pagestyle{myheadings}
%\author{October 21, 2013}
\date{}
\def\ds{\displaystyle}
\def\ul{\underline}

\begin{document}
\maketitle
%\markboth{334 midterm}{334 midterm}

An alternate to the $LU$ factorization is possible for positive
definite matrices $A$.  The text's discussion of this method is
skimpy.  This is a more complete discussion of the method. A matrix is
\textbf{symmetric positive definite} if for every $x\ne 0$
\[
x^TAx >0, \text{ and } A^T=A.
\]
It follows the $\det (A) >0$ and that all principal proper sub
matrices have positive determinant.  What follows is a description of
Cholesky's method.  We want to come up with a factorization of the
form
\[
A=LL^T,
\]
Where $L$ is lower triangular.  We construct $L=[\ell_{ij}]$ inductively.

\begin{enumerate}
\item
\[
\ell_{11} =\sqrt{a_{11}},
\]
where we take the positive square root.  Since $A$ is positive
definite, $a_{11}>0$ and this gives a positive real number.
\item We want $\ell_{11}\ell_{21} = a_{21}$, so we take 
\[
\ell_{21} = \frac{a_{21}}{\ell_{11}}.
\]
\item We want $\ell_{21}^2 + \ell_{22}^2 = a_{22}^2$.  So we set
\[
\ell_{22} = \sqrt{a_{22}^2 - \ell_{21}^2}.
\]
So now we have a $2\times 2$ matrix 
\[
L_2= 
\begin{bmatrix}
\ell_{11} & 0\\ \ell_{21} & \ell_{22}
\end{bmatrix}
\]
that satisfies
\[
L_2L_2^T= 
\begin{bmatrix}
a_{11} & a_{12} \\ a_{21} & a_{22} 
\end{bmatrix}
=A_2.
\]
Now take determinants of both sides to get 
\[
l_{11}^2l_{22}^2 = \det A_2 >0.
\]
So the complex number $\ell_{22}$ has a \emph{positive} square and
must have been real, in other words 
\[
a_{22}^2-\ell_{21}^2 >0,
\]
and we can take the (real) square root to be positive.

\item Now consider an $n\times n$ symmetric positive definite matrix
  $A$.  Let's suppose we have already handled $(n-1)\times (n-1)$
  matrices.  We want to produce a partitioned matrix 
\[
L=
\begin{bmatrix}
L_1 & 0\\ b & \ell
\end{bmatrix}
\]
so that\[
\begin{bmatrix}
L_1 &0\\b & \ell
\end{bmatrix}
\begin{bmatrix}
L_1^T& b^T\\0 & \ell
\end{bmatrix}=
\begin{bmatrix}
A_1&c^T\\ c & a_{nn}
\end{bmatrix}.
\]
In this equation $b$ and $c$ are $n-1$ dimensional row vectors and
$A_1$ is the upper left $(n-1) \times (n-1)$ part of $A$. One equation
we can solve uniquely is 
\[
bL_1^T = c.
\]
Now that we know $b$ we have one more equation
\[
\norm{b}^2 + \ell^2 = a_{nn}^2.
\]
Hence we let 
\[
\ell = \sqrt{a_{nn}^2 -\norm{b}^2},
\]
which is possibly a complex number, but it does give us a solution to 
\[
LL^T =A.
\]
If we compute determinants we find 
\[
\det(L_1)^2\ell^2 =\det(A)>0.
\]
Hence $\ell^2>0$ and $\ell$ must have been real and we choose it to be
the positive square root.


\end{enumerate}

Cholesky was a French soldier who was also a mathematician and
geodesist.  He was killed near the end of WWI.  One of his
aquaintances wrote a paper with Cholesky's method and credited him
with it.  It was published in 1924, after Cholesky's death.
 

%\bibliographystyle{amsplain}
%\bibliography{header}

\end{document}
