On shortest products
for nonnegative matrix mortality

Given a finite set $\mathcal{A}$ of integer square matrices of the same dimension, the matrix mortality problem asks if the monoid generated by $\mathcal{A}$, that is, the set of all possible products of matrices from $\mathcal{A}$, contains the zero matrix. This problem is undecidable already for sets of $3\times 3$ matrices [Pat70], and is a subject of extensive research, see [CHHN14] for a survey of recent developments.

We consider a special case of matrix mortality where all matrices in $\mathcal{A}$ are nonnegative, that is, all their entries are nonnegative. We call this problem nonnegative matrix mortality. The theory of nonnegative matrices has applications in the theory of codes [BPR10], Markov chains [Sen06] and symbolic dynamics [LM21], and recently there has been a significant interest in reachability problems for sets of nonnegative matrices and monoids generated by them [PV12, GGJ18, WZ23].

Clearly, for nonnegative matrix mortality it only matters which entries of the matrices in $\mathcal{A}$ are strictly positive and which are zero. In particular, this implies that nonnegative matrix mortality is decidable in polynomial space. Moreover, for a set $\mathcal{A}$ of nonnegative $n\times n$ matrices, the length of a shortest product from this set resulting in the zero matrix is at most $2^{n}-1$. This easily follows from the interpretation of $\mathcal{A}$ as a non-deterministic finite (semi-)automaton (NFA), as explained, e.g., in [RSX12]. Since our results, as well as most of the existing literature on nonnegative matrix mortality, use this correspondence, we provide its details.

We view a finite set $\mathcal{A}$ of nonnegative $n\times n$ matrices as an NFA with a state set $Q=\{1,2,\ldots,n\}$. Each letter $a_{j}$ of its alphabet $\Sigma$ corresponds to a matrix $A_{j}\in\mathcal{A}$. To define the transition relation $\Delta:Q\times\Sigma\to 2^{Q}$, we take $\Delta(i,a_{j})$ to be the set of all $h$ such that the entry $(i,h)$ in $A_{j}$ is strictly positive. When the transition relation is clear from the context, we denote $\Delta(q,a)$ as $q\cdot a$. We homomorphically extend it to words over $\Sigma$, and then to subsets $S\subseteq Q$ as $S\cdot w=\{p\mid p\in q\cdot w\mbox{ for some }q\in S\}$. In thus constructed NFA $(Q,\Sigma,\Delta)$, with respect to matrix mortality, words correspond to products of matrices from $\mathcal{A}$: we have $Q\cdot w=\emptyset$ if and only if the product of matrices corresponding to $w$ is the zero matrix. Such words $w$ are called mortal. To obtain the mentioned upper bound of $2^{n}-1$ (observed, e.g., in [IS99]), it is now enough to note that for a shortest mortal word $w=x_{1}x_{2}\ldots x_{k}$ the sets $Q\cdot x_{1}x_{2}\ldots x_{i}$ for different values of $i$ are pairwise different subsets of $Q$, and hence $k\leq 2^{n}-1$.

The length of a shortest mortal word of an NFA is called its mortality threshold. Let $\mathbf{mt}(n,m)$ denote the maximum mortality threshold of an NFA with $n$ states and $m$ letters admitting a mortal word. In this paper, we investigate the values $\mathbf{mt}(n,m)$ depending on $m$. As shown above, for every $n$ and $m$, $\mathbf{mt}(n,m)\leq 2^{n}-1$. We survey the known bounds on $\mathbf{mt}(n,m)$ in the next section, and in the rest of this section we mention some other relevant results.

The problem of checking if a given NFA admits a mortal word is PSPACE-complete, even when restricted to binary NFAs [KRS09]. As usually, we call an NFA binary if its alphabet has size two, and ternary if it has size three.

