When can a linear transformation on the space of $n\times n$ matrices be written as a product? This question is a generalization of a previous question of mine. Let $M_{n}(\mathbb{R})$ denote the space of $n \times n$ matrices with real entries, and let $\mathcal{T}:M_{n}(\mathbb{R})\to M_{n}(\mathbb{R})$ be a linear map. What are the conditions that $\mathcal{T}$ needs to satisfy so that we may find matrices $T_{1}$ and $T_{2}$ such that the following holds $$\mathcal{T}(A)=T_{1}AT_{2}$$
The prior question was Explicit Expression for Linear Transformation of a Matrix, and a comment there made me curious as to what can be said more generally.
 A: A caveat: I am fairly sure about all statements made here, but I have not checked in detail. If you like, treat this answer as an educated conjecture.
In a nutshell, the answer is as follows. Given the matrix $[\mathcal T]_{\mathcal B}$ of the transformation (relative to a certain basis of $M_n(\Bbb R))$, there exists a permutation $\phi:M_n(\Bbb R) \to M_n(\Bbb R)$ of the matrix entries such that $\mathcal T$ can be expressed in the desired form if and only if $\phi([\mathcal T]_{\mathcal B})$ has rank $1$ (or less).

Let $e_1,\dots,e_n$ denote the standard basis of $\Bbb R^n$. Let $E_{ij} = e_ie_j^T$. Let $\mathcal B$ denote the basis given by the set of matrices $E_{ij}$ where the tuples $(i,j)$ are taken in lexicographical order. Notably, the coordinate vector of a matrix $A$ is given by $[A]_{\mathcal B} = \operatorname{vec}(A)$, where $\operatorname{vec}$ denotes the row-major vectorization operator.
If $\mathcal T(A) = T_1AT_2$, then the matrix of $\mathcal T$ relative to $\mathcal B$ is given by
$$
[\mathcal T]_{\mathcal B} = T_1 \otimes T_2^\top.
$$
Given a transformation $\mathcal T$ over $M_n(\Bbb R)$, the matrix of $\mathcal T$ can be computed as follows. Let $E_1,E_2,\dots,E_{n^2}$ be an enumeration of the elements of $\mathcal B$ (in order). Then, for any matrix $A$, we have $\mathcal T(A) = \operatorname{vec}^{-1}([\mathcal T]_{\mathcal B}\operatorname{vec}(A)),$ and the $i$th column of $[\mathcal T]_{\mathcal B}$ is given by $\operatorname{vec}(\mathcal T(E_i))$.
Now, given the matrix $M = [\mathcal T]_\mathcal B$, the question is whether there exist matrices $A,B \in M_n(\Bbb R)$ such that $M = A \otimes B$. To that end, we define a linear map $\phi:M_n(\Bbb R) \to M_n(\Bbb R)$ as follows. For any column-vectors $u,v,x,y \in \Bbb R^n$, we want to have
$$
\phi((uv^T) \otimes (xy^T)) = (u x^T) \otimes (v y^T).
$$
Notably, we have
$$
\operatorname{vec}((uv^T) \otimes (xy^T)) = \operatorname{vec}((u \otimes x)(v \otimes y)^T) = u \otimes x \otimes v \otimes y\\
\operatorname{vec}(\phi((uv^T) \otimes (xy^T))) = \operatorname{vec}[(u \otimes v)(x \otimes y)^T] = u \otimes v \otimes x \otimes y.
$$
In terms of the Kronecker product, the matrix $[\phi]_{\mathcal B}$ may thus be computed as
$$
[\phi]_{\mathcal B} = \sum_{i,j,p,q = 1}^n (e_i \otimes e_j \otimes e_p \otimes e_q)(e_i \otimes e_p \otimes e_j \otimes e_q)^T
\\ = 
\sum_{i,j,p,q = 1}^n E_{ii} \otimes E_{jp} \otimes E_{pj} \otimes E_{qq}.
$$
It turns out that $M$ can be written in the form $M = A \otimes B$ for $A,B \in M_n(\Bbb R)$ if and only if $\phi(M)$ can be written in the form $M = uv^T$ for $u,v \in \Bbb R^{n^2}$, which is to say that $\phi(M)$ has rank at most $1$. If $\phi(M)$ can be written as $\phi(M) = uv^T$ for such $u,v$, then $A,B$ can be obtained by
$$
A = \operatorname{vec}(u), \quad B = \operatorname{vec}(v).
$$
