Definiteness, Cholesky and generating correlated normals

Positive semi-definiteness is the condition that makes a matrix a legitimate covariance matrix, and the Cholesky factorisation is the practical consequence: it is how you turn independent random numbers into correlated ones, and how you solve a linear system in half the time.

Test	Statement	Cost
Quadratic form	$x^\top A x \ge 0$ for all $x$	A definition, not a procedure
Eigenvalues	All $\lambda_i \ge 0$	$O(n^3)$ , and gives the most information
Cholesky	A factorisation $A = LL^\top$ exists	$O(n^3/3)$ , the fastest test in practice

Table 5.1 · Three equivalent tests. Attempting a Cholesky is the standard check: if the factorisation fails partway through, the matrix is not positive definite, and you learn it quickly.

Equation 5.2

The Cholesky factorisation

A "square root" of a symmetric positive-definite matrix. Unique, cheap, and the workhorse of simulation and of solving normal equations.

\Sigma = LL^\top, \qquad L \text{ lower triangular with positive diagonal}

$L$: Lower triangular, so systems involving it solve by substitution in $O(n^2)$ .
$\mathrm{Cov}(Lz)$: Equals $LL^\top = \Sigma$ when $z$ has identity covariance.

Derivation 5.3

Generating correlated normals

The one-line application, and it is asked constantly.

$z \sim N(0, I_n)$
Draw independent standard normals.
$x = \mu + Lz$
Apply the Cholesky factor.
$\mathrm{Cov}(x) = L\,\mathrm{Cov}(z)\,L^\top = LL^\top = \Sigma$

x \sim N(\mu, \Sigma)

Figure 5.4 · What Cholesky actually gives you. For a correlation of

0.6

, the second variable is

0.6 z_1 + 0.8 z_2

. The weights are a right angle —

0.6^2 + 0.8^2 = 1

— which is what keeps the variance at one while the correlation comes out exactly as asked.

Example 5.5

Give the Cholesky factor of the $2\times 2$ correlation matrix with $\rho = 0.6$ , and the recipe for two correlated standard normals.

Show the worked solutionHide the worked solution

Worked solution

Formula $L = \begin{pmatrix}1 & 0 \\ \rho & \sqrt{1-\rho^2}\end{pmatrix}$
Substitute $\rho = 0.6 \Rightarrow \sqrt{1 - 0.36} = 0.8$
Solve $x_1 = z_1$
$x_2 = 0.6z_1 + 0.8z_2$
Answer $x_2 = \rho z_1 + \sqrt{1-\rho^2}\,z_2$

Sanity check. Check the variance: $0.6^2 + 0.8^2 = 1$ , so $x_2$ is standard. And $\mathrm{Cov}(x_1,x_2) = 0.6$ as required. The two-variable case is worth memorising because it comes up constantly and needs no matrix algebra.

Definiteness, Cholesky and generating correlated normals

After this lesson you should be able to

The Cholesky factorisation

Generating correlated normals

The rest of this lesson is in Premium