Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices

Conference item

A zero-one matrix is a matrix with entries from {0, 1}. We study monoids containing only such matrices. A finite set of zero-one matrices generating such a monoid can be seen as the matrix representation of an unambiguous finite automaton, an important generalisation of deterministic finite automata which shares many of their good properties.
Let A be a finite set of n × n zero-one matrices generating a monoid of zero-one matrices, and m be the cardinality of A. We study the computational complexity of computing the minimum rank of a matrix in the monoid generated by A. By using linear-algebraic techniques, we show that this problem is in NC and can be solved in O(mn4) time. We also provide a combinatorial algorithm finding a matrix of minimum rank in O(n2+ω + mn4) time, where 2 ≤ ω ≤ 2.4 is the matrix multiplication exponent. As a byproduct, we show a very weak version of a generalisation of the Černý conjecture: there always exists a straight line program of size O(n2) describing a product resulting in a matrix of minimum rank.
For the special case corresponding to complete DFAs (that is, for the case where all matrices have exactly one 1 in each row), the minimum rank is the size of the smallest image of the set of states under the action of a word. Our combinatorial algorithm finds a matrix of minimum rank in time O(n3 + mn2) in this case.

Authors: Kiefer, S; Ryzhikov, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
• Pages: 61:1-61:22
• Series: Leibniz International Proceedings in Informatics (LIPIcs)
• Series number: 327
• Publication date: 2025-02-24
• Acceptance date: 2025-02-11
• Event title: 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
• DOI: 10.4230/LIPIcs.STACS.2025.61
• ISSN: 1868-8969
• ISBN: 9783959773652
• Language: English
• Keywords: matrix monoids; minimum rank; unambiguous automata