# Are $\left[\begin{matrix}x_\ell \\ x_\ell\varphi_k^\ell\end{matrix}\right]$ linearly independent?

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

• 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? Jan 21 '16 at 14:55
• @DouglasZare Yes, I mean "almost surely".
– 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.

• 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.
– Rob
Jan 21 '16 at 13:25
• 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 Jan 24 '16 at 17:05
• 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?
– Rob
Jan 25 '16 at 16:07
• 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. Jan 25 '16 at 18:58
• 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!
– Rob
Jan 26 '16 at 13:40