Let $\varphi_k\in\mathbb{C}$ be a primitive $k$-th root of unity, and define the sets $$S_\ell:=\left\{\left[\begin{matrix}x\\x\varphi_k^\ell\end{matrix}\right]\in\mathbb{C}^{2n}\;\middle|\;x\in\mathbb{R}^n\right\}$$ with $\ell=1,\ldots,k\leq 2n$. Taking randomly (independent and identically random with some continuous distribution) one element $y_\ell\in S_\ell$ from each set, can I conclude that $y_1,\ldots,y_k$ are linear independent with high probability?

Example $n=2, k=3$: $$y_1\in\left\{\left[\begin{matrix}x\\xe^{i\frac{2}{3}\pi}\end{matrix}\right]\;\middle|\;x\in\mathbb{R}^2\right\},\; y_2\in\left\{\left[\begin{matrix}x\\xe^{i\frac{4}{3}\pi}\end{matrix}\right]\;\middle|\;x\in\mathbb{R}^2\right\},\; y_3\in\left\{\left[\begin{matrix}x\\x\end{matrix}\right]\;\middle|\;x\in\mathbb{R}^2\right\}$$

  • $\begingroup$ Do you mean with probability $1$? If you say "with high probability" I expect to see a sequence where the limit of probabilities is $1$. While you could take a limit as $n \to \infty$, don't you mean the stronger statement? $\endgroup$ – Douglas Zare Jan 21 '16 at 14:55
  • $\begingroup$ @DouglasZare Yes, I mean "almost surely". $\endgroup$ – Rob Jan 21 '16 at 16:01

Edit: In response to asker comment, edited significatively the answer as it failed to take into account the case $n<k$

Here is my argument why the probability of linear independence is 1:

Case $k\leq n$:

Notice $y_1,...,y_k$ linearly dependent implies $x_1,...,x_k$ are linearly dependent. So the probability that $y_1,...,y_k$ are linearly dependent is less or equal than the probability that $x_1,...,x_k$ are linearly dependent. In this case, the probability of $x_1,...,x_k$ being linearly dependent is 0.

The proof is similar to one answer to this question. The idea is that, for each $l\leq k$, the probability that $x_l$ is in the same subspace than $x_1,...,x_{l-1}$ is 0.

Case $n<k\leq 2n$:

Let $x_{1},...,x_{k}$ s.t. $y_{1},...,y_{k}$ are linearly dependent. Since the probability that $x_{1},...,x_{n}$ are linearly independent is 1, we can assume w.l.o.g $x_{1},...,x_{n}$ will be linearly independent. Then $x_{1},...,x_{n}$ are a basis of $\mathbb{R}^{n}$. In particular, for $l\in\{n+1,...,k\}$, there are unique $w_{1l},...,w_{nl}$ s.t. $x_{l}=\sum_{i=1}^{n}w_{il}x_{i}$.

Now, since $y_{1},...,y_{k}$ are linearly dependent, there is $ \lambda\in\mathbb{C}^{k}\setminus\{0\}$ s.t. $$ 0=\sum_{i=1}^{k}\lambda_{i}y_{i}=\sum_{i=1}^{k}\lambda_{i}\left(\begin{array}{c} x_{i}\\ \varphi_{k}^{i}x_{i} \end{array}\right) $$

