Testing Simultaneous Similarity of Matrices and Related Problems for Matrix Semigroups

Abstract

This paper studies the problem of testing simultaneous similarity of matrics and related problems about matrix semigroups. Along with SIMULTANEOUS SIMILARITY this paper studies two problems: NONSINGULAR NULLSPACE and Nonsingular BASIS COMBINATION. These two problems are very similary to SIMULTANEOUS SIMILARITY and SIMULTANEOUS SIMILARITY is reducible to each of these two.

This paper also studies problems about matrix semigroups. Among other results, it shows that (i) for any field MATRIX SEMIGROUP INTERSECTION is PSPAGE-complete, (ii) for any finite field MATRIX SEMIGROUP MEMBERSH, MATRIX SEMIGROUP EQUALITY, and MATRIX SEMIGROUP ISOMORPHISM are all PSPACE-comple, (iii) for each inverse matrix semigroup over a field of characteristics zero, MATRIX SEMIGROUP MEMBERSHIP is PSPACE-complete, and (iv) for any field, MATRIX APERIODICITY for inverse semigroups is PSPACE-complete.