One Triangle, Used Twice

LU decomposition splits a matrix into two different triangles. Some matrices allow a neater split that uses one triangle twice:

Here $L$ is lower triangular (zeros above its diagonal) with positive numbers on its diagonal, and $L^{\mathsf T}$ is its transpose. This is the Cholesky decomposition. It stores one triangle instead of two and takes about half the work of LU, so libraries reach for it first whenever a matrix qualifies.

Finding $L$. Entry $(i, j)$ of $LL^{\mathsf T}$ is the dot product of row $i$ of $L$ with row $j$ of $L$. Matching those dot products to the entries of $A$, one column of $L$ at a time from left to right, gives

For example, $A = \begin{bmatrix} 9 & 6 \\ 6 & 5 \end{bmatrix}$ gives $L_{00} = \sqrt{9} = 3$, then $L_{10} = 6/3 = 2$, then $L_{11} = \sqrt{5 - 2^2} = 1$. Check: $\begin{bmatrix} 3 & 0 \\ 2 & 1 \end{bmatrix}\begin{bmatrix} 3 & 2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 9 & 6 \\ 6 & 5 \end{bmatrix}$.

When there is no such $L$. Not every matrix has a Cholesky decomposition. Two things rule it out:

• $A$ is not symmetric, meaning it differs from its own transpose: $A_{ij} \ne A_{ji}$ for some $i, j$. Every $LL^{\mathsf T}$ is symmetric, so no $L$ can rebuild such an $A$.
• A number under one of the square roots comes out zero or negative. Symmetric matrices for which this never happens are called positive-definite, and running the formulas is how you find out.

Task: write cholesky(A), where A is a square matrix given as a list of lists.

• If A is not exactly symmetric, return None.
• If any number under a square root is $\le 10^{-10}$, return None.
• Otherwise return $L$ as a list of lists of floats, including the 0.0 entries above the diagonal, with every entry rounded to 4 decimal places. Round only the finished answer; the formulas use the unrounded values.