Testing Simultaneous Similarity of Matrices and Related Problems for Matrix Semigroups

View/ Open
Date
2002Author
Ogihara, Mitsunori
Zalcstein, Yechezkel (Zeke)
Metadata
Show full item recordAbstract
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.