# Eigenvalues and eigenvectors of $I \otimes A \ + \ B^T \otimes I$ (used in Sylvester's equation)

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: $$M = \begin{pmatrix}a&c&e\\ b&d&f\end{pmatrix} \ \rightarrow \ M^{vec} = \begin{pmatrix}a\\b\\c\\ d\\e\\f\end{pmatrix}$$

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.

• Try applying (I\otimes A + B\otimes I) to V_i\otimes U_j. (note that B and B^T have the same eigenvalues). Jun 23 '16 at 3:31
• 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 ? Jun 23 '16 at 3:55
• This questioning is issued from the very nice text of N. Higham : eprints.ma.man.ac.uk/2142/01/covered/MIMS_ep2014_26.pdf 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 $$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\\$$
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$.