In [KM21], the case where $\mathcal{A}$ is a set of nonnegative integer matrices of joint spectral radius at most one is considered. This case includes, in particular, all sets $\mathcal{A}$ of $\{0,1\}$-matrices (that is, matrices whose entries belong to the set $\{0,1\}$) with the property that the monoid generated by $\mathcal{A}$ contains only $\{0,1\}$-matrices. Such sets $\mathcal{A}$ correspond to unambiguous NFAs, which are NFAs with the property that for every pair $p,q$ of states and every word $w$ there is at most one path from $p$ to $q$ labelled by $w$. It is proved in [KM21] that for sets of joint spectral radius at most one, the existence of a product resulting in the zero matrix can be checked in polynomial time, and for all $m$ we have $\mathbf{mt}_{\rho\leq 1}(n,m)\leq n^{5}$, where $\mathbf{mt}_{\rho\leq 1}(n,m)$ is $\mathbf{mt}(n,m)$ restricted to such sets. The best known lower bound is quadratic in $n$ [Rys97]. Some more results on mortal words for unambiguous NFAs are presented in [BC19].

Our contributions. We study the following question: given a set of $m$ nonnegative $n\times n$ matrices, how long can their shortest product resulting in the zero matrix be? In Section 2 we survey known results. Section 3 contains our main contributions. Namely, for $m=n$, we show a lower bound of $2^{n}-1$ (Theorem 4), matching the upper bound for arbitrary $m$. We prove it by constructing an NFA simulating a binary counter counting from $2^{n}-1$ to zero. The case of constant $m$ uses the same idea, but requires much more involved constructions to implement it, resulting in a lower bound of $2^{(n-4)/2}$ for $m=3$ (Theorem 5) and a lower bound of $2^{(n-2)/3}$ for $m=2$ (Theorem 6). We conclude the paper by discussing other approaches to NFA and DFA mortality in Section 4, and providing a list of open problems related to this setting in Section 5.

In this section, we explain existing results on $\mathbf{mt}(n,m)$. The first result about this value seems to be in the work [GHKR82], where it is proved that $\mathbf{mt}(n,m)$ is not bounded by any polynomial in $n$. Most of the known results are not stated in terms of matrix or NFA mortality, so we appropriately rephrase them. We also show that strong lower bounds on $\mathbf{mt}(n,m)$ can be easily obtained from existing results that are not obviously related to mortality.

For all lower bounds in this section, the main idea is to construct an NFA simulating a binary counter. Namely, for every $k$ we construct an NFA with the number of states linear in $k$ such that, when reading a word $w$, a dedicated set $Q=\{q_{1},\ldots,q_{k}\}$ of $k$ states behaves in the following way. We say that a state $q$ is active after the application of a word $w$ if $q\in p\cdot w$ for some state $p$, otherwise we say that it is inactive. Initially, all states in $Q$ are active. We interpret active and inactive states from $Q$ as a number in the binary encoding. Namely, given a word $w\in\Sigma^{*}$, define $\operatorname{bin}(w)=x_{1}x_{2}\ldots x_{k}$, where $x_{i}=1$ if $q_{i}\in Q\cdot w$, and $x_{i}=0$ otherwise. We treat $\operatorname{bin}(w)$ as a natural number represented in the binary notation, with the most significant bit first. By construction of the NFA we guarantee that when reading a letter, this number is either decremented by at most one or is set again to the number consisting of all ones. The length of a shortest mortal word for such NFA is then at least $2^{k}-1$.

For an alphabet whose size is equal to the number of states, this idea can be implemented in a fairly straightforward way with a $k$-state NFA. To implement it with a ternary and a binary alphabet, we need more advanced techniques. The main challenge is that at least one of the letters must have a different effect on the encoding of the number depending on its value. To achieve that, between every two decrements we shift the number to the right until it ends with a one, thus iteratively dividing it by two, and simultaneously add some additional marker bits to preserve the information about the number of shifts we performed. In particular, it is important to remark that in these constructions not every application of a letter decrements the value of the number that we are tracking. Namely, we will have one letter that actually decrements the value, and all other letters will perform auxiliary operations such as shifting the representation. These ideas will be explained in detail in due course.

Conventions for figures. In all figures in this section, we use a vertical bold outgoing arrow to indicate that there is a transition from the state it originates from to all the states of the NFA. Similarly, a vertical bold incoming arrow indicates that there is a transition from each state of the NFA (except for states with a dashed outgoing arrow) to the state where the arrow ends. A dashed outgoing arrow from a state means that the image of this state is empty.

