The complexity of the characteristic and the minimal polynomial

✍ Scribed by Thanh Minh Hoang; Thomas Thierauf

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 188 KB
• Volume: 295
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00404-8

✦ Synopsis

We investigate the complexity of (1) computing the characteristic polynomial, the minimal polynomial, and all the invariant factors of an integer matrix, and of (2) verifying them, when the coe cients are given as input.

It is known that each coe cient of the characteristic polynomial of a matrix A is computable in GapL, and the constant term, the determinant of A, is complete for GapL. We show that the veriÿcation of the characteristic polynomial is complete for complexity class C=L (exact counting logspace).

We show that each coe cient of the minimal polynomial of a matrix A can be computed in AC 0 (GapL), the AC 0 -closure of GapL, and there is a coe cient which is hard for GapL. Furthermore, the veriÿcation of the minimal polynomial is in AC 0 (C=L) and is hard for C=L. The hardness result extends to (computing and verifying) the system of all invariant factors of a matrix.