4
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Geoffrey Irving Feb 22 '13 at 21:45
  • $\begingroup$ 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. $\endgroup$ – ev-br Feb 22 '13 at 22:08
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.