Testing Simultaneous Similarity of Matrices and Related Problems for Matrix Semigroups

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6518

Title: Testing Simultaneous Similarity of Matrices and Related Problems for Matrix Semigroups
Author: Ogihara, Mitsunori ; Zalcstein, Yechezkel (Zeke)
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.
Type: Technical Report
URI: http://hdl.handle.net/1853/6518
Date: 2002
Relation: CC Technical Report; GIT-CC-02-01
Publisher: Georgia Institute of Technology
Subject: Simultaneous similarity
Matrix semigroups
Complexity
RNC
Algebra

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-CC-02-01.pdf 252.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record