How I can show that
$$
\operatorname{rank}(A\circ B) \leq \operatorname{rank}(A)\operatorname{rank}(B)
$$
where $A,B$ are rectangular matrices and $\circ$ is the Hadamard product between the two.
Similarly, how can we show that if $A$ has rank d, then $\operatorname{rank}(A\circ A)$ is at most $d+1 \choose 2$ ?
Best Answer
The first part of the question is well covered in the other question on Mathematics SE. To prove $\text{rank}\left(A\circ A\right)\leq {{d+1}\choose 2}$, we should specialize the derivation in the aforementioned question:
Writing matrix $A$ as a sum of rank-one matrices: $$ A=\sum_{i=1}^{d}p_iq_i^* $$ results in $$ A\circ A = \sum_{i=1}^{d}\sum_{j=1}^{d}(p_i\circ p_j)(q_i\circ q_j)^*. $$ For this particular case, we can make a bound a bit tighter compared to a general case. To determine the bound on the $\text{rank}(A\circ A)$, we need to find the max number of distinct rank-1 matrices, which would follow a simple combinatoric formula choose $n$ from $k$ with repetitions:
$$ \text{rank}(A\circ A)\leq {d+2-1 \choose 2} \leq {d+1 \choose 2}. $$