DocumentCode :
3379392
Title :
The complexity of the inertia and some closure properties of GapL
Author :
Hoang, Thanh Minh ; Thierauf, Thomas
Author_Institution :
Abteilung Theor. Informatik, Univ. Ulm, Germany
fYear :
2005
fDate :
11-15 June 2005
Firstpage :
28
Lastpage :
37
Abstract :
The inertia of an n × n matrix A is defined as the triple (i+ (A), i_(A), i0(A)), where i+(A), i_(A), and i0(A) are the number of eigenvalues of A, counting multiplicities, with positive, negative, and zero real part. It is known that the inertia of a large class of matrices can be determined in PL (probabilistic logspace). However, the general problem, whether the inertia of an arbitrary integer matrix is computable in PL, was an open question. In this paper we give a positive answer to this question and show that the problem is complete for PL. As consequences of this result we show necessary and sufficient conditions that certain algebraic functions like the rank or the inertia of an integer matrix can be computed in GapL.
Keywords :
computability; computational complexity; eigenvalues and eigenfunctions; matrix algebra; GapL; algebraic functions; arbitrary integer matrix; closure property; computability; computational complexity; eigenvalues; inertia; matrix algebra; probabilistic logspace; Computational complexity; Control theory; Eigenvalues and eigenfunctions; Linear algebra; Linear matrix inequalities; Polynomials; Robots; Sufficient conditions; Symmetric matrices; Testing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
ISSN :
1093-0159
Print_ISBN :
0-7695-2364-1
Type :
conf
DOI :
10.1109/CCC.2005.28
Filename :
1443071
Link To Document :
بازگشت