$AXB$ sort of decomposition?

Question

Let $f: M_n(\mathbb{C}) \to M_n(\mathbb{C})$ be a $\mathbb{C}$-linear map (not necessarily an algebra homomorphism). Do there exist matrices $A_1, \dots, A_d \in M_n(\mathbb{C})$ and $B_1 \dots, B_d \in M_n(\mathbb{C})$ such that $$f(X) = \sum_{j = 1}^d A_jXB_j,\text{ }\forall\,X \in M_n(\mathbb{C})?$$

Answer 1

You can construct it one term at a time by letting $A_j$ and $B_j$ be matrices that are zeroes everywhere except for one entry. This requires $d = n^4$ in general; I imagine you can do better.

Answer 2

$f$ is the sum of at most $n^2$ tensor products. cf. https://en.wikipedia.org/wiki/Kronecker_product

Proof. Let $A=[B_{k,l}]\in M_{n^2}$ be the associated block matrix, where $B_{k,l}\in M_n$. Let $C^{i,j}=[C_{k,l}]$ be the block matrix defined by $C_{k,l}=0$ except $C_{i,j}=B_{i,j}$. Then $C^{i,j}=E_{i,j}\otimes B_{i,j}$; since $A=\sum_{i,j}C^{i,j}$, we are done. Perhaps we can do better??

EDIT. I think that we cannot do better. For instance $A=\begin{pmatrix}1&0&0&1\\0&0&0&0\\0&0&0&0\\1&0&0&1\end{pmatrix}$ cannot be written as the sum of less than $4$ tensor products.

Answer 3

Here is a "coordinate-free" proof:

Proposition: Every linear map $M_n (\mathbb{C}) \to M_n (\mathbb{C})$ can be expressed in the form $$X \mapsto \sum_{i=1}^{d} A_i X B_i$$ for some matrices $A_1, \cdots, A_d, B_1, \cdots, B_d \in M_n (\mathbb{C})$.

Proof: Consider the linear map $T: M_n (\mathbb{C}) \otimes M_n (\mathbb{C}) \to \text{End} (M_n (\mathbb{C}))$ given by $$A\otimes B \mapsto (X \mapsto AXB)$$ on pure tensors and extended to the whole tensor product by linearity. Since both the domain and codomain have dimension $n^4$, to prove the proposition it suffices to show $T$ is injective.

Equivalently, we must show that if $\sum_{i=1}^{d} A_i X B_i = 0$ for all $X \in M_n (\mathbb{C})$, then for each $1\le i \le d$ either $A_i = 0$ or $B_i = 0$. We can do this by induction.

For the base case, suppose $AXB = 0$ for all $X \in M_n (\mathbb{C})$. If $B \neq 0$, then there is some $v \in \mathbb{C}^n$ such that $Bv \neq 0$. Thus, for any $w \in \mathbb{C}^n$, we may choose $X$ such that $XBv = w$, hence $Aw = 0$ for all $w\in \mathbb{C}^n$, i.e. $A = 0$.

Now, suppose $\sum_{i=1}^{d} A_i X B_i = 0$ for all $X \in M_n (\mathbb{C})$. Without loss of generality, we may assume $A_1, \cdots, A_d$ are linearly independent in $M_n (\mathbb{C})$ (if not, replace one of the $A_i$'s by a nontrivial linear combination of the others, and then we reduce ourselves to a case with smaller $d$).

If $B_1 \neq 0$, there is some $v\in \mathbb{C}^n$ such that $B_1 v \neq 0$. Let $P$ denote the orthogonal projection onto the line spanned by $B_1 v$. If $w\in \mathbb{C}^n$, we may choose $Y \in M_n (\mathbb{C})$ such that $YB_1 v = w$. Then with $X: = YP$, we see that $X B_i v = \lambda_i w$ for some constants $\lambda_i \in \mathbb{C}$ where $\lambda_1 = 1$ (note the $\lambda_i$'s don't depend on $w$). It follows that $$\sum_{i=1}^{d} A_i X B_i v = \sum_{i=1}^{d} \lambda_i A_i w = 0$$ for all $w\in \mathbb{C}^n$, hence $\sum_{i=1}^{d} \lambda_i A_i = 0$. By linear independence of the $A_i$'s, we conclude $A_1 = 0$. Now, by induction, we're done. $\blacksquare$