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 manyone reductions.

The problem of deciding whether two matrices are similar
is known to be in the complexity class AC^{0}(C=L).
We show that it is complete for this class under logspace manyone reductions.
We also consider the problems of deciding equivalence
and congruence of matrices.