Determinant of sum of Kronecker products

Question

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 |$

Answer 1

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$.

Answer 2

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.

Answer 3

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$.

Answer 4

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).