Let $d$, $n$ and $m$ be large positive integers with $m$ and $n$ much larger than $d$. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. For example, one could think of $P = N(0,\Sigma)$. Form a random $m \times d$ matrix $Z$ as follows.
For $k$ from $1$ through $m$, do the following
- Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
- Independently of anything else, sample $u$ from $U([0, 1])$.
- Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.
Let $G := Z^\top Z$.
Question. Is true that $G$ is invertible with high-probability ?
My intuition is that, since the rows of $Z$ admit a density (?!) and are distinct almost-surely, the probability that a row of $Z$ is contained in the span of other rows is zero. Thus, almost surely, $Z$ has full rank $\min(m,d) = d$, implying that $G$ is invertible a.s.