Tech Reports

ULCS-08-005

Computational Problems in Matrix Semigroups (PhD Thesis)

Paul Bell

Abstract

This thesis deals with computational problems that are defined on matrix semigroups, which play a pivotal role in Mathematics and Computer Science in such areas as control theory, dynamical systems, hybrid systems, computational geometry and both classical and quantum computing to name but a few. Properties that researchers wish to study in such fields often turn out to be questions regarding the structure of the underlying matrix semigroup and thus the study of computational problems on such algebraic structures in linear algebra is of intrinsic importance.

Many natural problems concerning matrix semigroups can be proven to be intractable or indeed even unsolvable in a formal mathematical sense. Thus, related problems concerning physical, chemical and biological systems modelled by such structures have properties which are not amenable to algorithmic procedures to determine their values.

With such recalcitrant problems we often find that there exists a tight border between decidability and undecidability dependent upon particular parameters of the system. Examining this border allows us to determine which properties we can hope to derive algorithmically and those problems which Will forever be out of our reach, regardless of any future advances in computational speed.

There are a plethora of open problems in the field related to dynamical systems, control theory and number theory which we detail throughout this thesis. We examine undecidability in matrix semigroups for a variety of different problems such as membership and vector reachability problems, semigroup intersection emptiness testing and freeness, all of which are well known from the literature. We also formulate and survey decidability questions for several new problems such as vector ambiguity, recurrent matrix problems, the presence of any diagonal matrix and quaternion matrix semigroups, all of which we feel give a broader perspective to the underlying structure of matrix semigroups.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.