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

1 Answer 1

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

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.