I am interested in the eigenvalues of the matrix $J = B \otimes A + M \otimes I_n$ where $A$ is $n \times n$, binary and symmetric (it is an adjacency matrix), $B$ is $m \times m$ diagonal with positive entries, $M$ is $m \times m$ with negative entries on the diagonal and positive entries on the off-diagonal.
This is similar looking to the Kronecker sum of two matrices
\begin{equation}
A \oplus B = I_m \otimes A + B \otimes I_n
\end{equation}
The Kronecker sum has the property that it's eigenvalues are the pairwise sums of the spectrums of $A$ and $B$. More precisely, for $\lambda_i \in \text{spectrum } A$, $i = 1, …, n$, and $\mu_j \in \text{spectrum }B$, $j = 1, \ldots, m$, $A \oplus B$ has eigenvalues $\lambda_i + \mu_j$ $i = 1, \ldots, n$, $j = 1, \ldots, m$. Moreover, if $x_1, \ldots, x_n$ are right eigenvectors of $A$ and $z_1, \ldots, z_m$ are right eigenvectors of $B$, then $z_j \otimes x_i$ are the right eigenvectors of $A \oplus B$ corresponding to $\lambda_i + \mu_j$.
Is it possible to derive similar properties of the eigenvalues of $J$? I have tried the following: assume $x$ is an eigenvector of $A$ with eigenvalue $\lambda$ and $z$ is an eigenvector of $M$ with eigenvalue $\mu$. The eigenvalues of $J$ have the form
\begin{align}
J (z \otimes x) & = (B \otimes A + M \otimes I_n)(z \otimes x) \newline
& = (B \otimes A)(z \otimes x) + (M \otimes I_n)(z \otimes x) \newline
& = Bz \otimes Ax + Mz \otimes x \newline
& = Bz \otimes \lambda x + \mu z \otimes x \newline
& = \lambda(Bz \otimes x) + \mu(z \otimes x)
\end{align}
And here I am stuck. Am I wrong from the very beginning? If $B = I_m$ we have the result for the Kronecker sum. If $B = \text{diag}(b, \ldots, b)$, then $b\lambda + \mu$ is the eigenvalue of the eigenvector $z \otimes x$.
I have also thought of pursuing the generalized eigenvalue problem, and the eigenvalue perturbation theory route.
Best Answer
Note that $(B^{-1/2} \otimes I) J (B^{-1/2} \otimes I)$ is congruent to $J$, so that its signature is identical to that of $J$. We compute $$ (B^{-1/2} \otimes I) J (B^{-1/2} \otimes I) \\= (B^{-1/2} \otimes I) (B \otimes A + M \otimes I) (B^{-1/2} \otimes I) \\ = (B^{-1/2} \otimes I) (B \otimes A) (B^{-1/2} \otimes I) + (B^{-1/2} \otimes I) (M \otimes I) (B^{-1/2} \otimes I) \\ = (B^{-1/2}BB^{-1/2}) \otimes A + (B^{-1/2}MB^{-1/2} \otimes I)\\ = I \otimes A + (B^{-1/2}MB^{-1/2} \otimes I)\\ = A \oplus (B^{-1/2}MB^{-1/2}). $$ Note also that $B^{-1/2}MB^{-1/2}$ has the same signature as $M$.