arXiv preprint ·
Factorisability of Low Dimensional Non-Negative Integer Matrices
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Discrete Mathematics
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
Minimum Sum Vertex Cover via Minimum Vertex Cover
Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
Get the few papers worth your time in Discrete Mathematics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.