A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank

For even $k$, the matchings connectivity matrix $mathbf{M}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al. (STOC 2013) showed that the rank of $mathbf{M}_k$ over $mathbb{Z}_2$ is $Theta(sqrt 2^k)$ and used this to give an $O^*((2+sqrt{2})^{mathsf{pw}})$ time algorithm for counting Hamiltonian cycles modulo $2$ on graphs of pathwidth $mathsf{pw}$. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within $mathbf{M}_k$, which enabled a pattern propagation commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar pattern propagation when only a black-box lower bound on the asymptotic rank of $mathbf{M}_k$ is given; no stronger structural insights such as the existence of large permutation submatrices in $mathbf{M}_k$ are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes $p$) parameterized by pathwidth. To apply this technique, we prove that the rank of $mathbf{M}_k$ over the rationals is $4^k / mathrm{poly}(k)$. We also show that the rank of $mathbf{M}_k$ over $mathbb{Z}_p$ is $Omega(1.97^k)$ for any prime $p eq 2$ and even $Omega(2.15^k)$ for some primes. As a consequence, we obtain that Hamiltonian cycles cannot be counted in time $O^*((6-epsilon)^{mathsf{pw}})$ for any $epsilon>0$ unless SETH fails. This bound is tight due to a $O^*(6^{mathsf{pw}})$ time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes $p eq 2$ in time $O^*(3.97^mathsf{pw})$, indicating that the modulus can affect the complexity in intricate ways.