Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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 at 21:06

Your Answer

 
discard

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.