## connectivity in automata by words of length n-1

Let $A$ be a complete strongly connected automaton with $n$ states. Does always exist a word $v$ of length at most $n-1$ such that its underlying graph is connected? That is for any pair of distinct states $p,q$ exists a positive integer $k$ such that either $p.v^k = q$ or $q.v^k = p$. Additionaly we can assume that there exists a word $w$ such that its underlying graph is connected.

The statement also can be reformulated in terms of linear algebra.

-
 The automaton is deterministic. Right? – Mark Sapir Apr 3 2012 at 18:26 >The automaton is deterministic. Right? right – Misha Berlinkov Apr 3 2012 at 18:26 There are some other assumptions missing otherwise the answer is obviously "no", see my answer. – Mark Sapir Apr 3 2012 at 18:43 The assumption is "Additionaly we can assume that there exists a word w such that its underlying graph is connected." and we can also assume that $w$ takes $A$ into one state, but I think it is not necessary. – Misha Berlinkov Apr 3 2012 at 18:55 Assumption that $|Aw|=1$ implies that the GCD of the lengths of cyclies in $A$ is 1 (see Trakhtman's theorem). Perhaps you should reformulate the question putting the necessary assumptions before the question itself. The question should say something like: If there exists $w$ for which $(A,w)$ is connected, then there exists such a $w$ of length at most $n-1$. – Mark Sapir Apr 3 2012 at 19:07
show 9 more comments