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

Question

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.

Answer 1

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