Factorisability of Low Dimensional Non-Negative Integer Matrices
En palabras de los autores
We consider the problem of determining if a given two-dimensional nonnegative integer matrix is the product of two such matrices, excluding trivial units. A matrix with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of 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.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Accepted for publication at 20th International Conference on Reachability Problems, RP 2026