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

Question

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?

Answer 1

The algebraic view has many useful properties. I think these become more evident when you move from the Boolean setting to richer semirings, e.g., tropical-weighted automata. At any rate, a celebrated result that uses this view is Simon's Factorization theorem. An excellent survey by Bojanczyk is here: https://www.mimuw.edu.pl/~bojan/papers/forests-dlt.pdf

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

This doesn't really answer your question, but maybe these references will be useful to get the overall gist of this approach.