On the rank of the communication matrix for deterministic two-way finite automata

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\left(\genfrac{}{}{0px}{}{n}{k-1}\right)\left(\genfrac{}{}{0px}{}{n}{k}\right)\left(\genfrac{}{}{0px}{}{2k-2}{k-1}\right)=(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 $\left(\genfrac{}{}{0px}{}{2k-2}{k-1}\right)$, and this implies the above formula for $f(n)$.