Consider a real-symmetric square matrix, $H$, which we take to be "large" for computational purposes - say, $10^{4}$ rows and $10^{4}$ columns. Such a matrix can be diagonalized using standard numerical methods; let's suppose that we have access to all spectral data (eigenvalues, eigenvectors, anything else you can imagine) of $H$.
Now, I want to study the real-symmetric matrix $L=H\otimes I - I\otimes H$, where $I$ is the identity matrix on $10^{4}$ elements. If we were to directly study $L$, it is now difficult to proceed computationally - with $10^{16}$ elements, it is hard to carry out, for example, numerical diagonalization. Of course, we are lucky - since we have access to the eigenvectors of $H$, we are spared the difficult part of diagonalizing $L$, and can easily read off its eigenvalues.
Since we have so much information about $H$, I would like to leverage that to learn more about $L$. In particular, I am interested in computing the Hessenberg decomposition of $L$. More precisely, the Hessenberg decomposition allows us to write $L = PAP^{\dagger}$ for a unitary matrix $P$ and a symmetric tridiagonal matrix $A$. I am interested in particular in the off-diagonal elements of $A$, which is to say, I need neither $P$ nor the diagonal elements of $A$.
Unfortunately the Hessenberg decomposition is roughly as difficult to carry out as exact diagonalization; the algorithm requires $\mathcal{O}(n^{3})$ arithmetic operations to carry out, where $n$ is the linear dimension of $L$. My hope is that our advanced knowledge of $H$ can simplify this problem substantially; it seems plausible to me that complete knowledge of the eigenspace of $L$ affords a significant computational advantage. I haven't been able to determine how these representations should be related, numerically or analytically, and am curious if it's foolish to keep trying. Perhaps even exact knowledge of the spectrum is insufficient to afford a significant advantage in this problem.