Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given four real symmetric matrices $A,B \in \mathbb{R}^{n \times n}$ and $C,D \in \mathbb{R}^{m \times m}$, is there an efficient way to compute the determinant:

$\det|A \otimes C + B \otimes D |$

share|improve this question
    
What do you mean by "efficient"? –  Igor Rivin Jul 6 at 19:24
    
Oh, sorry. I meant computationally efficient. By analogy, we can compute $|A \otimes C|$ via $|A|^m|C|^n$, which is vastly cheaper when $m,n>>1$. I'm wondering if there are any known results for a sum, that are less expensive than explicitly taking determinant of the full $mn \times mn$ matrix. –  jpillow Jul 6 at 19:38

4 Answers 4

up vote 2 down vote accepted

The case $A$ symmetric positive definite and $B$ symmetric and $C$ positive definite and $D$ symmetric is slightly easier.

In that case, first write $P'AP=I$ and $P'BP=\Delta_1$, and $Q'CQ=I$ and $Q'DQ=\Delta_2$, where $\Delta_1$ and $\Delta_2$ are diagonal matrices.

Now, write $(P\otimes Q)'(A\otimes C)(P\otimes Q) + (P\otimes Q)'(B\otimes D)(P\otimes Q)$ equals $(P'AP \otimes Q'CQ) + (P'BP \otimes Q'DQ) = (I\otimes I) + (\Delta_1\otimes \Delta_2)$.

Note that it takes $O(n^3+m^3)$ time to compute $P$ and $Q$.

share|improve this answer

I am not sure what the OP means by efficient, but note that in the special case where $C=B=I$ the eigenvalues of $A \otimes I + I \otimes B$ are just the sums of the eigenvalues of $A$ and $B.$ It seems pretty clear that computing the product of all these sums cannot be substantially easier than by the obvious expedient of computing the two eigenvalue decompositions, which IS $O(n^3)$ (assume $m=n$ for simplicity), which is better than the really dumb $O(n^6)$ algorithm, but certainly not quite instant.

share|improve this answer
    
Fantastic, yes —- that's exactly what I meant. Only, what about the case where $C$ and $B$ are not the identity. I'm simply trying to avoid the "dumb" $O(n^6)$ cost. –  jpillow Jul 6 at 19:41

Assume that $m=n$. If $A,B$ are invertible, then $A\bigotimes C+B\bigotimes D=A\bigotimes C(I_{n^2}+A^{-1}B\bigotimes C^{-1}D)$. Thus $\det(A\bigotimes C+B\bigotimes D)=|A|^n|C|^n\Pi_{i,j}(1+\lambda_i\mu_j)$ where $spectrum(A^{-1}B)=(\lambda_i)_i$ and $spectrum(C^{-1}D)=(\mu_j)_j$. These calculations have a numerical complexity in $O(n^3)$.

If $A$ or-and $B$ are singular, then change $A,B$ with $A+t I_n,B+t I_n$ (where $t\not=0$), calculate as above, and finally, consider the limit when $t$ tends to $0$.

share|improve this answer

Use a generalized Schur decomposition, or QZ decomposition, of the pairs A,B and C,D, and then work as in Suvrit's and Igor's answers. This reduces the problem to a triangular one, which is then easy. This is similar to loup blanc's answer, but it should be more stable in practice (all the factorizations involve orthogonal matrices only, so one can prove backward stability using standard techniques).

share|improve this answer

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.