Factorisability of Low Dimensional Non-Negative Integer Matrices

Bell, P ORCID: 0000-0003-2620-635X, Foster, E, Reidenbach, D and Semukhin, P ORCID: 0000-0002-7547-6391 Factorisability of Low Dimensional Non-Negative Integer Matrices. In: Reachability Problems . (20th International Conference on Reachability Problems, 21st Oct- 23rd Oct 2026, Turku, Finland). (Accepted)

Text BFRS26arXiv.pdf - Accepted Version Access Restricted Available under License Creative Commons Attribution. Download (528kB)

Abstract

We consider the problem of determining if a given two-dimensional nonnegative integer matrix M is the product of two such matrices, excluding trivial units. A matrix M with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of 2x2 matrices over the natural numbers, otherwise it is called composite. We also consider the problem of finding a (non-unique) factorisation of a composite matrix. Our results have applications in computational group theory and the theory of codes, where such matrices are called incidence matrices. We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

Item Type:	Conference or Workshop Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Computer Science and Mathematics
Publisher:	Springer
Date of acceptance:	3 August 2026
Date Deposited:	23 Sep 2026 10:04
Last Modified:	23 Sep 2026 10:04
URI:	https://researchonline.ljmu.ac.uk/id/eprint/29503

View Item