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 independent random variables 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 ?

Relate: Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries