# Computing eigenvalues of principal submatrices of Kronecker product of two PSD matrices

Given two PSD matrices $A \in R^{n \times n}$ and $B \in R^{m \times m}$ with eigenvalues $\lambda_i$ and $\mu_j$ respectively, the eigenvalues of the Kronecker product $A \otimes B$ are given by $\lambda_i \mu_j$, and therefore can be computed with a cost that does not exceed two times the cost of computing the eigenvalues of the biggest of the two matrices.

Is there a method to compute the eigenvalues of any principal submatrix of $A \otimes B$ with a similar computational cost?

-

Let $C$ be a principal sub-matrix of $A\otimes B$. Then you can find principal sub-matrices $\overline{A}$ (of the minimum size) and $\underline{A}$ (of the maximum size) of $A$ such that $C$ is a principal sub-matrix of $\overline{A}\otimes B$ and $\underline{A}\otimes B$ is a principal sub-matrix of $C$; one can write $$\underline{A}\otimes B\preceq C\preceq\overline{A}\otimes B,$$ where $X\preceq Y$ means $X$ is a principal sub-matrix of $Y$. Then if you compute the eigenvalues of $\overline{A}$ and $\underline{A}$, you can compute in the same way the eigenvalues of $\overline{A}\otimes B$ and $\underline{A}\otimes B$ and estimate the eigenvalues of $C$ using the Cauchy interlacing theorem.
Of course, if $C$ is not "large" enough, then $\underline{A}$ may be "empty".
Thanks for the answer. By "similar computational cost" I mean something that requires, let's say, $c \max\{m,n\}^3$ operations, or anyways a constant multiple of the cost required to compute the eigenvalues of both $A$ and $B$. –  user153643 May 28 '14 at 21:06