  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\neq 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\neq 2$ in time $O^*(3.97^\mathsf{pw})$, indicating
that the modulus can affect the complexity in intricate ways.
