Suppose we have a deterministic complete [finite automaton](https://en.wikipedia.org/wiki/Deterministic_finite_automaton) which is synchronized, meaning we have a [reset word](https://en.wikipedia.org/wiki/Synchronizing_word), i.e. a word which resets the automaton to a definite state, regardless from which state we start. Suppose further that the underlying digraph (i.e. the graph which we get when forgetting the labels on the transitions) is Eulerian, meaning that the outdegree equals the indegree at each vertex. Then do you know any (preferable elementary) proof of the following statement:



> 
> For every proper subset of the state set of the automaton, there exists a word whose inverse image (i.e. the set of states that are mapped to the given state set under the word) is larger in cardinality as the given set.
> 
> 
> 


The property that the digraph is Eulerian gives that the automaton is strongly connected, and the common value of the outdegree and the indegree equals the size of the alphabet. So, if we denote the state set by $Q$, the alphabet by $\Sigma$ and the state transition function by $\delta : Q \times \Sigma \to Q$, then as the digraph is Eulerian we have for $T \subseteq Q$
and with $\delta^{-1}(T, x) := \{ q \in Q : \delta(q, x) \in T \}$ for $x \in \Sigma$ that
$$
 \sum\_{x \in \Sigma} |\delta^{-1}(T, x)| = |\Sigma||T|.
$$
because these are two ways to count the number of incoming edges. Now this gives that for every $T \subseteq Q$ we have exactly one of the two cases
$$
 \forall x \in \Sigma : |\delta^{-1}(T, x)| = |T|
 \qquad
 \mbox{or}
 \qquad
 \exists x \in \Sigma : |\delta^{-1}(T, x)| > |T|. 
$$
This observation might be of help. The above statement written more formal:



> 
> For every proper subset $T \subseteq Q$, there exits a word $w \in \Sigma^{\ast}$ such that $|\delta^{-1}(T, w)| > |T|$.
> 
> 
> 



For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset
This is proved in Section 4 of Kari's paper [here.](https://pdfs.semanticscholar.org/3b73/3fae84ed37f9d1bd061ccdabb6af73a4f9f4.pdf)


Essentially the same proof is in chapter 15 of my book the Representation Theory of Finite Monoids done from a more representation theoretic viewpoint. The main trick is to use ascending chain condition of vector spaces and that if a collection is ever less than its average than it also exceeds its average. 


