# Cholesky decomposition of the inverse of a matrix

I have the Cholesky decomposition of a matrix $M$. However, I need the Cholesky decomposition of the inverse of the matrix, $M^{-1}$. Is there a fast way to do this, without first computing $M^{-1}$? In other words, is there a relationship between the Cholesky decompositions of a matrix and of its inverse?

My matrix is a covariance matrix and, hence, positive-definite.

If $L^T L = R$ is the available Cholesky decomposition, then inverting both sides of the equation you get,

$$L^{-1}(L^{T})^{-1} = R^{-1}$$

And since transposition and inverse are interchangeable:

$$L^{-1}(L^{-1})^{T} = R^{-1}$$

So if you define $P = (L^{-1})^T$ this is your desired answer. In other words,

$$P^{T}P=R^{-1}$$

• The decomposition obtained here for $R^{-1}$ is not the Cholesky decomposition as the first factor ,$P^T$, is upper triangular (should be lower triangular). – Juho Kokkala Jan 29 '17 at 12:58
• @JuhoKokkala Why does that matter? It is still triangular. – Rodrigo de Azevedo Jul 11 '18 at 17:33
• Whether it matters in practice would depend on what you use the Cholesky factor for (not specified in the question). The question asks how to get the Cholesky decomposition of $M^{-1}$, and this answer gives some decomposition that (in the general case) is not the Cholesky decomposition. – Juho Kokkala Jul 11 '18 at 18:30

I do not believe there is any way to do it without some $O(n^3)$ operation. Different choices can have different constants. In particular, assuming $M=LL^T$ and you already have the Cholesky factor $L$, computing $L^{-1}$ costs ~$n^3/3$ flops, and given that, you can form $M^{-1}$ = $L^{-T}L^{-1}$ in ~$n^3/3$ flops and take its Cholesky in another ~$n^3/3$ flops, which is ~$n^3/3$ flops cheaper than pretending you don't have $L$, forming $M^{-1}$ directly and taking its Cholesky. But it's still $O(n^3)$.