Decidable and Undecidable Problems in Matrix Theory
Vesa Halava · 1997
This work is a survey on decidable and undecidable problems in matrix theory. The problems studied are simply formulated, however most of them are undecidable. The method to prove undecidabilities is the one found by Paterson [Pat] in 1970 to prove that the mortality of finitely generated matrix monoids is undecidable. This method is based on the undecidability of the Post Correspondence Problem. We shall present a new proof to this mortality problem, which still uses the method of Paterson, but is a bit simpler. Keywords: decidability, undecidability, matrix semigroups, mortality, freeness, finiteness, zero in the right upper-corner, Skolem's problem Contents 1 Introduction 1 2 Preliminaries 3 2.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Semigroups and monoids . . . . . . . . . . . . . . . . . . . . . 3 2.3 Matrix semigroups and monoids . . . . . . . . . . . . . . . . . 3 2.4 Decidability and undecidability . . . . . . . . . . . . . . . . . 6 2.5 ...