Hadamard and tensor products: $\operatorname{rank}(A\circ B)\le\operatorname{rank}(A)\operatorname{rank}(B)=\operatorname{rank}(A\otimes B)$

$\newcommand{\rank}{\operatorname{rank}}$

For two matrices $A$ and $B$, the Hadamard product $A \circ B$ is the matrix obtained by $(A \circ B)_{i, j} = A_{i, j} B_{i, j}$.

Prove that $\rank(A \circ B) \le \rank(A) \rank(B) = \rank (A \otimes B)$

The first inequality is quite easy but I can't seem to put it into words (so maybe it isn't). Any help on either would be much appreciated.

• Velcome to the site! – kjetil b halvorsen May 28 '14 at 13:52

Let $r_A$ and $r_B$ are ranks of $A$ and $B$. Using, e.g., the SVD, $A$ and $B$ can be written as $$A=\sum_{i=1}^{r_A}p_iq_i^*, \quad B=\sum_{j=1}^{r_B}s_jt_j^*,$$ for some vectors $p_i$, $q_i$, $i=1,\ldots,r_A$, and $s_j$, $t_j$, $j=1,\ldots,r_B$. We have $$A\circ B=\sum_{i=1}^{r_A}\sum_{j=1}^{r_B}(p_i\circ s_j)(q_i\circ t_j)^*,$$ so $A\circ B$ is a sum of $r_Ar_B$ rank-one matrices and thus its rank cannot be higher than $r_Ar_B$.

To show that $r_Ar_B=\mathrm{rank}(A\otimes B)$, note that if $A=U_A\Sigma_AV_A^*$ and $B=U_B\Sigma_BV_B^*$ are SVDs of $A$ and $B$, respectively, then $$A\otimes B=(U_A\otimes U_B)(\Sigma_A\otimes \Sigma_B)(V_A\otimes V_B)^*$$ is an SVD of $A\otimes B$. So since there are $r_A$ and $r_B$ nonzero singular values of $A$ and $B$, respectively, there are $r_Ar_B$ nonzero singular values of $A\otimes B$.

• Hello, would you mind explaining the first line? I've not seen that version of SVD before. – user153840 May 28 '14 at 16:22
• @user153840 Every rank-$r$ matrix can be written as a sum of $r$ rank-one matrices. It's not exactly SVD, but can be deduced from it. It is essentially the same as the first equation in $\text{Om(nom)}^3$'s answer. – Algebraic Pavel May 28 '14 at 16:33

I find that the first inequality is best done using singular value decomposition.

Let $$B$$ have rank $$r$$. Note that $$B$$ can be written in the form $$B = \sum_{k=1}^r \sigma_k u_k v_k^*$$ So that $$A \circ B = \sum_{k=1}^r \sigma_k A \circ (u_k v_k^*)$$ Now here's the clever bit: note that $$(A \circ u_kv_k^*)[i,j] = A[i,j] \cdot u_k[i]v_k[j]$$ So that $$A \circ u_kv_k^* = \pmatrix{ u_k&&\\ &\ddots&\\ &&u_k[m] } A \pmatrix{ v_k&&\\ &\ddots&\\ &&v_k[n] }$$ Which has rank less than or equal to the rank of $$A$$.

Thus, $$A\circ B$$ is the sum of $$r$$ (that is, rank$$(B)$$) matrices whose rank is at most the rank of $$A$$. With the appropriate rank inequality, the conclusion follows.

As for the second part: it now suffices to note that $$\operatorname{rank}(A \otimes B) = \operatorname{rank}(A) \operatorname{rank}(B)$$ as is stated here for instance.

• For the last line, obviously left to right doesn't seen explaining. How about right to left, though? – user153840 May 28 '14 at 16:28
• I don't really know how to get to grips with $u \otimes v$. Is it the same way as you did with $A \otimes B$? And also, even if we proved this, would this show the ranks are equal? – user153840 May 28 '14 at 16:30