# Determine direction of eigenvector

Suppose that $A \in \mathbb{R}^{n \times n}$ and $B \in \mathbb{R}^{n \times m}$ are integer matrices. Let $P$ be the unbounded polytope in $\mathbb{R}^n$ given by $$B \cdot x \geq 0$$

As there is no explicit formula for the roots of high degree polynomials we cannot explictily compute the eigenvalues or eigenvectors of $A$ however:

Is there an algorithm to determine if there is an eigenvector of $A$ lying inside of $P$?

-
What does $\ge0$ mean in ${\bf R}^n$? – Gerry Myerson Dec 8 '12 at 21:40
A vector $v$ is non-negative if each entry of $v$ is non-negative, this is written $v \geq 0$. – Mark Bell Dec 8 '12 at 21:47

This is probably not what you need, but an obvious way to solve the problem is to find all eigenvectors of $A$, and then test if there is an eigenvector $v$ such that $Bv\ge0$ or $Bv\le0$. If the eigenspace spanned by $v$ does not pass through the polytope, some two entries of $Bv$ must have different signs.

-
But computing the eigenvectors of $A$ requires finding the roots of the characteristic polynomial, and there is no closed expression for the roots of high degree polynomials. – Mark Bell Dec 8 '12 at 21:52
Yes, that's why I said this is probably not what you want :-D Meanwhile, I'm a bit confused by your comment. You asked for an "algorithm". So I take that as a computer algorithm. However, if you'll end up using a computer to solve the problem, does it matter if there is no general formula for solving, say, a quintic equation? – user1551 Dec 8 '12 at 22:08
I should point out here, that no serious algorithms (except for 2x2 matrices maybe) compute the roots of the characteristic polynomial. Serious algorithms for solving the eigenvalue problem operate in completely different ways (direct transformation of matrices) and work reliably for matrix sizes of thousands. Still one of the more expensive algorithms in terms of time, but it shouldn't be a serious problem. – orion Aug 5 '15 at 6:54

I don't think the eigenvalue problem can be combined with the linear inequality condition in an obvious way. This looks to me like a combination of integer linear programming and eigenvalue problem, and the easiest way is probably just to solve the eigenvalue problem numerically and then test the inequality. If you want an analytical solution, I believe there isn't much hope for matrices of higher dimensions.

Another thing... an eigenvector is still an eigenvector if you multiply it by $-1$, so you have to check both. And if you have degeneracy of two eigenvectors... then you have to check all superpositions (intersection of your polytope with a plane/hyperplane).

I also notice that you have integer matrices... while this is very cute for the inequality part, the eigenvalues will most likely be irrational, so this additional condition won't help at all.

-

Assume that $A,B$ are generic square matrices. Then $A$ has essentially at most $n$ REAL eigenvectors $\pm (v_i)$ that are subjects to $n$ linear independent inequalities. The probability that at least one of the previous vectors is convenient is $\leq p_n=\dfrac{n}{2^{n-1}}$ When $n\geq 90$, $p_n\leq 2^{-80}$, that is to say that the event above NEVER occurs !! For example, a cryptographic system is assumed to be reliable when the probability of breaking it, is less than $2^{-80}$.

Conclusion. When $n\geq 90$, you're wasting your time -except if you know in advance that your matrix $A$ has a very special form-. When $n\leq 90$, consider the user1551 's method (less than one second!)

-
One more time, a "courageous" people (and probably incompetent) downvoted my answer without leaving his name and some explanation! – loup blanc Jun 13 at 9:08