Thanh Minh Hoang and Thomas Thierauf
Abstract:
We investigate the computational complexity of
some important problems in linear algebra.
-
The problem of verifying the characteristic polynomial of a matrix
is known to be in the complexity class C=L
( Exact Counting in Logspace).
We show that it is complete for C=L under logspace many-one reductions.
-
The problem of deciding whether two matrices are similar
is known to be in the complexity class AC0(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.