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

-
The text passage discusses a mathematical problem related to the determinant of a sum of Kronecker products of matrices. It includes a question about the computational efficiency of computing this determinant and provides several approaches and special cases for solving it.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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).

-
user
The text passage discusses a mathematical problem related to the determinant of a sum of Kronecker products of matrices. It includes a question about the computational efficiency of computing this determinant and provides several approaches and special cases for solving it.

TYPE: SINGLE_QUESTION_WITH_ANSWER