Find a vector NOT perpendicular to a given set of vectors

Question

Let us suppose to have a finite set of vectors $S=\{v_1,\ldots,v_m\}$ in $\mathbb{R}^n$ (with $m \gg n$ in general). I need to find a vector $x \in \mathbb{R}^n$ that is NOT perpendicular to any vector in $S$. The existence of such a vector $x$ is guaranteed, moreover almost every vector in $\mathbb{R}^n$ satisfies this property. But I need to find an algorithm to determine a vector with these properties, I cannot close my eyes and choose.

Any ideas?

EDIT1: in my case, the vectors in $S$ have some "symmetries" in the sense that they are generated by permutation and change of signs of a few vectors in $S$

EDIT2: $v_1+\ldots+v_m=0 \in \mathbb{R}^n$

EDIT3: I simplified the solution proposed by Tom Collinge. We define a sequence $\{x_i\}_{i=1}^m$ such that $x_m=x$ is what we are looking for. First define $x_1=v_1$, so $x_1 \cdot v_1 \ne 0$ and they are not perpendicular (obviously). Then, recursively, define for $k \in \{2,\ldots,m\}$ $$ x_k=\begin{cases} x_{k-1}+2v_k & \text{if }x_{k-1}=-v_k\\ x_{k-1}+v_k & \text{otherwise} \end{cases}. $$ By construction we have that $x_k \cdot v_i \ne 0$ for $i \le k$, then $x_m \cdot v_i \ne 0$ for all $v_i \in S$, so $x=x_m$ is not perpendicular to every element in $S$. Can it works?

EDIT4: As pointed out, the algorithm proposed in EDIT3 does not work

Answer 1

Here is an algorithm that will work, although it might not work well in practice (because it might involve very large numbers). Reorder your vectors so that $v_2, \ldots, v_k$ are the vectors orthogonal to $v_1$, and $v_{k+1}, \ldots, v_m$ are not orthogonal to $v_1$. Recursively solve the problem for the vectors $v_2, \ldots, v_k$, so that you get a vector $y$ which is not orthogonal to any of $v_2, \ldots, v_k$. (If $k = 1$, i.e. there are no vectors in the set orthogonal to $v_1$, you can take any non-zero vector.)

Now define $$ \alpha = \max\left\{\left|\frac{\langle y, v_i\rangle}{\langle v_1, v_i\rangle}\right| \mid i \in \{k+1, \ldots, m\}\right\} + 1. $$ Then set $x = \alpha v_1 + y$. For $i \in \{2, \ldots, k\}$ we have $$ \langle x, v_i\rangle = \langle \alpha v_1 + y, v_i\rangle = \langle y, v_i\rangle \neq 0 $$ by definition of $y$. For $i \in \{k+1, \ldots, m\}$ we have $$ \langle x, v_i\rangle = \alpha\langle v_1, v_i\rangle + \langle y, v_i\rangle. $$ Now if this were to equal zero, we would have $$ \alpha = \frac{-\langle y, v_i\rangle}{\langle v_1, v_i\rangle} $$ which contradicts the definition of $\alpha$. Therefore $x$ is a vector which is not orthogonal to any element of the original set.

Answer 2

If you can implement on a computer, perhaps the following would work.

Create an $m \times n$ matrix $A$, the rows of which contain your vectors. Now pick a random uniform vector $b > \vec{0} \in \mathbb{R}^m$, for example by generating the entrees of $\vec{b}$ uniformly, and solve $A \vec{x} = \vec{b}$.

If any solution is found, you are done. If not, re-generate $\vec{b}$ and do it again.

If your assertion that practically every vector in $\mathbb{R}^n$ will do is correct, you will get a viable answer in a very small amount of tries.

Answer 3

You probably want to have non orthogonal vectors to get out of numerical problems with dividing numbers by zero, right?

If that is the case, try to maximize that value instead! So solve the problem $$b_{opt}=\max_{b}\left(\min_i(v_i^Tb)\right)$$

This should have a nice solution that you can always work with.

Answer 4

I don't think it matters whether $m > n$ or not, and clearly we assume that $s_i \ne 0$ for any $i$

Define a sequence of vectors $(x_j)_ {j = 1}^m$ and constants $(\alpha_i)_{i = 1}^m$ as follows and then $x = x_m$ satisfies your requirement.

$\alpha_1 = 1; x_1 = \alpha_1 s_1$ and so $x_1$ is not orthogonal to $s_1$.

Given $k < m$ and $x_k = \sum_{i = 1}^k \alpha_i s_i$ and $x_k$ not orthogonal to any $\{s_i\}_{i = 1, k}$
Then for $i = 1, k + 1$ let $c_i = x_k \cdot s_i$ so that by non-orthogonality $c_i \ne 0$ for $i = 1, k$.
If $c_{k+1} \ne 0 $ then put $\alpha_{k+1} = 0 \implies x_{k+1} = x_k$ and $x_{k+1}$ is not orthogonal to $\{s_i\}_{i = 1}^{k+1}$

Otherwise, chose $\alpha_{k+1} \ne 0$ and such that $\alpha_{k+1} s_{k+1} \cdot s_i \ne - c_i$ for $i = 1, k$
(which can be done even if $s_{k+1}\cdot s_i = 0$, since $c_i \ne 0$ for $i = 1, k$).
Then for $i = 1, k$,
$$ \begin{split} x_{k+1} \cdot s_i &= (x_k \cdot s_i) + \alpha_{k+1}(s_{k+1} \cdot s_i) \\ &= c_i + \alpha_{k+1}(s_{k+1}.s_i) \\ &\ne 0 \end{split} $$

And for $i = k+1$,
$$ \begin{split} x_{k+1} \cdot s_i &= (x_k \cdot s_i) + \alpha_{k+1}(s_{k+1} \cdot s_i) \\ &= (x_k \cdot s_{k+1}) + \alpha_{k+1}(s_{k+1} \cdot s_{k+1}) \\ &= 0 + \alpha_{k+1}(s_{k+1} \cdot s_{k+1}) \\ &\ne 0 \end{split} $$ So, $x_{k+1}$ is not orthogonal to $\{s_i\}_{i = 1, k+1}$