# Trace of inverse from LU decomposition

Given an LU decomposition of $$A\in \mathbb{R}^{n\times n}$$, is there a way to compute $$\operatorname{trace}(A^{-1})$$ with lower complexity than that of the inversion ($$O(n^3)$$ in practice)?

This question has been asked already on Mathoverflow twice and on Math.SE, but the answers there are not useful.

Base case: Computing the factorization requires $$\frac 2 3n^3$$ operations and the inverse requires $$\frac 4 3n^3$$ operations. Computing the trace adds $$O(n)$$. Let's round that to $$2n^3$$.
LU case: Computing the factorization requires $$\frac 2 3n^3$$ operations. If you were to compute $$L^{-1}$$ and $$U^{-1}$$, those operations each require $$\frac 1 3n^3$$ operations. The trace of the matrix product $$U^{-1}L^{-1}$$ is essentially a dot product of two vectors with length $$n^2$$, call that $$O(n^2)$$. Let's round that to $$\frac 4 3n^3$$.
• Good call. I edited my answer to include the factorization time for inversion. Fundamentally, inverting a triangular matrix is still $O(n^3)$, and you need every coefficient of $L$ and $U$ to compute the trace. However, reducing the run time of your routine by 30 or 50% is definitely worth the effort, even if you can't change the asymptotic behavior! Commented Nov 13, 2020 at 17:38