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 Strassen-like algorithm for computing the Hadamard product. $\endgroup$ – Jeremy Rouse Apr 20 '18 at 13:33
  • $\begingroup$ Yes, you are right! $\endgroup$ – someone Apr 20 '18 at 13:40
  • $\begingroup$ The flattening bound for tensor rank gives you the result. I'll try to write up details later. $\endgroup$ – Zach Teitler Apr 20 '18 at 14:41
  • $\begingroup$ @zach-teitler Thank you, Prof. Zach Teitler. Actually, I am in the middle of reading one paper of you!. $\endgroup$ – someone Apr 20 '18 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 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$.

  • $\begingroup$ Thanks for your nice answer. I think, this proof can be generalized to any square matrices. Or maybe non square matrices.! $\endgroup$ – someone Apr 20 '18 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$ – Zach Teitler Apr 20 '18 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.