Rank of $A\otimes B - B\otimes A$ Let $A$, $B\in\mathbb{R}^{n\times n}$ be full-rank random matrices and define the Kronecker products $P=A\otimes B$ and $Q=B\otimes A$. Through example-based examination, I have found that
$\text{rank}(P-Q)=n^2-n$,
but I am struggling to formulate a proof of this. Thus far, I have focused on the fact that $P$ and $Q$ are permutation-similar such
$Q=ZPZ$,
where $Z=Z^T=Z^{-1}$. We know that $P$ and $Q$ have the same eigenvalues and that the eigenvectors, $\Phi_P$ and $\Phi_Q$, are related by $\Phi_P=Z\Phi_Q$. Furthermore,
$\Phi_P-Z\Phi_QZ=T=[T_1 \ldots T_{n^2}]$,
where $T_i=0$ for $i \in \{1:n+1:n^2\}$. I presume that this somehow shows the rank condition, but I cannot figure out the coupling. I would like to ask whether I am on the right track; and if yes, can you provide some pointers on how I proceed to show the rank condition?
 A: A slight variant of Fedor's answer: using a QZ (generalized Schur) factorization $A=QT_A Z, B = Q T_BZ$, you can make an orthogonal change of basis such that $A$ and $B$ are both upper triangular. Then $P$ and $Q$ are both upper triangular, too, and the eigenvalues of $P-Q$ are its diagonal elements $a_{ii}b_{jj} - b_{ii}a_{jj}$, $i,j=1,\dots,n$. This makes it evident that $n$ of them are zeros, and that the rest of the entries in the upper triangle, generically, is not.
(EDIT: note that this change of variables does not preserve eigenvalues, since $Q$ and $Z$ are different in general, but it does preserve the rank.)
A: For generic $A,B$ the matrix $A$ is invertible and $B=CA$, where $C$ is also generic. We have $(A\otimes B-B\otimes A)(u\otimes v)=Au\otimes CAv-CAu\otimes Av$. The vectors $Au$ run over the whole $\mathbb{R}^n$, so the image of the operator $A\otimes B-B\otimes A$ is the same as the image of $I\otimes C-C\otimes I$ (where $I$ is the identity matrix). Choosing an eigenbasis for $C$ (it exists if $C$ is generic, possibly it is complex but the rank is the same over $\mathbb{R}$ and over $\mathbb{C}$), where $Ce_i=\lambda_i e_i$, we get $$(I\otimes C-C\otimes I)(e_i\otimes e_j)=(\lambda_j-\lambda_i)e_i\otimes e_j.$$
So, $(e_i\otimes e_j)$ is an eigenbasis, and all but $n$ eigenvalues are non-zero.
