Testing Simultaneous Similarity of Matrices and Related Problems for Matrix Semigroups
Zalcstein, Yechezkel (Zeke)
MetadataShow full item record
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.