How to calculate inverse of sum of two Kronecker products with specific form efficiently? I have a matrix with specific form of $A\otimes I + B\otimes J$ where $A$ and $B$ are general dense matrices, $n\times n$. $I$ is an $m\times m$ identity matrix. $J$ is a $m \times m$ dense matrix with 1 everywhere.
Is there any efficient way to calculate $(A\otimes I + B \otimes J)^{-1}$ efficiently?
If it is impossible, what if we assume $B$ is diagonal?
 A: In more generality, we can write down an "efficient" inverse for both
$$A_1 \otimes A_2 + B_1 \otimes B_2 \quad \text{and} \quad A_1 \otimes B_2 + B_1 \otimes A_2$$
whenever $B_1$ and $B_2$ are nonsingular. The matrix in the question is of the fist form with $A_1 = B$, $A_2=J$, $B_1 = A$, $B_2 = I$ (since, as noted by Denis Serre in his answer, the matrix can only be nonsingular when $A$ is). The idea is to simultaneously diagonalize each pair $A_i, B_i$ independently, using the generalized eigendecompositions,
$$A_i V_i = B_i V_i \Lambda_i$$
where $V_i$ is the nonsingular matrix of eigenvectors and $\Lambda_i$ the diagonal matrix of eigenvalues. It's then immediate that the "generalized" Kronecker sums have generalized eigendecompositions
$$(A_1 \otimes A_2 + B_1 \otimes B_2)(V_1 \otimes V_2) = (B_1 \otimes B_2)(V_1 \otimes V_2)(\Lambda_1 \otimes \Lambda_2 + I \otimes I),$$
$$(A_1 \otimes B_2 + B_1 \otimes A_2)(V_1 \otimes V_2) = (B_1 \otimes B_2)(V_1 \otimes V_2)(\Lambda_1 \otimes I + I \otimes \Lambda_2),$$
whence
$$(A_1 \otimes A_2 + B_1 \otimes B_2)^{-1} = (V_1 \otimes V_2)(\Lambda_1 \otimes \Lambda_2 + I \otimes I)^{-1} (V_1^{-1}B_1^{-1} \otimes V_2^{-1}B_2^{-1}),$$
$$(A_1 \otimes B_2 + B_1 \otimes A_2)^{-1} = (V_1 \otimes V_2)(\Lambda_1 \otimes I + I \otimes \Lambda_2)^{-1} (V_1^{-1}B_1^{-1} \otimes V_2^{-1}B_2^{-1}),$$
provided none of the eigenvalues are zero. This simplifies further if one or both of the matrix pencils has more structure. E.g., if $A_2$ is symmetric and $B_2$ symmetric positive definite, then we can take $V_2$ such that $V_2^T B_2 V_2 = I$ so that $V_2^{-1} B_2^{-1} = V_2^T$. This is the case for the matrix in the question with $A_2 = J$, $B_2 = I$.
In the context of numerical computation, if the matrices are not symmetric and either matrix of eigenvectors $V_i$ is ill-conditioned, it may be better to work with the QZ decomposition (generalizing the Schur decomposition) instead, which has a similar tensor product structure. If $A_i, B_i$ have QZ decompositions
$$ A_i = Q_i S_i Z_i^*, \quad B_i = Q_i T_i Z_i^*, $$
where $Q_i, Z_i$ are unitary and $S_i, T_i$ triangular, then we also have the QZ decomposition
$$ (A_1 \otimes A_2 + B_1 \otimes B_2) = (Q_1 \otimes Q_2) (S_1 \otimes S_1 + T_1 \otimes T_2) (Z_1 \otimes Z_2)^*$$
$$ B_1 \otimes B_2 = (Q_1 \otimes Q_2) (T_1 \otimes T_2) (Z_1 \otimes Z_2)^*$$
since the Kronecker product of triangular (unitary) matrices is triangular (unitary). Thus
$$ (A_1 \otimes A_2 + B_1 \otimes B_2)^{-1} = (Z_1 \otimes Z_2) (S_1 \otimes S_2 + T_1 \otimes T_2)^{-1} (Q_1 \otimes Q_2)^*,$$
requiring the inverse of a large triangular instead of diagonal matrix. This approach works even when one or both $B_i$ are singular, requiring only that the pencils $A_i - \lambda B_i$ are regular (and again that no eigenvalues, which appear along the diagonal of $S_1 \otimes S_2 + T_1 \otimes T_2$, are zero).
A: Following Nickelnine37's idea, but in the right way, let us write your matrix
$$M=(A\otimes I)(I_{nm}+C\otimes J),\qquad C:=A^{-1}B.$$
Thus
$$M^{-1}=(I_{nm}+C\otimes J)^{-1}(A^{-1}\otimes I).$$
Finally
$$(I_{nm}+C\otimes J)^{-1}=I_{nm}+K\otimes J$$
where
$$K=-(I+mC)^{-1}C=(A+mB)^{-1}B,$$
because of $J^2=mJ$.
Is this what you want ?
Remark. I implicitely assumed that $A$ is invertible. If it is not, and $m\ge2$, then $M$ is not invertible, because $\ker M$ contains $(\ker A)\otimes(\ker J)$, where each factor is non-trivial.
A: Assuming $B$ and $J$ are invertible and that all matrices are square:
\begin{align}
(A \otimes I + B \otimes J)^{-1} &= \big( (AB^{-1} \otimes J^{-1} + I \otimes I)(B \otimes J) \big)^{-1} \\
&= (B^{-1} \otimes J^{-1})\big(AB^{-1} \otimes J^{-1} + I \otimes I\big)^{-1}
\end{align}
Now eigen-decompose $AB^{-1}$ and $J$.
$$
AB^{-1} = U \Lambda_U U^{-1}, \quad J = V \Lambda_V V^{-1} 
$$
Substitute these definitions in.
\begin{align}
(A \otimes I + B \otimes J)^{-1} &=  (B^{-1} \otimes J^{-1})\big(U \Lambda_U U^{-1} \otimes V \Lambda_V^{-1} V^{-1}  + I \otimes I \big)^{-1} \\
&= (B^{-1} \otimes J^{-1})\big((U \otimes V)(\Lambda_U \otimes \Lambda_V^{-1} + I \otimes I)( U^{-1} \otimes V^{-1})\big)^{-1} \\
&= (B^{-1}U \otimes J^{-1}V)(\Lambda_U \otimes \Lambda_V^{-1} + I \otimes I)^{-1}( U^{-1} \otimes V^{-1}) \\
\end{align}
And there you have it.
