Let $A$ and $B$ be $n \times n$ square matrices, with resp. eigenpairs $(\lambda_i,U_i)$ and $(\mu_j,V_j)$.

Let $I_n$ be the order $n$ identity matrix.

I have seen a result that says that the $n^2$ eigenvalues of $$M_{AB}:=I_n \otimes A \ + \ B^T \otimes I_n$$ are all the $\lambda_i+\mu_j$.

My question is: how is it possible to prove it, and under which conditions is it true ?

Another issue: can something be said about the eigenvectors of $M_{AB}$ ?

Appendix: The context is that of Sylvester equation :

Let notation $M^{vec}$ be associated with the "vectorialization" of a matrix $M$, obtained by "stacking" its columns like in the following example: \begin{equation} M = \begin{pmatrix}a&c&e\\ b&d&f\end{pmatrix} \ \rightarrow \ M^{vec} = \begin{pmatrix}a\\b\\c\\ d\\e\\f\end{pmatrix} \end{equation}

We will need the fundamental technical property of Kronecker product:

$$\underbrace{(ABC)^{vec}}_{vector}=\underbrace{(C^T \otimes A)}_{matrix}.\underbrace{(B)^{vec}}_{vector} \ \ \ (*)$$

Sylvester equation is

$$\text{find} \ X \ \ \ \text{such that} \ \ \ AX+XB=C$$

Being evidently equivalent to

$$(AX)^{vec} + (XB)^{vec} = C^{vec}$$

it can can be transformed, using property (*) and linearity of Kronecker's product, into:

$$(I \otimes A \ + \ B^T \otimes I)X^{vec}=C^{vec}$$

explaining the usefulness of matrix $M_{AB}=I \otimes A \ + \ B^T \otimes I$, its inversibility being a condition for a unique solution to Sylvester's equation, this inversibility being determined by the fact that none of its eigenvalues is zero.

  • 2
    $\begingroup$ Try applying (I\otimes A + B\otimes I) to V_i\otimes U_j. (note that B and B^T have the same eigenvalues). $\endgroup$
    – stewbasic
    Jun 23 '16 at 3:31
  • $\begingroup$ Thanks @stewbasic, now it becomes clear ! Could you transform your comment into an answer (maybe giving some supplementary details) in order I can validate it as the answer to this question ? $\endgroup$
    – Jean Marie
    Jun 23 '16 at 3:55
  • $\begingroup$ This questioning is issued from the very nice text of N. Higham : eprints.ma.man.ac.uk/2142/01/covered/MIMS_ep2014_26.pdf $\endgroup$
    – Jean Marie
    Jun 23 '16 at 4:08

Let $U_A$, $T_A$, $U_B$, $T_B$ form the complex Schur factorization of A and $B^T$, i.e. $U_A T_A U_A^H = A$, $U_B T_B U_B^H = B^T$, where $U_A$, $U_B$ are unitary matrices, $T_A$, $T_B$ are upper triangular matrices with complex entries, and $X^H$ denotes conjugate transposition. Then \begin{equation} I_n\otimes A + B^T\otimes I_n = (U_B I_n U_B^H)\otimes (U_A T_A U_A^H) + (U_B T_B U_B^H)\otimes(U_A I_n U_A^H)\\ = (U_B \otimes U_A)\times(I_n\otimes T_A)\times(U_B^H\otimes U_A^H) + (U_B \otimes U_A)\times(T_B\otimes I_n)\times(U_B^H\otimes U_A^H)\\ = (U_B \otimes U_A)\times(I_n\otimes T_A + T_B\otimes I_n)\times(U_B^H\otimes U_A^H)\\ = (U_B \otimes U_A)\times(I_n\otimes T_A + T_B\otimes I_n)\times(U_B\otimes U_A)^H\\ \end{equation}

Since the Kronecker product of unitary matrices is an unitary matrix, we have the Schur factorization of $M_{AB}$. Since i-th diagonal entries of $T_A$ and $T_B$ are respectively $\lambda_i$ and $\mu_i$, then it is clear that eigenvalues of $M_{AB}$ are given by $\lambda_i + \mu_j$ for all combinations of $i, j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.