1
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Apr 20, 2018 at 13:33
  • $\begingroup$ Yes, you are right! $\endgroup$
    – someone
    Apr 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$ Apr 20, 2018 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, 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$ Apr 20, 2018 at 17:52

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • $\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, 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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