# Determinant of sum of Kronecker products

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

-
What do you mean by "efficient"? – Igor Rivin Jul 6 '14 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 '14 at 19:38

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

-

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.

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

-

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

-