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

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)$$.

• If $i$ or $j$ was sampled at step $k$, can they be sampled again at step $k+1$? My current answer may have misinterpreted "without replacement". Commented Jul 8, 2022 at 19:57
• @Thanks for the input. Yes, it can be sampled again. What i meant by "w/o replacement" is that i and j are distinct. I've made this clearer now; see edit. Commented Jul 8, 2022 at 20:09

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.
• Thanks for the input and sorry for the confusion. I meant to say each $\{i,j\}$ is sampled uniformly from the set of two-element subsets of $\{1,\ldots,n\}$ (note that there are ${k \choose 2}$ such subsets). Commented Jul 8, 2022 at 20:12
• I fixed the answer. $m^2=o(n)$ is sufficient. Commented Jul 9, 2022 at 0:45
• Also the fact that the condition is Independent of d is weird. Cant the first probability bound be made $1 - O(\min(m,d)^2/n)$, for example ? Commented Jul 9, 2022 at 12:02