Cholesky for correlated shocks

hardMathsacceptance —~40 min

Implement cholesky(a) — the lower-triangular Cholesky factor L of a symmetric positive-definite matrix given as a list of rows, so that L·Lᵀ = a: L[i][i] = sqrt(a[i][i] - Σ_k<i L[i][k]²) and, for j < i, L[i][j] = (a[i][j] - Σ_k<j L[i][k]·L[j][k]) / L[j][j]. Entries above the diagonal are 0.

Multiply L by a vector of independent normals and you get correlated shocks — the way a multi-asset Monte Carlo, or a Heston simulation, breathes together. Return L with every entry rounded to 4 decimal places.

example 1

input

a=[[4.0, 2.0], [2.0, 3.0]]

output

[[2, 0], [1, 1.4142]]

example 2

input

a=[[4.0, 2.0, 0.6], [2.0, 2.0, 0.5], [0.6, 0.5, 1.0]]

output

[[2, 0, 0], [1, 1, 0], [0.3, 0.2, 0.9327]]

constraints

2 ≤ n ≤ 6
a is symmetric positive-definite

teacher · 2 hints · the first is free

↗ read the theory

the chapter this problem is cut from

▶ open in the workbench

run the same math on a real tape

●solution.py· utf-8 · spaces:4

from math import sqrt


def cholesky(a: list) -> list:
    """Lower-triangular L with L·Lᵀ = a, entries rounded to 4 dp."""
    n = len(a)
    L = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1):
            if i == j:
                s = sum(L[i][k] ** 2 for k in range(j))
                L[i][j] = sqrt(a[i][i] - s)
            else:
                # TODO: subtract sum(L[i][k] * L[j][k] for k < j) — needed from 3×3 up
                L[i][j] = a[i][j] / L[j][j]
    return [[round(v, 4) for v in row] for row in L]

ln 1, col 1tab indent · esc leave editor

python 3.13 · pyodide

+ 6 hidden on submit

input · keyword arguments to cholesky()

a=[[4.0, 2.0], [2.0, 3.0]]

expected

[[2, 0], [1, 1.4142]]

the judge calls cholesky() with exactly these inputs · outputs are compared to 6 decimal places

● standing bypython 3.13 in your browser · pyodide 0.28.3 · judged on the server to 6 dp⌘↵ run · ⌘⇧↵ submit

paper only · educational · not advice