Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

What do you mean by "similar computational cost"? Like multiplying two numbers? That is unlikely. However, you can estimate them somewhat efficiently.

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

share|cite|improve this answer
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

Your Answer


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.