Strassen-like algorithm for Hadamard product of $2\times 2$ matrices

Question

Let $A=\pmatrix{a_1& a_2\\a_3&a_4}, B=\pmatrix{b_1& b_2\\b_3&b_4}$ be two matrices. Let $C$ be the Hadamard product of $A$ and $B$. $$C=\pmatrix{c_1& c_2\\c_3&c_4}=\pmatrix{a_1b_1& a_2b_2\\a_3b_3&a_4b_4}=\pmatrix{a_1& a_2\\a_3&a_4} \circ \pmatrix{b_1& b_2\\b_3&b_4}=A \circ B.$$ $$c_1=a_1b_1,\quad c_2=a_2b_2,\quad c_3=a_3b_3,\quad c_4=a_4b_4.$$ $$T:\mathcal{A} \times\ \mathcal{B} \to \mathcal{C}$$ where $T\in \mathcal{A}^* \otimes \mathcal{B}^* \otimes \mathcal{C}$, where $\mathcal{A}=\mathcal{B}=\mathcal{C}=\operatorname{Mat}_{2 \times 2}(\Bbbk)$, the space of $2 \times 2$ matrices over the field $\Bbbk$. We can express this product as a sum of elementary tensors: $$T=\sum^{4}_{i=1} \ a_i\otimes b_i\otimes c_i$$ where the $a_i$, etc., correspond to standard bases for the spaces of matrices (i.e., the elementary matrices) (or the dual bases). For sure the rank of $T$ is at most $4$. I am trying to show that the rank is exactly $4$. I tried to find the rank by flattening but could not find any good flattening to give me the exact rank. Any idea about flattening? thanks.

Answer 1

Let's write $T \in \mathcal{A}^* \otimes \mathcal{B}^* \otimes \mathcal{C}$ for the tensor, and $L_T : \mathcal{A} \otimes \mathcal{B} \to \mathcal{C}$ for the linear map given by $A \otimes B \mapsto A \circ B$. This $L_T$ is one of the flattenings of $T$.

You gave an expression for $T$ as a sum of four simple tensors, so the tensor rank satisfies $\operatorname{rank}(T) \leq 4$.

On the other hand, $\operatorname{rank}(T) \geq \operatorname{rank}(L_T)$. (This is the "flattening bound for rank".) One way to see this inequality is that if $U$ is a simple tensor, then $L_U$ has rank $1$; and $L_{U+V} = L_U + L_V$; so if $T$ is a sum of $r$ simple tensors, then $L_T$ is a sum of $r$ rank-one maps, so $\operatorname{rank}(L_T) \leq r$.

Finally, for $T$ and $L_T$ as above, we can find the rank of $L_T$. It has rank $4$ because $L_T$ is surjective. Given any $2 \times 2$ matrix $C$, we can get $C$ as the image of, say, $A \circ B = C$ where $A=C$ and $B$ is the matrix of all $1$s.

So $\operatorname{rank}(T) \geq \operatorname{rank}(L_T) = 4$.