  The communication matrix for two-way deterministic finite automata (2DFA)
with $n$ states is defined for an automaton over a full alphabet of all
$(2n+1)^n$ possible symbols: its rows and columns are indexed by strings, and
the entry $(u, v)$ is $1$ if $uv$ is accepted by the automaton, and $0$
otherwise. With duplicate rows and columns removed, this is a square matrix of
order $n(n^n-(n-1)^n)+1$, and its rank is known to be a lower bound on the
number of states necessary to transform an $n$-state 2DFA to a one-way
unambiguous finite automaton (UFA). This paper determines this rank, showing
that it is exactly $f(n)=\sum_{k=1}^n \binom{n}{k-1} \binom{n}{k}
\binom{2k-2}{k-1} =(1+o(1)) \frac{3\sqrt{3}}{8\pi n} 9^n$, and this function
becomes the new lower bound on the state complexity of the 2DFA to UFA
transformation, thus improving a recent lower bound by S. Petrov and Okhotin
(``On the transformation of two-way deterministic finite automata to
unambiguous finite automata'', Inf. Comput., 2023). The key element of the
proof is determining the rank of a $k! \times k!$ submatrix, with its rows and
columns indexed by permutations, where the entry $(\pi, \sigma)$ is $1$ if
$\sigma \circ \pi$ is a cycle of length $k$, and 0 otherwise; using the methods
of group representation theory it is shown that its rank is exactly
$\binom{2k-2}{k-1}$, and this implies the above formula for $f(n)$.

Formal Languages and Automata Theory;Combinatorics;Representation Theory