3
$\begingroup$

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

  • 0
    What do you call an $integer$ matrix ?2016-10-21

3 Answers 3

0

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.

  • 2
    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.2015-08-05
0

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.

-3

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!)

  • 0
    I think the downvotes are because this is analogous to answering "how do I check if a matrix is positive definite?" with "the probability tends to zero for large matrices, so don't worry about it". But these are not random matrices, and of course in practice one does very often encounter large positive definite matrices.2017-12-04