Bell, PC, Niskanen, R, Potapov, I and Semukhin, P (2023) On the Identity and Group Problems for Complex Heisenberg Matrices. In: Reachability Problems - 17th International Conference, RP 2023, Nice, France, October 11-13, 2023, Proceedings , 14235. pp. 42-45. (Reachability Problems: 17th International Conference, RP 2023, 11th October - 13th October 2023, Nice, France).

Text BNPS_RP23.pdf - Accepted Version Restricted to Repository staff only until 5 October 2024. Download (483kB)

Abstract

We study the Identity Problem, the problem of determining if a finitely generated semigroup of matrices contains the identity matrix; see Problem 3 (Chapter10.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 Heisen bergmatrices generates a group, can also be decided in polynomial time.

Item Type:	Conference or Workshop Item (Paper)
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science & Mathematics
Publisher:	Springer cHAM
SWORD Depositor:	A Symplectic
Date Deposited:	22 Aug 2023 11:02
Last Modified:	17 Oct 2023 10:41
DOI or ID number:	10.1007/978-3-031-45286-4
URI:	https://researchonline.ljmu.ac.uk/id/eprint/20852

View Item