The presented constructions, as well as all mentioned constructions from the literature, have purely combinatorial nature. In this brief section we discuss a possibility of a more algebraic view on automata mortality. We focus on a simpler case of strongly connected DFAs, since even for this case very little is known. A DFA is called strongly connected if for every pair $p,q$ of its states there is a word mapping $p$ to $q$.

In [AVG13], another reachability property of strongly connected complete DFAs, namely the reset threshold, was linked to exponents of primitive matrices. A word is called synchronizing for a complete DFA $\mathcal{A}$ if it maps all states of $\mathcal{A}$ to the same state. The length of a shortest synchronizing word of $\mathcal{A}$ is then called its reset threshold. Let $M$ be the sum of the matrices of all letters of $\mathcal{A}$. If $\mathcal{A}$ is synchronizing, $M$ must be primitive. A matrix is primitive if some its power has only strictly positive entries. The smallest such power is called the exponent of a matrix. In [AVG13] it is proved that the exponent of $M$ is at most the reset threshold of $\mathcal{A}$ plus $n-1$, where $n$ is the number of states of $\mathcal{A}$. Thus, one obstacle for a complete DFA to synchronize fast is a large exponent of the corresponding matrix. A more advanced property of similar kind is proposed in [Gus13].

The DFA mortality problem is sometimes framed as synchronization of a particular class of complete DFAs (namely, of complete DFAs with a single sink state), but we find that DFA mortality significantly differs from DFA synchronization and deserves independent treatment. One reason for that is the dependence on the size of the alphabet: adding more letters to a complete DFA usually helps to synchronize it faster, but, in contrast, it allows a DFA to “stall” for longer when applying a mortal word. Thus, the known series of complete DFAs with the largest reset threshold have two letters [AVG13], but the series with the largest known mortality threshold have the number of letters equal to the number of states [Rys97]. Perhaps more importantly, the results of [AVG13] do not apply to DFA mortality, since after adding a sink state a DFA stops being strongly connected.

Mortality and synchronization can be viewed as very combinatorial phenomena: having a set of matrices, we ask for just one product of such matrices with a certain property, and hence have to make a lot of independent choices when constructing this product. Primitivity of a single matrix has much more algebraic flavour to it, since it concerns iterated multiplication of a single matrix.

We thus pose the following semi-formal question: is there an algebraic property of a DFA telling us something about its mortality threshold?

A simpler question is to ask for an algebraic property guaranteeing that a mortal word exists. For DFAs this is trivial, but for unambiguous NFAs, a proper superclass of DFAs, such property is precisely that the joint spectral radius of the corresponding set of matrices is strictly smaller than one [KM21]. For general NFAs one has to keep in mind that deciding the existence of a mortal word becomes PSPACE-complete, and hence one has to look for a “non-constructive” property.

The discovery of the connection between reset threshold and the exponent of a matrix in [AVG13] was done by observing in exhaustive search experiments the similarity between the attainable large values of reset thresholds on the one hand and exponents of primitive matrices on the other hands. The present paper can be seen as a step towards a similar potential development for mortality. For small $n$, it is not hard to write down the sets of $n\times n$ matrices with large mortality thresholds provided in the previous section, in case one wants to check some conjectures connected to our question. To further assist with this goal, we now briefly survey what is known about DFA mortality, and provide a new simple family of binary DFAs with large mortality thresholds.

Denote by $\mathbf{mt}_{\mathrm{d}}(n,m)$ the maximum mortality threshold of a DFA with $n$ states and $m$ letters admitting a mortal word. In [Rys97] it is proved that for all $m$ we have $\mathbf{mt}_{\mathrm{d}}(n,m)\leq\frac{n(n+1)}{2}$, and that this upper bound is tight already for $m=n$. The binary case is more intriguing. To the best of our knowledge, the first series of $n$-state binary DFAs with quadratic mortality threshold is provided in Proposition 3.4 of [BCM⁺03], showing that $\mathbf{mt}_{\mathrm{d}}(n,2)\geq\frac{(n-1)^{2}}{4}$. Later on, such series with slightly larger mortality threshold were provided in [Mar08] and [AV19], showing, respectively,

A few more series with simpler structure but with slightly smaller mortality threshold are provided in [Ryz19]. It is not known if $\mathbf{mt}_{\mathrm{d}}(n,2)=\frac{n^{2}}{4}+\mathcal{O}(n)$.

