Probabilisticts methods for primitive matrix semigroups

We study the primitivity property of finitely generated matrix semigroups from a probabilistic point of view and via two approaches. A finite set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive; the length of the shortest of these products is called the exponent of the set. We firstly study the primitivity property of random matrix sets, by rephrasing it in terms of random labeled directed multigraphs. We extend classical models of random graph theory to labeled directed multigraphs and we show that these random models admit a sharp threshold with respect to the primitivity property. We also show that when primitive, these models have low exponent with high probability. We then prove that they exhibit the same threshold behavior with respect to the property of being column-primitive and we use these results for studying the 2-directability property and 3-directability property of random nondeterministic finite state automata (NDFAs). In particular, we show that an NDFA generated according to the uniform distribution admits a short 2-directing word and a short 3-directing word with high probability. Inspired by the probabilistic method, we then present a more involved randomized construction that generates primitive sets with large exponent with nonvanishing probability and we use our findings for exhibiting new families of synchronizing finite state automata with quadratic reset threshold. Secondly, we embed the primitivity problem in a probabilistic game framework in order to study its properties. We develop a tool, that we call the synchronizing probability function for primitive sets of matrices, that captures the speed at which a primitive set reaches its first positive product thus representing the convergence of the primitivity process, and we show that this function must increase regularly in some sense. We then show that this function can be used for efficiently approximating the exponent of any given primitive set made of matrices having neither zero-rows nor zero-columns (NZ-matrices) and for (potentially) improving the upper bound on the maximal exponent among the primitive sets of NZ-matrices. Finally, we prove that in a primitive semigroup of matrix size n × n, for all k ≤ √n the length of the shortest product having a row or a column with k positive entries is linear in n, question that is still open for synchronizing automata.