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

  • $\begingroup$ 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". $\endgroup$
    – jlewk
    Commented Jul 8, 2022 at 19:57
  • $\begingroup$ @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. $\endgroup$
    – dohmatob
    Commented Jul 8, 2022 at 20:09

1 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.

  • $\begingroup$ 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). $\endgroup$
    – dohmatob
    Commented Jul 8, 2022 at 20:12
  • $\begingroup$ I fixed the answer. $m^2=o(n)$ is sufficient. $\endgroup$
    – jlewk
    Commented Jul 9, 2022 at 0:45
  • $\begingroup$ Thanks for the update. I was hoping for something like m = O(n) at worst. m = n^2 seems vert extrême... $\endgroup$
    – dohmatob
    Commented Jul 9, 2022 at 5:46
  • $\begingroup$ 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 ? $\endgroup$
    – dohmatob
    Commented Jul 9, 2022 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.