# Given $n$-linearly independent vectors how do I find a vector not orthogonal to any of them?

I'm trying to do this as part of another proof:

Let $v_1, \ldots, v_k \in \mathbb{R}^{n}$ be linearly independent vectors. How do I find a vector that's not orthogonal to any of these?

Edit: the proof doesn't necessarily have to be constructive. I just need to know that such a vector exists.

Edit 2: I just realized that linear independence doesn't need to hold. Then $k$ is allowed to be greater than $n$.

-
Not orthogonal? Take $v_1$. – Git Gud Feb 10 '13 at 22:09
Why is $v_1$ not orthogonal to any of the other vectors? – user61799 Feb 10 '13 at 22:11
Since the vectors are linearly independent, $\|v_1\|>0$. Then $v_1\cdot v_1 = \|v_1\|^2 > 0$, hence $v_1$ is not orthogonal to itself. – user7530 Feb 10 '13 at 22:12
@GitGud $(1,0),(0,1)$. However, the statement $(1,0)$ is not orthogonal to both vectors is false. – Amr Feb 10 '13 at 22:14
"orthogonal" or "not orthogonal"? The title is wrong? – leonbloy Feb 10 '13 at 22:36

Let $V=[v_1,\ldots,v_k]$ (so that $V$ is $n\times k$) and $\mathbf{1}$ be the $k$-vector with all entries equal to $1$. Since the rank of $V$ is $k$, the equation $V^Tx=\mathbf{1}$ has a solution, and this $x$ is not orthogonal to any column of $V$.

-
Actually, there is no need to assume $k<n$. – 1015 Feb 10 '13 at 23:40
Ha ha, you're right. Although the OP asks for a vector that is not orthogonal to every $v_i$, subconsciously I was still thinking about a vector that is orthogonal to every $v_i$. – user1551 Feb 11 '13 at 10:06

I will be using Dirac notation to address the question.

Consider a set of linearly independent vectors $$V=\{|v_i\rangle : i \in \{1,\ldots,k\}\}$$ and a linear combination thereof given by $$|u\rangle=\sum_{i=1}^k a_i |v_i\rangle,$$ where $a_i$ are expansion coefficients.

For $|u\rangle$ to have a non-zero projection onto any of the vectors in $V$ we require \begin{align} \langle v_j|u\rangle&=\sum_{i=1}^k \langle v_j| v_i\rangle a_i\\ &\neq 0. \end{align}

The above is a set of $k$ inequalities with $k$ unknowns, which can be solved in principle. A vector of the desired form exists.

-

Let $V_1, \dots, V_k$ be the one-dimensional subspaces spanned by $v_1, \dots, v_k$ respectively. Then what you're asking is equivalent to: prove that $\mathbb{R}^n$ is not equal to $V_1 ^{\perp} \cup \dots \cup V_k ^{\perp}$, where $V_i ^{\perp}$ denotes the orthogonal complement subspace to $V_i$. This follows from the fact that this union can't be a subspace since the vectors are distinct.

-

Let $A$ be the $n\times k$ matrix whose columns are the vectors $v_1,\ldots,v_k$. By assumption, it has rank $k$. So $A^t$ has rank $k$ and is $k\times n$. Equivalently, it is surjective, and admits a right $n\times k$ inverse, say $A^tB=I_k$.

Now pick your favorite vector $b$ with nonzero coefficients, say $b=(1,\ldots,1)$, in $\mathbb{R}^k$. We want to solve for $v\in\mathbb{R}^n$ such that $$A^tv=b.$$ This is a linear system. The solution set is $Bb+\ker A^t$.

Any such $v$ answers your problem, since the coordinates of $A^tv$ are precisely the inner products $(v_j,v)$.

-
$v$ is an $n$-vector and $b$ is a $k$-vector. It would seem that $Bb$ is also a $k$-vector, not an $n$-vector. – robjohn Jun 1 '13 at 12:40
@robjohn So moderators can comment on deleted answers? You're almighty! There were two typos: $B$ is $n\times k$, and it is a right inverse. – 1015 Jun 1 '13 at 12:54

Once you drop (in Edit 2) the assumption of linear independence, the nasty possibility arises that some $v_i$ is the zero vector, in which case (according to the usual convention) every vector is orthogonal to it. So let's assume none of the $v_i$'s are zero.

Then one way to get a vector not orthogonal to any of them is to pick a vector $w$ at random. To make "at random" precise, pick the $n$ components of $w$ independently, uniformly from $[0,1]$. So $w$ is a random point in the unit cube $[0,1]^n$ of $\mathbb R^n$. The vectors in this cube that are orthogonal to any $v_i$ constitute an $(n-1)$-dimensional hyperplane section of the cube, so the set of such "undesirable" vectors has measure zero. Therefore, the set of "good" $w$'s, those not orthogonal to any $v_i$ has measure $1$. A randomly chosen $w$ will, with probability $1$, do what you wanted.

-