# simplifying a product of a determinant and an inverse of a (nearly) singular matrix

Given two square matrices, $A$ and $B$, I need to calculate the product $tr(A^{-1}B)\times detA$. The catch is that $A$ is singular --- more precisely, it depends on some parameter $t$, such that it's non-singular at any finite $t$ and only becomes singular in the limit $t\to 0$ --- which is exactly the limit I need to evaluate the above expression.

It seems not unreasonable to assume that the product $det(A)\times A^{-1}$ is well-behaved even when both det and inverse are not, since the inverse contains one over the determinant. This way, I can take the limit of $t\to 0$ analytically, and the original expression reduces to the sum over the products of the elements of $B$ and minors of $A$. Which seems to require $O(N^4)$ operations ($N$ terms, $N^3$ operations for each of the minors), where $N$ is the size of $A$ and $B$.

On the other hand, if I were to just work at finite $t$-s, I'd only need $O(N^3)$ operations.

My gut feeling is that there must be a way of doing the $t\to 0$ computation in just $O(N^3)$, but I don't see it. Since I doubt I'm the first person to be thinking about these things, I'd appreciate any hints, tips, pointers to the literature, counterexamples, hints at impossibility --- anything.

In case it matters, my matrices are dense, and they are not that huge, $N$ is about a hundred, maybe a few hundreds. But I'll need to process quite a number of such pairs, so that overall complexity matters,

-
This product is called a cofactor matrix. Unfortunately, unless the determinant happens to be close to one, the cofactor matrix can easily overflow the exponent range (even for double precision) for $N \approx 100$. –  Geoffrey Irving Feb 22 '13 at 21:45
Thanks Geoffrey! I guess my question was (and still is) if there's a way of doing this computation without constructing the cofactor matrix explicitly. –  ev-br Feb 22 '13 at 22:08

## 1 Answer

I had to do this once, and the trick is to use the singular value decomposition (SVD). The SVD of $A$ is $A=U\Sigma V^H$, so

$$\operatorname{tr}(A^{-1}B) \cdot \det A = \operatorname{tr}(V\Sigma^{-1}U^H B) \det \Sigma \det (UV^H)$$

Applying the cyclic permutation invariance of the trace,

$$= \operatorname{tr}(\Sigma^{-1}U^H B V) \det (\Sigma)\det (UV^H) = \operatorname{diag}(\Sigma^{-1})^T\operatorname{diag}(U^H B V) \det(\Sigma)\det (UV^H)$$ where the first pair of diag's in the right-most expression is an inner product. At this point the singularity in $\Sigma^{-1}$ can cancel with the singularity in $\det\Sigma = \prod_j \sigma_j$. This assumes $B$ is square and $A$ is rank deficient by 1.

-
great, thanks a whole lot Victor! –  ev-br Feb 24 '13 at 12:24