Consider a matrix $\mathrm{X}$ sampled uniformly at random from the set of all rank $r$ matrices over $\mathbb{F}_q^{m \times n}$ and a matrix $\mathrm{Y}$ sampled uniformly at random from the set of all full rank matrices over $\mathbb{F}_q^{n \times n}$. Let $\mathrm{Z} = \mathrm{X}\mathrm{Y}$.
I am trying to prove something like the statement that $\mathrm{Z}$ is uniform over the set of all rank $r$ matrices over $\mathbb{F}_q^{m \times n}$.
Assume $m > n$ and $r \leq n$.
This old stackexchange answer says that this is indeed the case, but it does not explain how to reach the result. Is this a common result in random matrix theory, and if so, can someone provide a reference or a proof?
Best Answer
The claim is relatively well-known and even true for the more general case, where $P(Y \text{ is invertible}) = 1$, i.e., $Y$ does not have to be uniform. We assume that $X$ and $Y$ are independent and $P(X=x)=p$ uniformly over all matrices $x$ of rank $r$.
A proof goes as follows. Let $z \in \mathbb{F}_q^{m\times n}$ be a matrix of rank $r$. Start with demarginalization to obtain $$ P(Z=z)=\sum_{y} P(Y=y,Z=z) = \sum_{y} P(Z=z|Y=y)P(Y=y), $$ where the sum ranges over all invertible matrices $y$. Now, since $y$ is invertible, $z=xy$ if and only if $x=zy^{-1}$ and hence $P(Z=z|Y=y) = P(X=zy^{-1}|Y=y)$. Due to independence of $X$ and $Y$ we get $P(X=zy^{-1}|Y=y)=P(X=zy^{-1})=p$, as $zy^{-1}$ is a matrix of rank $r$. Consequently, $$ P(Z=z) = \sum_{y} p P(Y=y) =p\sum_{y} P(Y=y) = p, $$ which proves the claim.