For an even integer t ≥ 2, the Matching Connectivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on t vertices; an entry H_t[M₁, M₂] is 1 if M₁ and M₂ form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that H_t has rank exactly 2^t/2−1 over GF(2). The upper bound is established by an explicit factorization of H_t as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis X_t of H_t. The lower bound follows because the 2^t/2−1 × 2^t/2−1 submatrix with rows and columns labeled by X_t can be seen to have full rank.

We obtain several algorithmic results based on the rank of H_t and the particular structure of the matchings in X_t. First, we present a 1.888ⁿ n^O(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + √ 2)^pwn^O(1) time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + √2 − ε)^pwn^O(1), for any ε > 0, would imply the breakthrough result of a (2 − ε^′)ⁿ-time algorithm for CNF-Sat for some ε^′ > 0.