# Computational method to compute both the (log) determinant and inverse of a matrix

Suppose I have a square matrix $$\mathbf{A} \in \mathbb{R}^{n\times n}$$ and a vector $$\mathbf{b}\in\mathbb{R}^n$$. In my application I need to accomplish two things.

1. I need to find the solution of the linear system $$\mathbf{A}\mathbf{x}=\mathbf{b}$$.
2. I need to compute the log-determinant of $$\mathbf{A}$$.

Naively, I could accomplish this by computing an eigen-decomposition of $$\mathbf{A} = \mathbf{Q}\Lambda\mathbf{Q}^{-1}$$ and use this to obtain both the inverse $$\mathbf{A}^{-1}=\mathbf{Q}\Lambda^{-1}\mathbf{Q}^{-1}$$ and the log-determinant as $$\sum_{i=1}^n \log \Lambda_{ii}$$. In this approach I require one $$\mathcal{O}(n^3)$$ operation to compute the eigen-decomposition and another $$\mathcal{O}(n^3)$$ operation to obtain the inverse of $$\mathbf{Q}$$. Is this the best way? Is there a procedure that involves only a single $$\mathcal{O}(n^3)$$ operation?

The matrix $$\mathbf{A}$$ does have a certain amount of special structure. It is of the form $$\mathbf{A} = \mathrm{Id}_n + \epsilon \mathbf{B}$$ where $$\mathbf{B}\in\mathbb{R}^{n\times n}$$, so $$\mathbf{A}$$ is not far off from the identity.

The LU decomposition will give you what you want with only $$\tfrac{2}{3}n^3 + \mathcal{O}(n^2)$$ FLOPs. The linear system is solved by solving two triangular systems. The determinant is the product of the determinants of L and U, which, in turn, are the products of the diagonal elements.

I should also add that we can't really say anything about the performance of two $$\mathcal{O}(n^3)$$ operations versus one $$\mathcal{O}(n^3)$$; they're both just $$\mathcal{O}(n^3)$$. For example, SVD takes roughly $$20n^3 + \mathcal{O}(n^2)$$ flops. So, two LU decomposition (or even ten) will be much cheaper.

• Let me add that Julia has a very clean factorize interface that selects the best factorization method for each class of matrices and lets you write F = factorize(A); x = F \ b; d = det(F); ld = logdet(F), where the only $\mathcal{O}(n^3)$ operation is the decomposition in factorize. Matlab has a similar decomposition method, but it does not support det (sad trombone). Apr 16, 2023 at 8:23

If your matrix $$A$$ is close to the identity I guess that you could try the following approximation

\begin{align} \log(\det(I + \epsilon B)) &= \log\det(I + \epsilon_0 B) + (\epsilon - \epsilon_0)\operatorname{tr}(B (I + \epsilon_0 B)^{-1}) - \frac{(\epsilon - \epsilon_0)^2}{2} \operatorname{tr}(B (I + \epsilon_0 B)^{-1} B (I + \epsilon_0 B)^{-1}) + O(\epsilon^3) \end{align}

If the expansion is around $$\epsilon = 0$$, you get

$$\log(\det(I + \epsilon B)) \approx \epsilon \operatorname{tr}(B) \, ,$$

at first order. And

$$\log(\det(I + \epsilon B)) \approx \epsilon \operatorname{tr}(B) - \frac{\epsilon^2}{2} \operatorname{tr}(B^2) \, ,$$

at second order.