Cholesky and positive-definite matrices

Square roots for matrices

A symmetric matrix $A$ is positive definite when $\mathbf{x}^{T}A\mathbf{x}>0$ for every $\mathbf{x}\neq\mathbf{0}$ ; equivalently, all its eigenvalues are positive. Covariance matrices are always positive semidefinite, because $\mathbf{w}^{T}\Sigma\mathbf{w}$ is the variance of a portfolio and variances cannot be negative. They are positive definite, with every portfolio having strictly positive variance, exactly when no asset is redundant.

A=LL^{T},\qquad L_{jj}=\sqrt{A_{jj}-\sum_{k<j}L_{jk}^{2}},\qquad L_{ij}=\frac{A_{ij}-\sum_{k<j}L_{ik}L_{jk}}{L_{jj}}\ (i>j)

(1)

Every positive definite matrix has a Cholesky factorisation $A=LL^{T}$ with $L$ lower triangular and a positive diagonal: the matrix analogue of a square root. It uses the symmetry, so it costs about $\tfrac13n^3$ , half of LU, and it needs no pivoting. If the algorithm meets a negative number under a square root, the matrix is not positive definite, which makes Cholesky a cheap test of that property.

A factor and a simulationFor

A=\begin{pmatrix}4&2\\2&5\end{pmatrix}

L_{11}=\sqrt4=2

L_{21}=2/2=1

L_{22}=\sqrt{5-1^2}=2

, so

L=\begin{pmatrix}2&0\\1&2\end{pmatrix}

and

LL^{T}=\begin{pmatrix}4&2\\2&5\end{pmatrix}

. To simulate two returns with correlation

0.6

and unit variances, factor

\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}

into

L=\begin{pmatrix}1&0\\0.6&0.8\end{pmatrix}

and set

\mathbf{x}=L\mathbf{z}

with

\mathbf{z}

independent standard normals: then

\operatorname{Cov}(\mathbf{x})=LL^{T}=\Sigma

Positive definite: $\mathbf{x}^{T}A\mathbf{x}>0$ for all $\mathbf{x}\neq\mathbf{0}$ ; all eigenvalues positive.
Cholesky: $A=LL^{T}$ , half the cost of LU, no pivoting, and a cheap positive-definiteness test.
Correlated draws: $\mathbf{x}=L\mathbf{z}$ turns independent normals $\mathbf{z}$ into returns with covariance $\Sigma$ .

A sample covariance can fail to factorIf you estimate a covariance matrix from fewer observations than assets, or two assets have identical returns, the sample matrix is only semidefinite and Cholesky stops on a zero or slightly negative pivot. Remedies are more data, dropping duplicates, shrinkage towards a well-behaved target, or adding a small multiple of the identity to the diagonal.

Lab · what's graded

Factor a matrix20 pts
Factor a correlation matrix20 pts
A correlated draw15 pts
Which matrix is positive definite15 pts
When Cholesky fails10 pts
Simulating correlated returns20 pts

Square roots for matrices

A=LL^{T},\qquad L_{jj}=\sqrt{A_{jj}-\sum_{k<j}L_{jk}^{2}},\qquad L_{ij}=\frac{A_{ij}-\sum_{k<j}L_{ik}L_{jk}}{L_{jj}}\ (i>j)

(1)

A factor and a simulationFor

A=\begin{pmatrix}4&2\\2&5\end{pmatrix}

L_{11}=\sqrt4=2

L_{21}=2/2=1

L_{22}=\sqrt{5-1^2}=2

, so

L=\begin{pmatrix}2&0\\1&2\end{pmatrix}

and

LL^{T}=\begin{pmatrix}4&2\\2&5\end{pmatrix}

. To simulate two returns with correlation

0.6

and unit variances, factor

\Sigma=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}

into

L=\begin{pmatrix}1&0\\0.6&0.8\end{pmatrix}

and set

\mathbf{x}=L\mathbf{z}

with

\mathbf{z}

independent standard normals: then

\operatorname{Cov}(\mathbf{x})=LL^{T}=\Sigma

Positive definite: $\mathbf{x}^{T}A\mathbf{x}>0$ for all $\mathbf{x}\neq\mathbf{0}$ ; all eigenvalues positive.
Cholesky: $A=LL^{T}$ , half the cost of LU, no pivoting, and a cheap positive-definiteness test.
Correlated draws: $\mathbf{x}=L\mathbf{z}$ turns independent normals $\mathbf{z}$ into returns with covariance $\Sigma$ .

Lab · what's graded

Factor a matrix20 pts
Factor a correlation matrix20 pts
A correlated draw15 pts
Which matrix is positive definite15 pts
When Cholesky fails10 pts
Simulating correlated returns20 pts

Cholesky and positive-definite matrices

Square roots for matrices

Lab · what's graded

Log in to run your code.

Cholesky and positive-definite matrices

Square roots for matrices

Lab · what's graded

Log in to run your code.