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