# Decompose a Matrix into a Sum of Tensor Products

Given the matrix $$\phantom{-} \pmatrix{ 0 & a+b& -b+a&0\\ \phantom{-}a+c& a+d&\phantom{-} b+c&b+d\\ -c+a&c+b&-d+a&d+b\\ 0&c+d&\phantom{-}d-c&0\\ }.$$ How could one decompose it into the (smallest) sum of tensor product, like $M\otimes E_{k}$ and $E_{n}\otimes M$, where $M=\pmatrix{a&b\\c&d}$ and $E_j$ is a matrix with entries $0$ or $\pm 1$, like $\pmatrix{0&1\\0&0}$ or $\pmatrix{1&\phantom{-}1\\1&-1}$. I tried it with sums of $M\otimes 1_{kn}$ and $1_{kn}\otimes M$ ($1_{kn}$ has a $1$ at element $(k,n)$ and $0$ elsewhere), but haven't found a solution, yet...

In order to minimise the number of summands, feel free to substitue every element by its negative (if a solution exists).

-
I suppose this $E \otimes M-M\otimes E$ ( $E=\pmatrix{1&1\\1&1}$) is not included in the "feel free to substitue every element by its negative". – P.. Nov 9 '12 at 22:33
@Pambos Why not? You can construct it from the $1_{kn}$'s... – draks ... Nov 10 '12 at 12:44

You cannot decompose $$A=\phantom{-} \pmatrix{ 0 & a+b& -b+a&0\\ \phantom{-}a+c& a+d&\phantom{-} b+c&b+d\\ -c+a&c+b&-d+a&d+b\\ 0&c+d&\phantom{-}d-c&0\\ }$$ into $X\otimes M+M\otimes Y$. The system $A=X\otimes M+M\otimes Y$ for $X=\pmatrix{x_1&x_2\\x_3&x_4}, \ Y=\pmatrix{y_1&y_2\\y_3&y_4}$ does not have a solution in $x_i,y_i$.
For, $X\otimes M+M\otimes Y= \pmatrix{ x_1a+ay_1 & x_1b+ay_2& x_2a+by_1&x_2b+by_2\\ x_1c+ay_3& x_1d+ay_4& x_2c+by_3&x_2d+by_4\\ x_3a+cy_1&x_3b+cy_2&x_4a+dy_1&x_4b+dy_2\\ x_3c+cy_3&x_3d+cy_4&x_4c+dy_3&x_4d+dy_4\\ },$
where $x_i,y_i \in \mathbb{Z}.$ The elements $(3,4)$ and $(4,3)$ of this matrix give $x_4=1$ and $x_4=-1↯.$
However, for $E=\pmatrix{1&1\\1&1}$ you have $$E\otimes M-M\otimes E=\phantom{-} \pmatrix{ 0 & -a+b& -b+a&0\\ -a+c& -a+d& -b+c&-b+d\\ -c+a&-c+b&-d+a&-d+b\\ 0&-c+d&-d+c&0\\ }.$$