4
$\begingroup$

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\}$$

$\endgroup$
  • $\begingroup$ It suffices to find one choice of a_i such that S_m is linearly independent, right? $\endgroup$ – David Cohen Jan 18 '16 at 19:32
  • $\begingroup$ "Every choice of m vectors from $ {a_1 …,a_{2m} } $ is linearly independent with high probability" ... are they not linearly independent with probability 1 under the hypotheses ? $\endgroup$ – user83457 Jan 19 '16 at 12:53
  • $\begingroup$ @DavidCohen No, there is definitely a choice of $a_1,\ldots,a_{2m}$ for which they are linear dependent, e.g. choosing $a_1=a_2=a_3=a_4$. That's why they are supposed to be chosen random. $\endgroup$ – Rob Jan 19 '16 at 14:50
  • $\begingroup$ @michael Yes, you can even say this. But "with high probability" is enough for me, which is not a defined expression anyway. I consider it as "the probability is at least close to 1". $\endgroup$ – Rob Jan 19 '16 at 14:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But submanifold may have full measure w.r.t. some continuous distribution (I guess, it does not mean "absolutely continuous", but only "atomless") $\endgroup$ – Fedor Petrov Jan 18 '16 at 23:48
  • $\begingroup$ @Fedor, I guess "absolutely continuous" is what OP meant (otherwise they clearly may be linearly dependent a. s.) $\endgroup$ – Kostya_I Jan 19 '16 at 6:00
  • $\begingroup$ No, there is condition "any m are linearly independent with high probability" $\endgroup$ – Fedor Petrov Jan 19 '16 at 6:26
  • $\begingroup$ OK, I see. I did't think it was part of the condition. $\endgroup$ – Kostya_I Jan 19 '16 at 6:37
  • $\begingroup$ Actually, I didn't consider that as part of the condition. It is just meant as a fact which can be followed from the conditions in the sentence before. I just want to prove a similar thing like this for my set. btw... Thanks, I'm currently trying to understand your proof... please wait. ;-) $\endgroup$ – Rob Jan 19 '16 at 14:46
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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