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.

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

share|improve this question
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

2 Answers 2

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.

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

share|improve this answer

Your Answer


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.