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

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.

• I think the question title is a little confusing. Strassen's algorithm does not compute the Hadamard product. Rather, you're trying to rule out the possibility of a Strassen-like algorithm for computing the Hadamard product. – Jeremy Rouse Apr 20 '18 at 13:33
• Yes, you are right! – someone Apr 20 '18 at 13:40
• The flattening bound for tensor rank gives you the result. I'll try to write up details later. – Zach Teitler Apr 20 '18 at 14:41
• @zach-teitler Thank you, Prof. Zach Teitler. Actually, I am in the middle of reading one paper of you!. – someone Apr 20 '18 at 14:46
• @someone One of my papers? I am blushing. If you want to ask any questions, please feel free to email me any time. – Zach Teitler Apr 20 '18 at 17:52

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$.
• Yes, the Hadamard product of $m \times n$ matrices is represented by a rank $mn$ tensor... the Hadamard product of $m_1 \times m_2 \times m_3$ tensors, is represented by a rank $m_1 m_2 m_3$ tensor... :-) – Zach Teitler Apr 20 '18 at 16:27