On the invertibility of $Z^\top Z$, where $Z$ is a Random matrix with concentrated weakly correlated entries

Question

Let $d$, $n$, and $m$ be large positive integers. 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 $\{i,j\}$ of distinct indices uniformly from ${n \choose 2}$, the collection of two-element subsets of $\{1,\ldots,2\}$
• Independently of anything else, sample $u$ from $U([0, 1])$.
• Set the $k$th row of $Z$ to $ux_i + (1-u)x_j$.

Question. Is true that if $n$ is sufficiently larger than $d$, then $Z$ has full rank $\min(m,d)$ 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)$.

---

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

Answer 1

At step $k$, we pick two indies $i\ne j\in [n]$ (say, wlog, $i$ is picked first, then $j$) and the probability that $i$ has been picked before at least once at steps $1,...,k-1$ is at most $$ \frac{2(k-1)}{n}. $$ By the union bound, at each step, both $x_i$ and $x_j$ have never been picked before with probability at least $$ 1- O(m^2/n) $$ which converges to $1$ if $m^2 = o(n)$.

Conditionally on the uniform $u$ and on the choice of the pairs $\{i,j\}$ at each step, the quantity $$ \det(Z^TZ) $$ is a polynomial in the entries of $X$. Since $X$ admits a density with respect to the Lebesgue measure in $R^{n\times d}$, either this is the zero polynomial, or $P(\det(Z^TZ)\ne 0)=1$ thanks to https://math.stackexchange.com/questions/1920302/the-lebesgue-measure-of-zero-set-of-a-polynomial-function-is-zero.

It remains to prove that it is not the zero polynomial. If $m\ge d$, this follows by taking $x_{ik}=x_{jk}=1$ (for $x_i,x_j$ the rows sampled at step $k$) and $x_{il}=x_{jl}=0$ for all $l\ne k$. Then for this choice of $X$, $Z^TZ=I_d$ and $\det(Z^TZ)=1$ so it cannot be the zero polynomial.