Expanding $$ 0=\sum_{i=1}^{k}\lambda_{i}\left(\begin{array}{c} x_{i}\\ \varphi_{k}^{i}x_{i} \end{array}\right) $$ we get \begin{eqnarray} 0 & = & \sum_{i=1}^{n}\lambda_{i}\left(\begin{array}{c} x_{i}\\ \varphi_{k}^{i}x_{i} \end{array}\right)+\sum_{l=n+1}^{k}\lambda_{l}\left(\begin{array}{c} x_{l}\\ \varphi_{k}^{l}x_{l} \end{array}\right) \\ & = & \sum_{i=1}^{n}\lambda_{i}\left(\begin{array}{c} x_{i}\\ \varphi_{k}^{i}x_{i} \end{array}\right)+\sum_{l=n+1}^{k}\lambda_{l}\left(\begin{array}{c} \sum_{i=1}^n w_{il}x_i\\ \varphi_{k}^{l}\sum_{i=1}^n w_{il}x_i \end{array}\right)\\ & = & \sum_{i=1}^{n}\left(\begin{array}{c} x_{i}\left(\lambda_i+\sum_{l=n+1}^k\lambda_lw_{il}\right)\\ x_{i}\left(\varphi_{k}^i\lambda_i+\sum_{l=n+1}^k\lambda_l\varphi_k^lw_{il}\right) \end{array}\right) \end{eqnarray} Using $x_1,...,x_n$ are linearly independent, we deduce, for all $i\in\{1,...,n\}$, \begin{eqnarray} \lambda_{i}+\sum_{l=n+1}^{k}\lambda_{l}w_{il} & = & 0\\ \lambda_{i}+\sum_{l=n+1}^{k}\lambda_{l}\varphi_{k}^{l-i}w_{il} & = & 0 \end{eqnarray} which implies $\sum_{l=n+1}^{k}w_{il}\lambda_{l}(1-\varphi_{k}^{l-i})=0$ and $(\lambda_{n+1},...,\lambda_{k})\neq0$. In other words, for all $i$, $(w_{in+1},...,w_{ik})$ are linearly dependent, which happens with probability 0.

  • 1
    $\begingroup$ Hi Nate and thanks for your answer. The entries $x_{i,j}\in\mathbb{R}$ belonging to the vector $x_i\in\mathbb{R}^n$ are supposed to be independent and identically random of some continuous distribution. But I think you are missing something: If $k>n$, as in my example, the $k$ different vectors $x_i$ cannot be linear independent, since they are $\in \mathbb{R}^n$. There can only be $n$ linear independent vectors $\in\mathbb{R}^n$ at most, no matter how random they are. $\endgroup$ – Rob Jan 21 '16 at 13:25
  • 1
    $\begingroup$ Yes. I edited the answer to show how I deduced that system of equations. I prefered to edit the answer rather than adding it as a comment as the equations are pretty large and they would look awkward in a coment $\endgroup$ – Nate River Jan 24 '16 at 17:05
  • 1
    $\begingroup$ Thanks! At the end you wanted to say, that it implies, that $(w_{in+1} (1-\varphi_k^{(n+1)-1},\ldots,w_{ik} (1-\varphi_k^{k-1})$ are linearly independent, right? Since $i$ also appears in the power or $\varphi_k$. Furthermore I am not really sure if you can that they are almost surely not linearly dependent, because $w_{il}$ and $\lambda_l$ are not independent. The $w_{il}$ are defined by the $x_i$ and so do the $\lambda_l$, too. Or can you? $\endgroup$ – Rob Jan 25 '16 at 16:07
  • 1
    $\begingroup$ Yes, very bad choice of words from my part, sorry!. What I should have said was this: For each $i\leq n$, let $H_i:=(\lambda_{n+1}(1-\varphi_k^{n+1-i}),...,\lambda_k(1-\varphi_k^{k-i}))^{ \perp }$. Since $(\lambda_{n+1},...,\lambda_k)\neq 0$, $H_i$ is a subspace of $\Bbb C^k$ of dimension less or equal than $k-1$. We also know $\sum_{l=n+1}^{k}w_{il}\lambda_{l}(1-\varphi_{k}^{l-i})=0$. This implies, for each $i$, the vector $(w_{in+1},...,w_{ik})\in H_i$. This happens with probability 0. $\endgroup$ – Nate River Jan 25 '16 at 18:58
  • 1
    $\begingroup$ Now you mean that $H_i$ is a subspace of $\mathbb{C}^{k-n}$ of dimension $\leq k-n-1$, right? And since $w_i=(w_{i,m+1},\ldots,w_{i,k})\in\mathbb{C}^{k-n}$ and $w_i\in H_i\subseteq\mathbb{C}^{k-n-1}$, at least one component of each $w_i$ must be $0$. And this has probability $0$, right? If yes, I'm with you! $\endgroup$ – Rob Jan 26 '16 at 13:40

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.