Below we provide a very simple series of binary DFAs with mortality threshold $\frac{n^{2}+8n}{4}+\mathcal{O}(1)$ which does not seem to appear in the literature. It can be seen as a simplification of the construction from [Mar08] with approximately the same mortality threshold. Let $\mathcal{A}=(Q,\{a,b\},\delta)$ be such that $Q=\{q_{1},\ldots,q_{k},p_{1},\ldots,p_{k}\}$. Define

The fact that $\mathcal{A}$ has mortality threshold $\frac{n^{2}+8n}{4}+\mathcal{O}(1)$ follows, for example, from Lemma 1 in [AV19], since this is another example of adding a tail to an almost permutation automaton, formally defined in [AV19]. While most of the known series with large mortality thresholds have this structure, not all of them do: for example, DFAs from the series in [BCM⁺03] do not have a tail, and have a cycle going through all states instead.

An illustration for the case $k=4$ is provided below, with the action of $a$ depicted by solid arrows and the action of $b$ by dashed arrows.

The unique shortest mortal word for this DFA is $a^{k}ba^{k}aba^{k}(aaba^{k})^{k-2}$. The intuition behind this word is that if everything is done “optimally”, after killing (that is, applying a word that is undefined for a state) two states among $q_{1},\ldots,q_{k}$, the structure of the cycles on them maintains that $q_{1}$ and $q_{k}$ are inactive, and hence they have to be traversed in the process of killing every remaining active state from $q_{1},\ldots,q_{k}$.

One of the most interesting questions that remains open is the precise behaviour of $\mathbf{mt}(n,m)$ and $\mathbf{mt}_{\mathrm{d}}(n,m)$ for $m=2$ and $m=3$. As already discussed in Section 4, lower bounds on $\mathbf{mt}_{\mathrm{d}}(n,2)$ were investigated quite actively [AV19, BCM⁺03, Mar08, Ryz19], and all these bounds are still of the form $\frac{n^{2}}{4}+\mathcal{O}(n)$. To the best of our knowledge, there is no plausible conjecture on the value of $\mathbf{mt}_{\mathrm{d}}(n,2)$ in the literature, and there are no known upper bounds better than $\frac{n(n+1)}{2}$ [Rys97], a bound that holds for any size of the alphabet. It is in fact easy to see that this bound cannot be tight for $\mathbf{mt}_{\mathrm{d}}(n,2)$, but we were not able to obtain a significant improvement for it. However, we conjecture that it can be improved to at least the bound $\mathbf{mt}_{\mathrm{d}}(n,2)\leq\frac{7n^{2}}{16}+\mathcal{O}(n)$. As for bounds on $\mathbf{mt}_{\mathrm{d}}(n,3)$, we are not aware of any results. Since the dependence of $\mathbf{mt}_{\mathrm{d}}(n,m)$ on $m$ seems to be far from trivial, this is a natural first step to approach its investigation. Alternatively, one can ask for bounds on $\mathbf{mt}_{\mathrm{d}}(n,\frac{n}{2})$.

The same questions can be asked about $\mathbf{mt}(n,m)$, and the situation with existing results is similar: we already surveyed known lower bounds in Section 2 and mentioned that $\mathbf{mt}(n,m)\leq 2^{n}-1$. To the best of our knowledge, no better upper bounds for small $m$ are known, and the same comments that we made about the precise dependence of $\mathbf{mt}_{\mathrm{d}}(n,m)$ on $m$ also apply to $\mathbf{mt}(n,m)$.

Mortality of unambiguous NFAs is even further from being understood. As mentioned in the introduction, we know that the mortality threshold for them is between $\frac{n(n+1)}{2}$ [Rys97] and $n^{5}$ [KM21]. The lower bound is provided by a series of DFAs, and all known families of unambiguous NFAs with large mortality threshold are DFAs or their co-deterministic counterparts (obtained by reversing the direction of each transition). Since unambiguous NFAs constitute a much more general class than DFAs, this is a curious situation that deserves further investigation.

Finally, it would be interesting to see any subclasses with good (that is, polynomial) behaviour of $\mathbf{mt}(n,m)$ besides the class of unambiguous NFAs [KM21].