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.

$\begingroup$ 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 Strassenlike algorithm for computing the Hadamard product. $\endgroup$– Jeremy RouseApr 20, 2018 at 13:33

$\begingroup$ Yes, you are right! $\endgroup$– someoneApr 20, 2018 at 13:40

$\begingroup$ The flattening bound for tensor rank gives you the result. I'll try to write up details later. $\endgroup$– Zach TeitlerApr 20, 2018 at 14:41

$\begingroup$ @zachteitler Thank you, Prof. Zach Teitler. Actually, I am in the middle of reading one paper of you!. $\endgroup$– someoneApr 20, 2018 at 14:46

$\begingroup$ @someone One of my papers? I am blushing. If you want to ask any questions, please feel free to email me any time. $\endgroup$– Zach TeitlerApr 20, 2018 at 17:52
1 Answer
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$ rankone 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$.

$\begingroup$ Thanks for your nice answer. I think, this proof can be generalized to any square matrices. Or maybe non square matrices.! $\endgroup$– someoneApr 20, 2018 at 16:03

$\begingroup$ 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... :) $\endgroup$ Apr 20, 2018 at 16:27