Why are the vectors with this special structure linearly independent with high probability?

Question

Given $a_i\in\mathbb{R}^m$ for $i=1,\ldots,2m$ with independent and identically random entries of some continuous distribution. Every choice of $m$ vectors from $\{a_1\ldots,a_{2m}\}$ is linearly independent with high probability.

How can I prove the linear independence with high probability of the vectors in the set

$$S_m:=\left\{\left[\begin{matrix}a_1\\a_{2m}\end{matrix}\right]\in\mathbb{R}^{2m}\right\}\cup\left\{\left[\begin{matrix}a_i\\a_{i-1}\end{matrix}\right]\in\mathbb{R}^{2m}\;\middle|\;i=2,\ldots,2m\right\}\text{ ?}$$ What can I use as argument here? Or is it just too obvious and you think it is not necessary to prove anything?

In order to understand the structure quickly, here a small example of the set for $m=2$: $$S_2=\left\{\left[\begin{matrix}a_1\\a_4\end{matrix}\right],\left[\begin{matrix}a_2\\a_1\end{matrix}\right],\left[\begin{matrix}a_3\\a_2\end{matrix}\right],\left[\begin{matrix}a_4\\a_3\end{matrix}\right]\right\}$$

Answer 1

Consider the set $\Lambda$ of all $2m$-tuples $p=(p_1,\dots,p_{2m})$ of real numbers such that $\sum p_ia_i=0$. Let us call a 2m-tuple $(a_1,\dots,a_{2m})$ "bad" if there is a nonzero $p\in \Lambda$ such that $S(p)\in \Lambda$, where $S$ is the operator which cyclically shifts the coordinates. Let us prove that almost all $2m$-tuples are good. If $p\in\Lambda$ and $S(p)\in\Lambda$, then $\Lambda$ contains the subspace $\langle p,S(p)\rangle$ spanned by $p$ and $S(p)$, either two-dimensional or one-dimensional. The set of 2D subspaces of this form is a $(2m-1)$-dimensional smooth manifold (parametrized, e. g., by the unit sphere minus the eigenvectors with eigenvalues $\pm 1$). The set of all $2m$-tuples $(a_1,\ldots,a_{2m})$ such that the corresponding $\Lambda$ contains a given 2D subspace has dimension $(2m-2)m$, and depends smoothly on the subspace. Hence, the set of all "bad" $2m$-tuples corresponding to a two-dimensional $\langle p,S(p)\rangle$ is contained in a $(2m^2-1)$-dimensional smooth manifold. The case of one-dimensional $\langle p,S(p)\rangle$ also gives a finite union of lower-dimensional subspaces.

Answer 2

First, under the hypotheses the vectors are linearly independent with probability 1. By induction, and it suffices to show that $a_1,...,a_m$ are linearly independent with prob 1 as the general case is a finite union of cases like that.

The matrix whose ith column is $a_i$ consists if i.i.d. entries with a continuous distribution. They are linearly independent if the determinant of the matrix is non 0. Separating out the $a_{11}$ (= first element of $a_1$) term, the determinant is of the form $a_{11}f($(other $a_{ij})$ + $g($other $a_{ij})$. f is the determinant that occurs in a problem one dimension smaller, and is therefore non zero almost surely by the induction hypothesis. Calculate the probability that this is 0 by conditioning on the other $a_{ij}$. By continuity of the distribution, this probability is 0.

For the proposer's problem, do the same, Now the determinant is a quadratic in $a_{11}$as it occurs twice in the relevant matrix. Now it must be shown that the quadratic is not 0. When that is seen to be a non zero quadratic it follows as above that $a_{11}$ satisifies it with probability 0, as it is equal to either of its roots with probability 0 by continuity.

The coefficient of the quadratic term is not the determinant of an identical problem only in a smaller dimension, as above, but it has these features:

$a_{22}, ..., a_{2n}$ occur only once, and the determinant is a linear function of them. There are no cross terms because they are in the same row.

If you substitute $a_{n2}, ..., a_{nn}$ for $a_{22}, ..., a_{2n}$ you get the matrix from an identical problem one dimension smaller, which by the induction hypothesis is almost surely non 0.

It follows that the determinant is if the form $\lambda_2 a_{22}+ ... \lambda_n a_{2n} + \lambda$ where the $\lambda_i$ do not depend on $a_{2i}$ and not all $\lambda_i$ are 0 with probability 1, because if they were, you would get 0 when you plugged in $a_{n2}, ..., a_{nn}$, which is the determinant which is non 0 by the induction hypothesis. The result follows from :

If $X_i$ are independent with continuous distributions and $\lambda_i$ are constants not all 0 the $P ( \lambda_0 + \sum \lambda_i X_i ) = 0$ .