The complexity of verifying the characteristic polynomial and testing similarity
Thanh Minh Hoang, Thomas Thierauf · 2002
We investigate the computational complexity of some important problems in linear algebra. 1. The problem of verifying the characteristic polynomial of a matrix is known to be in the complexity class C/sub =/L (Exact Counting in Logspace). We show that it is complete for C/sub =/L under logspace many-one reductions. 2. The problem of deciding whether two matrices are similar is known to be in the complexity class AC/sup 0/(C=L). We show that it is complete for this class under logspace many-one reductions. We also consider the problems of deciding equivalence and congruence of matrices.