0
$\begingroup$

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

$\endgroup$
2
  • $\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$ Jan 21, 2016 at 14:55
  • $\begingroup$ @DouglasZare Yes, I mean "almost surely". $\endgroup$
    – Rob
    Jan 21, 2016 at 16:01

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
12
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 13:40

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.