  For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a
matrix that has rows and columns both labeled by all perfect matchings of the
complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is
a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of
the Hamiltonicity problem, we present three results on the structure of H_t: We
first show that H_t has rank at most 2^{t/2-1} over GF(2) via an appropriate
factorization that explicitly provides families of matchings X_t forming bases
for H_t. Second, we show how to quickly change representation between such
bases. Third, we notice that the sets of matchings X_t induce permutation
matrices within H_t.
  Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} time
Monte Carlo algorithm that solves the Hamiltonicity problem in directed
bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles
modulo two in directed bipartite or undirected graphs in the same time bound.
Moreover, we use the fast basis change algorithm from the second result to
present a Monte Carlo algorithm that given an undirected graph on n vertices
along with a path decomposition of width at most pw decides Hamiltonicity in
(2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that
for every \epsilon >0 this cannot be improved to
(2+\sqrt{2}-\epsilon)^{pw}n^{O(1)} time unless the Strong Exponential Time
Hypothesis fails, i.e., a faster algorithm for this problem would imply the
breakthrough result of a (2-\epsilon)^n time algorithm for CNF-Sat.
