Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Not orthogonal? Take $v_1$. –  Git Gud Feb 10 '13 at 22:09
1  
Why is $v_1$ not orthogonal to any of the other vectors? –  user61799 Feb 10 '13 at 22:11
2  
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
1  
"orthogonal" or "not orthogonal"? The title is wrong? –  leonbloy Feb 10 '13 at 22:36

5 Answers 5

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
$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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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