# Relationship between the transition monoid of an automaton and its adjacency matrix

Let $$A=(Q,\Sigma, \Delta, q_0, F)$$ be an NFA over an alphabet $$\Sigma$$, $$M(A)$$ be its transition monoid.

For all $$a\in\Sigma$$, let $$S_a\in\mathbb{B}^{|Q|\times|Q|}$$ be the adjacency matrix of $$A$$ relative to $$a$$, i.e., $$S_a(i,j)=1$$ iff $$(q_i,a,q_j)\in\Delta$$.

If I'm not mistaken, $$M(A)$$ is generated by $$S=\{S_a\mid a\in\Sigma\}$$ with the usual matrix product and identity (this is also explained in Pin's book, page 86, if I didn't misunderstood). This also means we can see each element of $$M(A)$$ as a matrix.

So are there any useful properties we can get about $$M(A)$$ from looking at the elements of $$M(A)$$ as matrices? Maybe some spectral properties?

• Spectral ideas (like eigenvalues) usually assume the matrix is over a field. Have they been generalised to semirings? Commented Jan 27, 2023 at 18:08
• Afaik yes, but I hardly know anything about these things… Commented Jan 27, 2023 at 20:08
• I'd be interested in references for spectral methods on matrices over semirings. Commented Jan 27, 2023 at 21:29

In the tropical semiring you can get pretty far using this view, by examining the generated semigroup (which is not necessarily finite), and defining the so-called stabilization monoid, which captures which runs diverge to $$\infty$$ and which stay bounded. An application of this can be found in a work on determinization of polynomially ambiguous weighted automata, here: https://hal.inria.fr/inria-00360205/document