I am having some problems on understanding an inequality regarding the rank of the Hadamard product (element-wise product). I have $B=A\circ A$ where $A$ is a $n\times r$ matrix, and $\circ$ is the Hadamard product, so $B$ must also be a $n\times r$ matrix, so, according to my intuition, $rank(B)\le \min (n,r)$, but I have read that the actual upper bound for the rank is as follows: $rank(B)\le {d+1 \choose 2} $, where $d$ is the rank of $A$, but I am confused since the value of ${d+1 \choose 2} $ is greater than $d$ so it means that the Hadamard product is increasing the rank of the original matrix $A$, but this sounds weird for me since we are not increasing the amount of rows and columns, so the upper bound for $B$ must be the same as for $A$. Thanks for any explanation about this.
Hadamard (element-wise multiplication) product rank
hadamard-productlinear algebra
Best Answer
The value $\binom{d+1}{2}$ is only greater than the maximal possible rank of $B$ if $A$ has sufficiently high rank. Not every $m\ \times r$ matrix has the maximal possible rank of $\min\{m,r\}$.
The point of the inequality is that if $A$ has a small enough rank so that $\binom{d+1}{2} < \min\{n,r\}$, then $\operatorname{rank}(B) \leq \binom{d+1}2$ gives us a non-trivial upper bound. In the case that $\binom{d+1}{2} \geq \min\{n,r\}$, this inequality doesn't give us any information about the rank of $B$ because, as you noted, we already know that $\operatorname{rank}(B) \leq \min\{m,r\}$.