Efficient test and factorization of small nonnegative integer matrices
Factorisability of Low Dimensional Non-Negative Integer Matrices
Discrete MathematicsData Structures and AlgorithmsInformation Theory
Summary
This paper looks at how to tell if a grid of whole numbers can be split into the product of two smaller such grids, ignoring simple cases. If it can’t be split, it’s called prime; if it can, it’s composite. The authors also provide a way to find such a split when it exists. Their work is useful in areas like group theory and code design, where these grids represent connections or relationships. They also offer an efficient method to do these tests and factorizations.
What this means in practice
- •For computational algebra software developers: Add a fast matrix primality test to algorithms involving groups represented by incidence matrices to improve factorisation routines.
- •For error correction code designers: Use efficient factorisation of incidence matrices to analyze and optimize code structures in communication systems.
Authors
Paul C. Bell, Eva Foster, Daniel Reidenbach, Pavel Semukhin
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 $2 \times 2$ 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.