Narrow Results

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of integral square matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several questions for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words.

Motivated by recent results relating synchronizing DFAs and primitive sets, we tackle the synchronization process and the related longstanding Černý conjecture by studying the primitivity phenomenon for sets of nonnegative matrices having neither zero-rows nor zero-columns. We formulate the primitivity process in the setting of a two-player probabilistic game and we make use of convex optimization techniques to describe its behavior. We develop a tool for approximating and upper bounding the exponent of any primitive set and supported by numerical results we state a conjecture that, if true, would imply a quadratic upper bound on the reset threshold of a new class of automata.

We consider the following matrix reachability problem: given r square matrices with entries in a semiring, is there a product of these matrices which attains a prescribed matrix? Similarly, we define the vector (resp. scalar) reachability problem, by requiring that the matrix product, acting by right multiplication on a prescribed row vector, gives another prescribed row vector (resp. when multiplied on the left and right by prescribed row and column vectors, gives a prescribed scalar). We show that over any semiring, scalar reachability reduces to vector reachability which is equivalent to matrix reachability, and that for any of these problems, the specialization to any r ≥ 2 is equivalent to the specialization to r = 2. As an application of these reductions and of a theorem of Krob, we show that when r = 2, the vector and matrix reachability problems are undecidable over the max-plus semiring (ℤ∪{-∞}, max,+). These reductions also improve known results concerning the classical zero corner problem. Finally, we show that the matrix, vector, and scalar reachability problems are decidable over semirings whose elements are "positive", like the tropical semiring (ℤ∪{+∞}, min,+).

We study properties determined by idempotents in the following families of matrix semigroups over a semiring $S$: the full matrix semigroup $M_n(S)$, the semigroup $U{T}_n(S)$ consisting of upper triangular matrices, and the semigroup $U_n(S)$ consisting of all unitriangular matrices. Il’in has shown that (for $n>2$) the semigroup $M_n(S)$ is regular if and only if $S$ is a regular ring. We show that $U{T}_n(S)$ is regular if and only if $n=1$ and the multiplicative semigroup of $S$ is regular. The notions of being abundant or Fountain (formerly, weakly abundant) are weaker than being regular but are also defined in terms of idempotents, namely, every class of certain equivalence relations must contain an idempotent. Each of $M_n(S)$, $U{T}_n(S)$ and $U_n(S)$ admits a natural anti-isomorphism allowing us to characterise abundance and Fountainicity in terms of the left action of idempotent matrices upon column spaces. In the case where the semiring is exact, we show that $M_n(S)$ is abundant if and only if it is regular. Our main interest is in the case where $S$ is an idempotent semifield, our motivating example being that of the tropical semiring $𝕋$. We prove that certain subsemigroups of $M_n(S)$, including several generalisations of well-studied monoids of binary relations (Hall relations, reflexive relations, unitriangular Boolean matrices), are Fountain. We also consider the subsemigroups $U{T}_n(S^{\ast })$ and $U_n(S^{\ast })$ consisting of those matrices of $U{T}_n(S)$ and $U_n(S)$ having all elements on and above the leading diagonal non-zero. We prove the idempotent generated subsemigroup of $U{T}_n(S^{\ast })$ is $U_n(S^{\ast })$. Further, $U{T}_n(S^{\ast })$ and $U_n(S^{\ast })$ are families of Fountain semigroups with interesting and unusual properties. In particular, every $\widetilde{{ℛ}}$-class and $\widetilde{{ℒ}}$-class contains a unique idempotent, where $\widetilde{{ℛ}}$ and $\widetilde{{ℒ}}$ are the relations used to define Fountainicity, but yet the idempotents do not form a semilattice.