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

Question

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

Answer 1

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.

Answer 2

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