On the Identity and Group Problems for Complex Heisenberg Matrices

Bell, Paul C, Niskanen, Reino, Potapov, Igor and Semukhin, Pavel (2023) On the Identity and Group Problems for Complex Heisenberg Matrices. .

Text RP2023_paper.pdf - Author Accepted Manuscript Access to this file is embargoed until 5 October 2024. Download (674kB)

Abstract

We study the Identity Problem, the problem of determining if a finitely generated semigroup of matrices contains the identity matrix; see Problem 3 (Chapter 10.3) in “Unsolved Problems in Mathematical Systems and Control Theory” by Blondel and Megretski (2004). This fundamental problem is known to be undecidable for Z4 × 4 and decidable for Z2 × 2. The Identity Problem has been recently shown to be in polynomial time by Dong for the Heisenberg group over complex numbers in any fixed dimension with the use of Lie algebra and the Baker-Campbell-Hausdorff formula. We develop alternative proof techniques for the problem making a step forward towards more general problems such as the Membership Problem. We extend our techniques to show that the fundamental problem of determining if a given set of Heisenberg matrices generates a group, can also be decided in polynomial time.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	03 Nov 2023 16:47
Last Modified:	22 Nov 2023 22:42
DOI:	10.1007/978-3-031-45286-4_4
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3176549