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.

  • $\begingroup$ Velcome to the site! $\endgroup$ – 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$.

  • $\begingroup$ Hello, would you mind explaining the first line? I've not seen that version of SVD before. $\endgroup$ – user153840 May 28 '14 at 16:22
  • $\begingroup$ @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. $\endgroup$ – 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[1]&&\\ &\ddots&\\ &&u_k[m] } A \pmatrix{ v_k[1]&&\\ &\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.

  • $\begingroup$ For the last line, obviously left to right doesn't seen explaining. How about right to left, though? $\endgroup$ – user153840 May 28 '14 at 16:28
  • $\begingroup$ 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? $\endgroup$ – user153840 May 28 '14 at 16:30

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.