Complexity results for some eigenvector problems

DOI10.1080/00207160008805009MaRDI QIDQ4521209zbMATH OpenOpenAlexFDO

Authors Thomas Eiter, Georg Gottlob

Publication date 21 August 2001

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160008805009

zbMATH Keywords

combinatorial optimizationeigenvectorsinteger eigenvalue problemsinteger programmingproblem complexity

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

The paper addresses a set of complexity problems that may be formulated in connection with the integer solution of integer eigenvalue problems. The paper's aims can be illustrated with an example of its contents: Given an \(n\times n\) matrix \(M\), an integer eigenvalue \(\lambda\) of \(M\), a real number \(K\), and an integer bound \(b\geq 1\), does there exist a non-zero eigenvector \(x\), with coordinates whose modules are bounded by \(b\), and whose Euclidean norm is smaller than \(K\)? The answer is that the problem is NP-complete, i.e. it cannot be solved by a deterministic Turing machine in polynomial time.

Recommendations

• Permuted max-algebraic eigenvector problem is \(NP\)-complete
• The complexity of the matrix eigenproblem
• Computing a common eigenvector of two matrices in a finite number of arithmetic operations
• Complexity issues for the symmetric interval eigenvalue problem
• On ±1 eigenvectors of graphs

Cites work

• Bounded Query Classes
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3917549 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the randomized error of polynomial methods for eigenvector and eigenvalue estimates
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• The complexity of optimization problems
• The complexity of selecting maximal solutions

Cited in

(7)

• Generalizations of matched CNF formulas
• On the computation of all eigenvalues for the eigenvalue complementarity problem
• Permuted max-algebraic eigenvector problem is \(NP\)-complete
• scientific article; zbMATH DE number 5864487 (Why is no real title available?)
• Composites with invisible inclusions: Eigenvalues of ℝ-linear problem
• scientific article; zbMATH DE number 7365978 (Why is no real title available?)
• On the quality of complementary bounds for eigenvalues

This page was built for publication: Complexity results for some eigenvector problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4521209)