Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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,

share|improve this question
    
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. –  Zhenya Feb 22 '13 at 22:08

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
great, thanks a whole lot Victor! –  Zhenya Feb 24 '13 at 12:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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