A Tight Lower Bound for Counting Hamiltonian Cycles
via Matrix Rank∗

arXiv:1709.02311v2 [] 21 Nov 2017

Radu Curticapean† Nathan Lindzey‡ Jesper Nederlof§

Abstract
For even k ∈ N, the matchings connectivity matrix Mk is a binary matrix indexed by perfect matchings on
k vertices; the entry at (M, M 0 ) is 1 iff M ∪ M 0 forms a single cycle. Cygan et al. (STOC 2013) showed
√ k
√
that the rank of Mk over Z2 is Θ( 2 ) and used this to give an O∗ ((2 + 2)pw ) time algorithm for counting
Hamiltonian cycles modulo 2 on graphs of pathwidth pw. The algorithm carries over to the decision problem
via witness isolation. 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 Mk , 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 Mk is given; no stronger structural insights such as the existence of large permutation
submatrices in Mk 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 Mk over the rationals is 4k /poly(k), using the
representation theory of the symmetric group and various insights from algebraic combinatorics. We also
show that the rank of Mk over Zp is Ω(1.97k ) for any prime p 6= 2 and even Ω(2.15k ) for some primes.
Combining our rank bounds with the new pattern propagation technique, we show that Hamiltonian
cycles cannot be counted in time O∗ ((6 − ε)pw ) for any ε > 0 unless SETH fails. This bound is tight due to a
O∗ (6pw ) time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian
cycles cannot be counted modulo primes p 6= 2 in time O∗ (3.97pw ) and, for some primes, not even in time
O∗ (4.15pw ), indicating that the modulus can affect the complexity in intricate ways.

∗

Part of this work was done while Radu and Jesper were visiting the Simons Institute for the Theory of Computing.
Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI).
radu.curticapean@gmail.com. Supported by ERC Grant PARAMTIGHT (No. 280152) and ERC Grant SYSTEMATICGRAPH (No. 725978).
‡
Department of Combinatorics and Optimization, University of Waterloo. nlindzey@uwaterloo.ca.
§
Department of Mathematics and Computer Science, Technische Universiteit Eindhoven. j.nederlof@tue.nl.
Supported by NWO Veni project 639.021.438
†

1

1

Introduction

Rank is a fundamental concept in linear algebra and has numerous applications in diverse areas of
discrete mathematics and theoretical computer science, such as algebraic complexity [8], communication complexity [27], and extremal combinatorics [30], to name only a few. A common phenomenon
is that low rank often helps in proving combinatorial upper bounds or designing algorithms, e.g.,
through representative sets [7, 13, 21] or the polynomial method (which ultimately relies on fast
rectangular matrix multiplication, enabled through low-rank factorizations of problem-related matrices [37]). In particular, rank has recently found applications in fine-grained complexity (see [1]
and the references therein) and parameterized complexity. In the latter, several influential results,
such as algorithms for kernelization [21], the longest path problem [31], and connectivity problems
parameterized by treewidth [12, 11, 7], rely crucially on low-rank factorizations.
In view of the utility of low rank in proving upper bounds, it is natural to ask, conversely,
whether high rank translates into lower bounds. Indeed, examples for this connection can be found
in communication complexity [22, Section 1.4] and circuit complexity [16]. In the present paper, we
find such applications also in fine-grained and parameterized complexity: We develop a technique
that allows us to transform rank lower bounds into conditional lower bounds for the problem #HC
of counting Hamiltonian cycles. The decision version HC of #HC, which asks for the existence of a
Hamiltonian cycle, is a classical subject of algorithmic research. For decades, the well-known O∗ (2n )
time dynamic programming algorithm [18] was essentially the fastest known algorithm for HC, until
a breakthrough result [4] showed that HC can actually be solved in O∗ (1.657n ) randomized time.
This result spawned several novel algorithmic insights into HC, but also showed that we still do not
understand this problem in a satisfactory way: No deterministic O∗ ((2 − ε)n ) time algorithm for
HC is known, and even no randomized O∗ ((2 − ε)n ) time algorithms are known for the more general
traveling salesman problem, the directed Hamiltonian cycle problem, or the counting version #HC.
One of the novel algorithmic techniques for HC following in the wake of [4] is closely tied to the
rank of the so-called matchings connectivity matrix [11]. For even k, the matchings connectivity
matrix Mk is indexed by the perfect matchings of the complete graph Kk , and the entry Mk [M, M 0 ]
for perfect matchings M and M 0 is defined as 1 if the union M ∪ M 0 is a single cycle, and 0 otherwise.
See Figure 1 for an example. The matchings connectivity matrix can be seen as a description of
the behavior of Hamiltonian cycles under graph separators, an interpretation that proved useful
for algorithmic applications. For instance, the authors of [11] show that the rank of Mk over Z2
is precisely 2k/2−1 and use this surprisingly low rank to count Hamiltonian cycles modulo 2 in
bipartite directed graphs in O(1.888n ) time, which was recently improved to O∗ (3n/2 ) time in [6]. A
randomized algorithm for the decision version √
follows from witness isolation.
The low rank of Mk also enabled an O∗ ((2+ 2)pw ) time algorithm for HC on graphs with a given
path decomposition of width pw. For this problem, the standard dynamic programming approach
would require to keep track of all partitions of separators, resulting in a running time of O∗√(2pw log pw );
it is thus somewhat remarkable that the single-exponential
running time of O∗ ((2 + 2)pw ) can
√
be achieved.√Even more surprisingly, the base 2 + 2 appears to be optimal, as it is known that
any O((2 + 2 − ε)pw ) time algorithm would violate the Strong Exponential Time Hypothesis
(SETH) [11]. This was proven by combining a general reduction technique for SETH-based lower
bounds from [24] with a special property of Mk , namely, that Mk contains a principal minor of
size 2k/2−1 that is a permutation matrix. In other words, there is a collection of 2k/2−1 perfect
matchings such that every perfect matching in this collection can be extended to a Hamiltonian
cycle by precisely one other member.
2

Nr

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1
2
3

0
0
0

0
0
0

0
0
0

0
1
1

1
0
1

1
1
0

0
1
1

1
1
0

1
0
1

1
0
1

1
1
0

0
1
1

1
1
0

1
0
1

0
1
1

4
5

0
1

1
0

1
1

0
0

0
0

0
0

0
1

1
0

1
1

1
0

0
1

1
1

1
1

0
1

1
0

6

1

1

0

0

0

0

1

1

0

1

1

0

0

1

1

7

0

1

1

0

1

1

0

0

0

0

1

1

0

1

1

8

1

1

0

1

0

1

0

0

0

1

0

1

1

1

0

9

1

0

1

1

1

0

0

0

0

1

1

0

1

0

1

10

1

0

1

1

0

1

0

1

1

0

0

0

0

1

1

11

1

1

0

0

1

1

1

0

1

0

0

0

1

0

1

12

0

1

1

1

1

0

1

1

0

0

0

0

1

1

0

13

1

1

0

1

1

0

0

1

1

0

1

1

0

0

0

14

1

0

1

0

1

1

1

1

0

1

0

1

0

0

0

15

0

1

1

1

0

1

1

0

1

1

1

0

0

0

0

Fig. 1: Originally from [11], this figure displays the matchings connectivity matrix M6 , which
indicates which pairs of the 15 perfect matchings on 6 vertices form a Hamiltonian cycle.
The general technique for SETH-based lower bounds from [24] was successfully applied to various
problems parameterized by pathwidth: As a result, the optimal base in the exponential dependence
on the pathwidth has been identified for many problems, assuming SETH. However, there are still
natural open problems left, such as #HC: It has been shown that this problem can be solved in
O∗ (6pw ) time [7], later extended to O∗ ((2ω + 2)tw ) time when parameterized by treewidth [38],
where 2 ≤ ω < 2.371 denotes the matrix multiplication constant. A tight lower bound however
remained elusive, and √
this might justify optimism towards improved algorithms: For example, if we
∗
could lift the O ((2 + 2)pw ) time algorithm for #HC modulo 2 to an O∗ ((4 − ε)pw ) time algorithm
for #HC, we could solve #HC on bipartite graphs in O∗ ((2 − ε0 )n ) time, since bipartite graphs
have pathwidth at most n/2.

Our main results
We strike out the route towards faster algorithms for #HC sketched above: We show that the
current pathwidth (and, assuming ω = 2, treewidth) based algorithms are optimal assuming SETH.
Theorem 1.1. Assuming SETH, there is no ε > 0 such that #HC can be solved in O∗ ((6 − ε)pw )
time on graphs with a given path decomposition of width pw.
This
√ theorem gives a natural example for an NP-hard problem whose decision version (with base
2) and counting version (with base 6) differ provably under SETH.
We prove Theorem 1.1 by starting from the general reduction technique in [24], augmented with
a novel idea: We extend the technique in such a way that it can exploit arbitrary lower bounds on
the matrix rank of Mk , without further insights into the particular structure of basis vectors. That
is, we derive Theorem 1.1 as a consequence of the following more general “black-box” connection

2+

3

between the rank of Mk and the running time for #HC: If the exponential base of the rank can be
lower-bounded by r, then we do not expect O∗ ((2 + r − ε)pw ) time algorithms.
Theorem 1.2. Let r ∈ R be such that logr (rank(Mk ))/k → c, where c ≥ 1, as even k tends to
infinity.1 Assuming SETH, there is no ε > 0 such that #HC can be solved in O∗ ((2 + r − ε)pw )
time on graphs with a given path decomposition of width pw.
For prime numbers p, the same applies to #HC modulo p when replacing r by rp , which is
defined analogously to r by taking rank(Mk ) over Zp .
To prove Theorem 1.1, we then combine Theorem 1.2 with our second main contribution: We
determine the rank of Mk over Q up to polynomial factors, and for primes p 6= 2, we additionally
give lower bounds on the rank over Zp that are higher than the rank over Z2 .
Theorem 1.3. The rank of Mk over the rational numbers is at least Ω(4k /k 3 ). For any prime
p 6= 2, the rank of Mk over Zp is at least Ω(1.979k ), and for prime 5 ≤ p ≤ 13, it is at least
Ω(2.152k ). See Theorem 3.7 for a full list.
The bound over Q is obtained by a novel application of representation theory, inspired by
a previous approach from [33], where the rank of a bipartite version of Mk over Q was found
to be Θ(2k ) up to polynomial factors. In the bipartite version of Mk , only perfect matchings
contained in the complete bipartite graph Kk/2,k/2 are considered. In our non-bipartite version,
any perfect matching in the complete graph Kk is allowed; this is more appropriate for algorithmic
applications, and our new bound over Q shows that going to the non-bipartite setting increases the
rank significantly.
Combined with Theorem 1.2, our bound over Zp suggests √
that #HC modulo √
prime p 6= 2 is
harder than modulo 2: We can solve #HC modulo 2 in O∗ ((2 + 2)pw ) time, where 2 ≤ 1.42, but
we cannot solve #HC modulo p 6= 2 in O∗ ((2 + 1.97)pw ) time unless SETH fails. This connects to
recent results [5, 6], which show that the counting Hamiltonian cycles modulo cn (not parameterized
by pathwidth) can be solved in time O∗ ((2 − εc )n ), where εc > 0 depends on the constant c.

Connection matrices and fingerprints
The matchings connectivity matrix Mk fits into a bigger picture of so-called connection matrices for
graph parameters, and our bounds on the rank of Mk translate into rank bounds in this framework.
The connection matrices of a graph parameter f are a sequence of matrices Ck , for k ∈ N,
which describe the behavior of f under graph separators of size k. To define these matrices, say
that a k-boundaried graph, for k ∈ N, is a simple graph with k distinguished vertices that are
labeled 1, . . . , k. Two k-boundaried graphs G and H can be glued together, yielding a graph G ⊕ H,
by taking the disjoint union of G and H and identifying vertices with the same label. The k-th
connection matrix Ck of f then is an infinite matrix whose rows and columns are indexed by
k-boundaried graphs such that the entry Ck [G, H] is f (G ⊕ H).
The ranks of connection matrices are closely related to graph-theoretic, algorithmic, and modeltheoretic properties of graph parameters [20, 26, 25]. In particular, the connection matrices Ck for
the number of Hamiltonian cycles were studied in [25, 26], where their rank was upper-bounded by
2O(k log k) . As a consequence of Theorem 1.3, we can improve upon this and obtain the following
essentially tight bounds.
1

This implies that rank(Mk ) can be lower-bounded by Ω(rk ) up to sub-exponential factors.

4

Theorem 1.4. For k ∈ N, the rank of the connection matrix Ck for the number of Hamiltonian
cycles is 6k , up to polynomial factors.
To prove this theorem, we use a third matrix, the fingerprint matrix Hk for Hamiltonian cycles,
which will also play an important role in our main reduction.2 A fingerprint of a k-boundaried
graph is a pair (d, M ), where d ∈ {0, 1, 2}k assigns 0, 1 or 2 to each boundary vertex, and M is a
perfect matching on the boundary vertices to which d assigns 1. Fingerprints are essentially the
states one would use in the natural dynamic programming routine for counting Hamiltonian cycles
parameterized by pathwidth; they describe the behavior of a Hamiltonian cycle on a given side
of a separation. A pair of fingerprints (d, M ) and (d0 , M 0 ) on B combines if dv + d0v = 2 for every
v ∈ B and additionally M ∪ M 0 forms a single cycle. The fingerprint matrix Hk is a binary matrix,
indexed by fingerprints, and the value at a pair of fingerprints is 1 iff the two fingerprints combine.
It can be derived easily from our rank bound for the matchings connectivity matrix Mk that
the rank of Hk is 6k up to polynomial factors, see Fact 2.2. To establish Theorem 1.4, we show in
Fact 2.3 that Ck and Hk have the same rank.

Proof techniques
In the remainder of the introduction, we sketch the techniques used to obtain Theorems 1.3 and 1.2,
which together imply Theorem 1.1.
Theorem 1.3: Rank of the matchings connectivity matrix
To prove Theorem 1.3, we give two different lower bounds on the rank of Mk : One is relatively
simple and contained in Section 3. For this bound, we first explicitly compute the rank of small
matching connectivity matrices and then use a product construction to give lower bounds for larger
orders. While the resulting bound is loose, it also applies to the rank of Mk over Zp for prime p 6= 2,
whereas our more sophisticated main bound does not. In particular, we can use the bound to show
that the rank of Mk over Z3 and other primes is asymptotically larger than the rank over Z2 .
Our main result however concerns the rank of Mk over Q, which we establish to be 4k up to
polynomial factors in Section 4. To this end, we build upon representation-theoretic techniques that
were also used in Raz and Spieker’s bound [33] for the bipartite version of Mk , and which we first
survey briefly: A hook partition λ of some number k ∈ N is a number partition with the particular
form (t, 1, . . . , 1) for some t ≤ k. One can view λ as a Ferrers diagram, which is a left-adjusted
diagram made of cells, as shown in Figure 4a. A standard Young tableau of shape λ is a labeling of
this diagram with numbers from [k] such that the numbers are strictly increasing in each row and
each column, see Figure 4b. Raz and Spieker showed that the rank of the bipartite variant of M2k
can be expressed as a weighted sum over all hook partitions λ of k, where each λ is weighted by the
squared
to the central binomial coefficient
 number of Young tableaux of shape λ. This sum simplifies
2k−2
k
k−1 , showing that the bipartite variant of Mk has rank Θ(2 ), up to polynomial factors.
To address the non-bipartite setting, we found ourselves in need of additional techniques from
algebraic combinatorics that were not present in Raz and Spieker’s original bound, such as the
perfect matching association scheme [14] and zonal spherical functions [29]. With these at hand, we
2

To avoid (or add) confusion, let us stress that we consider three matrices related to the Hamiltonian cycle problem:
The matchings connectivity matrix Mk , the connection matrix Ck for the number of Hamiltonian cycles, and the
fingerprint matrix Hk for Hamiltonian cycles. We will revisit their differences in Section 2. While these matrices are
closely related, our arguments benefit from using different matrices for different proofs.

5

C1
x1 , x2

C2

C3

C4

β

x3 , x4

x5 , x6
Fig. 2: A block propagation scheme for n = 6 variables, m = 4 clauses, variable block size γ = 2,
and row pathwidth β = 3. The q = n/γ = 3 variable blocks correspond to rows. Assignments
to blocks are propagated from left to right. Clauses correspond to columns and clause
satisfaction is propagated downwards.
prove that the rank of M2k can be lower-bounded by a similar sum over number partitions λ as in
the bipartite case, this time however ranging over domino hook partitions λ, which have the form
(2t, 2t, 2, . . . , 2) for some t ≤ k. As in the bipartite case, we then observe that this sum simplifies
significantly, this time however to (essentially) a product of two consecutive Catalan numbers. This
entails a lower bound of 4k for the rank of Mk , up to polynomial factors. It then follows easily from
the upper bound in the bipartite setting that this bound is tight up to polynomial factors.
Theorem 1.2: SETH-hardness via assignment propagation
To describe how we turn lower bounds on the rank of Mk into algorithmic intractability results
for #HC under SETH, let us first survey the general construction from [24], which we dub a block
propagation scheme: Given a CNF-formula ϕ with n variables, such a scheme produces an equivalent
instance I of the target problem with parameter value k ≤ cn for some constant c ≤ 1. An algorithm
with running time O∗ ((21/c − ε)k ) for the target problem would then refute SETH, as it would imply
a O∗ ((2 − ε)n ) time algorithm for CNF-SAT.
The constructed target instance I has the outline sketched in Figure 2: The n variables of ϕ
are grouped into q = dn/γe blocks of constant size γ ∈ N, where γ depends only on the  in the
running time we wish to rule out. The variable blocks are represented as rows, each propagating
an assignment of type {0, 1}γ using a thin graph of pathwidth β ∈ N. Specifically, an assignment
{0, 1}γ is represented as the type of a partial solution for the target problem on a β-boundaried
graph (e.g., as a partial coloring of the boundary, or in our case, as a fingerprint of a Hamiltonian
cycle.) The relationship between β and γ is important in this construction: Intuitively, if we can
choose β small for large γ, then the target problem has a large “combinatorial capacity” in the
sense that it allows us to pack assignments to large blocks into thin wires.
In a block propagation scheme, the clauses of ϕ are then represented as columns; the column
corresponding to clause C checks whether the overall assignment of type {0, 1}n propagated by the
rows satisfies C. To this end, one can use cell gadgets, which are graphs with β left and β right
interface vertices, and c additional top/bottom interface vertices, where c ∈ N depends only on
the target problem. The cell gadget is placed at the intersection of a row and a column, and it
needs to “decode” an assignment x ∈ {0, 1}γ from the state of the left β interface vertices, decide

6

whether x satisfies the clause, and “encode” x back into the state of right β vertices. The top and
bottom interface is used to propagate, from the top of a column downwards, whether the respective
clause is already satisfied by the partial assignments to the blocks above a given cell. Due to the
grid-like construction, the overall pathwidth of the instance I is usually easily seen to be bounded
by βq + O(1), where the additive constant accounts for the size of cell gadgets.
The main technical effort in these reductions lies in constructing the cell gadget, and this
usually subsumes constructing a “state tester”, a gadget that tests whether, in a solution to I,
the β left/right interface vertices are in a particular state S (say, a particular partial coloring, or
a particular fingerprint of a Hamiltonian cycle). This requires constructing a graph that can be
extended to a solution of the target instance iff the β relevant vertices are in state S, and for various
problems, such constructions can be achieved with some effort. In the case of #HC, we face the
situation that testers for fingerprints of Hamiltonian cycles do not exist: There are fingerprints S
such that any graph that extends S to a Hamiltonian cycle also extends some unwanted fingerprints
S 0 6= S. Our main insight here is that this problem can be solved by firstly restricting to a set of 6β
good fingerprints that induce a full-rank submatrix F of the fingerprint matrix Hβ , and secondly
simulating a “linear combination” of testers, with coefficients obtained from the inverse of F. In
the fingerprint tester for S, other fingerprints S 0 6= S will have extensions of non-zero weight, but
the weights of these extensions are chosen in such a way (depending on F−1 ) that extensions of
S 0 6= S cancel out. (A similar idea was used before to obtain conditional lower bounds for the
complexity of permanents [10].) This allows us to simulate a state tester for fingerprints, and the
use of cancellations also shows why this lower bound
works only for #HC and not for HC—which
√
is fortunate, since HC does admit an O∗ ((2 + 2)pw ) time algorithm.

2

Preliminaries and notation

If ϕ is a CNF-formula, and x is a (partial) assignment to its variables, we write x |= ϕ to denote
that x satisfies ϕ. For integers n, we let [n] = {1, . . . , n}. All graphs in this paper will be undirected.
If G = (V, E) is a graph, v ∈ V is a vertex and X ⊆ E is an edge set, we let dX (v) denote the
number of edges in X that are incident to v. We write M2n for the set of all perfect matchings of
the complete graph K2n .
Strong Exponential Time Hypothesis: As formulated by Impagliazzo and Paturi [19], the complexity assumption SETH states that for every ε > 0, there is a constant k such that k-CNF-SAT
(the satisfiability problem for k-CNF formulas on n variables) cannot be solved in time O∗ ((2 − ε)n ).
It is common to state this hypothesis as ruling out even randomized algorithms, making it slightly
stronger. A result from Calabro et al. [9, Theorem 1] gives a randomized reduction from k-CNF-SAT
to the problem UNIQUE-k-CNF-SAT, where the k-CNF formula is guaranteed to have at most
one satisfying assignment. This allows us to assume that the k-CNF formulas in the statement of
(randomized) SETH have at most one satisfying assignment.
Pathwidth: A path decomposition of a graph G = (V, E) S
is a path P in which each node x has an
associated set of vertices Bx ⊆ V (called a bag) such that x Bx = V and the following holds:
1. For each edge {u, v} ∈ E there is a node x in P such that u, v ∈ Bx .
2. If v ∈ Bx ∩ By then v ∈ Bz for all nodes z on the (unique) path from x to y in P.
7

The width of P is the size of the largest bag minus one, and the pathwidth of a graph G is the
minimum width over all possible path decompositions of G. A path decomposition starts in L if the
first bag contains L and ends in R if the last bag contains R.
Since our focus here is on path decompositions, we only mention in passing that the related
notion of treewidth can be defined in the same way, except for letting the nodes of the decomposition
form a tree instead of a path.
0

0

Kronecker products: Given a field F and two matrices A ∈ Fn×m and B ∈ Fn ×m , the Kronecker
0
0
product A ⊗ B is a matrix in Fn·n ×m·m . Its rows can be indexed by pairs (i, i0 ) ∈ [n] × [n0 ], and
similarly for columns. The entry of A⊗B at row (i, i0 ) and column (j, j 0 ) is defined as A[i, j]·B[i0 , j 0 ].
For t ∈ N, the t-th Kronecker power of A is the t-fold product A⊗t = A ⊗ . . . ⊗ A, and we consider
its rows and columns to be indexed by [n]t and [m]t respectively.
If A and B each have full rank over F, then so does A ⊗ B. Note that this requires F to be a
field; it would fail if F contained zero divisors. For our purposes of computing the rank of matrices
over Zp , this means we require p to be prime.
Fingerprints: The HC-fingerprints (which we often abbreviate as fingerprints) capture the states
of the natural dynamic program for Hamiltonian cycles:
Definition 2.1 (Fingerprint, Partial Solutions). Let G = (V, E) be a graph and let B ⊆ V , where
B is the set of ‘boundary vertices’. A fingerprint on B is a pair (d, M ) where d ∈ {0, 1, 2}B and M
is a perfect matching on d−1 (1). A partial solution in G for (d, M ) is an edge set H ⊆ E such that
(i) dH (v) = 2 for every v ∈ V \ B, (ii) dH (v) = dv for every v ∈ B, and (iii) if (u, v) ∈ M then u
and v are the endpoints of the same path of H.
Two fingerprints (d, M ) and (d0 , M 0 ) on B combine (or match) if dv + d0v = 2 for every v ∈ B
and M ∪ M 0 forms a single cycle or is empty.
Variants of connection matrices: Our paper studies three related matrices that describe the
behavior of Hamiltonian cycles under separators. We recall their definitions here for reference:
Mk , the k-th matchings connectivity matrix: This binary matrix is indexed by perfect matchings
M, M 0 ∈ Mk , and Mk [M, M 0 ] is 1 iff M ∪ M 0 is a single cycle. This matrix appears naturally
in our rank lower bounds.
Hk , the k-th fingerprint matrix (for Hamiltonian cycles): This binary matrix is indexed by all fingerprints (d, M ) on a fixed set B of size k. An entry Hk [f, f 0 ] equals 1 iff f and f 0 combine.
This matrix will be crucially used in the algorithmic lower bound.
Ck , the k-th connection matrix (for the number of Hamiltonian cycles): This integer-valued matrix
is indexed by all k-boundaried graphs, and hence infinite. The entry Ck [G, G0 ] counts the
Hamiltonian cycles in the graph G ⊕ G0 . (If an edge between boundary vertices is present in
both G and G0 , we count it twice in G ⊕ G0 .) This matrix will not be used in later sections,
but we still mentioned it to connect to the established literature on connection matrices.
The subscript k is omitted when clear from the context. As we show below, we can easily transform
rank bounds for Mk into bounds for Hk and Ck , thus justifying our focus on the rank of Mk :

8

Fact 2.2. If p is a polynomial such that rank(Mk ) ≥ ck /p(k), then rank(Hk ) ≥ (2 + c)k /q(k) for
some polynomial q.
Proof. Subject to proper indexing, the matrix Hk is a block-antidiagonal matrix that has a block for
every vector d ∈ {0, 1, 2}k , since fingerprints with degree functions d, d0 not satisfying d(v)+d0 (v) = 2
for all v cannot match. Therefore, we obtain:
rank(Hk ) ≥

X
|d−1 (1)|=i
i even

 
k  
1
k
1X k
k−i
·2
· rank(Mi ) ≥
· 2k−i · ci /p(i) ≥ (2 + c)k /q(k),
i
k
i
k
i=1

where q is a polynomial satisfying p(i) ≥ q(i) for i = 1, . . . , k, and the last inequality follows from
the binomial theorem. The upper bound follows similarly.
Furthermore, a simple argument shows that the fingerprint matrix Hk and the connection matrix
Ck actually have the same rank.
Fact 2.3. For every k ∈ N, the matrices Hk and Ck have the same rank.
Proof. We first show that rank(Ck ) ≥ rank(Hk ) by finding Hk as a submatrix of Ck . To this end,
we construct a k-boundaried graph GF for every k-fingerprint F and then find Hk as the submatrix
induced by these graphs. Given F , the graph GF is constructed as follows: At first, it contains
only the boundary vertices 1, . . . , k. Then we add an arbitrary partial solution for F to GF . For
instance, if F = (d, M ) and M is non-empty, pick the lexicographically first edge of the matching M ,
say ij ∈ M , and connect i to j in GF with a path that passes through all vertices in d−1 (2) in an
arbitrary order. Then add all edges in M \ {ij} to GF as edges. If M is empty, add a Hamiltonian
cycle on d−1 (2). Finally, subdivide all edges of the graph; this adds some number of subdivision
vertices to GF , which we consider not to be part of the boundary. Note that the degree of boundary
vertex i ∈ [k] in GF is precisely d(i).
Given two k-fingerprints F, F 0 , we observe that any Hamiltonian cycle in GF ⊕ GF 0 uses all
edges of the graph, as every edge is incident to a (subdivision) vertex of degree 2. This implies,
firstly, that the number of Hamiltonian cycles in GF ⊕ GF 0 is either 0 or 1. Secondly, it implies
that dF + dF 0 needs to be the constant 2-function for GF ⊕ GF 0 to have a Hamiltonian cycle. If this
condition is fulfilled, then by construction, GF ⊕ GF 0 has a Hamiltonian cycle iff M ∪ M 0 forms a
single cycle. Summarizing, we have that Ck [GF , GF 0 ] ∈ {0, 1} and that Ck [GF , GF 0 ] > 0 iff F and
F 0 match. This shows that the set of k-boundaried graphs GF , for k-fingerprints F , induce the
fingerprint matrix Hk as a submatrix in Ck , and the lower bound on the rank of Ck follows.
For the upper bound of rank(Ck ) ≤ rank(Hk ), we find a matrix Ak such that Ck = Ak · Hk · ATk .
The rows of Ak are indexed by k-boundaried graphs G, the columns are indexed by fingerprints F ,
and we define Ak [G, F ] to count the partial solutions in G for the fingerprint F .
Given two k-boundaried graphs G and G0 , every Hamiltonian cycle C in G ⊕ G0 induces a
partial solution in each of G and G0 , for fingerprints F and F 0 , respectively. The pair of fingerprints
PC = (F, F 0 ) can be determined uniquely from the partial solutions of C, and since C is a Hamiltonian
cycle, it follows that F and F 0 match. Given a matching pair of fingerprints (F, F 0 ), the number of
Hamiltonian cycles of G ⊕ G0 with PC = (F, F 0 ) is precisely Ak [G, F ] · Ak [G0 , F 0 ], as the extensions
in each of G and G0 can be chosen independently, provided they agree with F and F 0 respectively.

9

We conclude that the number of Hamiltonian cycles in G ⊕ G0 can be expressed as
X
Ak [G, F ] · Ak [G0 , F 0 ] = (Ak · Hk · ATk )[G, G0 ].
F,F 0
match

It follows that Ck = Ak · Hk · ATk as claimed, establishing the upper bound on the rank.

3

A simple rank lower bound

Before showing our main lower bound on the rank of the matchings connectivity matrix Mk in
Section 4, we first establish the second part of Theorem 1.3; this turns out to be somewhat simpler.
Let p 6= 2 be a fixed prime. To obtain the lower bound on the rank of Mk over Zp , we proceed
in two steps: First, we use a computer program to compute, for a small constant B ∈ N, the rank
of MB over Zp . Then we use a product construction to amplify this initial rank to a lower bound
on the rank of MtB for t ∈ N.

3.1

The initial matrix

We choose B ∈ N maximally such that MB can still be computed, e.g., by the MATLAB script
provided in the ancillary files. If the rank of MB over Zp is r, then the symmetry of MB implies
the existence of a set I of perfect matchings in KB such that the submatrix F = MB [I, I] has full
rank over Zp . Our computations enable the following choices:
Lemma 3.1. For any prime p ∈
/ {2, 3}, the matrix M10 has (full) rank 945 over Zp . Furthermore,
the matrix M12 has rank 3618 over Z3 , rank 9890 over Z5 , and rank 9933 over Zp for p ∈ {7, 11, 13}.
Proof. The dimensions of M10 are 945 × 945. Our calculations show that the determinant of M10
is non-zero and contains only the prime factors 2 and 3. It follows that M10 has full rank over Zp
for any prime p ∈
/ {2, 3}. Over Z3 , the rank of M10 is found to be 567, but we will obtain a better
bound by going to M12 , a matrix of dimensions 10395 × 10395, where the claimed rank bounds can
be obtained by calculation.
For concreteness, we illustrate our approach in the next subsections with M6 as initial matrix, see
Figure 1, and revisit the better choices provided in Lemma 3.1 at the end of the proof. Calculation
shows that det(M6 ) = −217 , so M6 has full rank over Zp for primes p 6= 2, and we can choose a set
I of size 15 to get a full-rank matrix F = MB [I, I]. Already B = 6 gives a lower bound on the
rank of Mn over Zp with p 6= 2 that is higher than the rank over Z2 .

3.2

Amplification via Kronecker products

After having obtained F = MB [I, I], we then “tensor up” this matrix to obtain rank lower bounds
on MtB for t ∈ N: To this end, we find the Kronecker power F⊗t , which is a full-rank matrix of
dimensions |I|t × |I|t , as a submatrix of MtB . It follows that rank(Mn ) ≥ Ω(|I|n/B ) whenever n is
divisible by B. For B = 6, this yields rank(Mn ) ≥ Ω(15n/6 ) = Ω(1.57n ) over Zp when p 6= 2.
(t)
To proceed, it will be useful to define a particular graph KB on tB vertices for each t ∈ N, which
(t)
can be viewed as a subgraph of KtB . Only perfect matchings contained in KB will be relevant.
The graph consists of t disjoint copies of KB and “patch edges” between adjacent KB -copies that
will be used to combine solutions of the individual KB -copies to a global solution.
10

v11

v31

v21

(t)

Fig. 3: The graph KB for B = 6 and t = 3. Each gray block represents a copy of K6 . Patch
edges are drawn with light gray lines; the figure wraps around. Each K6 -copy shows a row
matching (green) and a column matching (blue). The special vertex vi1 in the i-th copy is
drawn red, and the edge incident with vi1 in the column matching is dotted. After deleting
the dotted edges, we can choose patch edges, depending only on the column matching, so as
(t)
to obtain a Hamiltonian cycle of KB .
(t)

Definition 3.2. Let B ∈ N be fixed. For t ∈ N, let KB be obtained as follows, see also Figure 3:
1. Take t disjoint copies of KB and denote the vertices of copy i ∈ [t] by vi1 , . . . , viB .
1 , interpreting t + 1 as 1. These
2. For each i ∈ [t] and j ∈ [t] \ {1}, add an edge from vij to vi+1
are the patch edges.
(t)

The perfect matchings of KB contain a particular subset I t of size |I|t that is essentially the
t-th power of I; this set will be the row set of the full-rank submatrix we wish to find in MtB . The
elements of I t are disjoint unions of perfect matchings, one for each KB -copy.
Definition 3.3. Given a tuple N = (N1 , . . . , Nt ) ∈ I t , for t ∈ N, we define a perfect matching MN
(t)
of the graph KB by
MN = {{via , vib } | i ∈ [t] and {a, b} ∈ Ni }.
We write I

t

= {MN | N ∈ I t } for the perfect matchings that can be obtained from I t this way.

It remains to find an appropriate column set of perfect matchings. Note that we cannot reuse
I t for this purpose: If t ≥ 2, the union of any two perfect matchings in I t is disconnected, and
therefore MtB [I t , I t ] contains only zeroes.
We do however obtain a suitable column set, which we denote by I :t , by using the patch edges
(t)
of KB : Each perfect matching in I :t is obtained from some M ∈ I t by deleting one particular
edge from each KB -copy, and patching the resulting isolated vertices to adjacent KB -copies.
:
Definition 3.4. Given a tuple N = (N1 , . . . , Nt ) ∈ I t , for t ∈ N, we define a perfect matching MN
(t)
of the graph KB :

1. Start with the perfect matching MN .
r(i)

2. For i ∈ [t], let r(i) denote the neighbor of 1 in Ni . Delete the edge from vi1 to vi
rendering these two vertices isolated.
r(i)

3. For i ∈ [t], include the patch edge from vi

11

1 . (Consider t + 1 = 1 here.)
to vi+1

in MN ,

:
We then define I :t = {MN
| N ∈ I t }.
(t)

:
It is easily seen that MN
is indeed a perfect matching of the graph KB , for each N ∈ I t : We
r(i)
started with the perfect matching MN , then reduced the degree of vi1 and vi to 0 for all i ∈ [t],
and then increased these degrees back to 1 in the third step. No other degrees were affected.
Having defined our rows I t and columns I :t , we proceed to study the submatrix MtB [I t , I :t ].
Note that both I t and I :t correspond bijectively to I t , so the indexing of MtB [I t , I :t ] already
puts this matrix close to the t-th Kronecker power of F. Its content also does not fail us:

Lemma 3.5. Identifying I

t

and I :t each with I t in the natural way, we have MtB [I

t , I :t ]

= F⊗t .

Proof. Given R, C ∈ I t with R = (R1 , . . . , Rt ) and C = (C1 , . . . , Ct ), let H = MR ∪ MC: be the
(t)
union of its corresponding perfect matchings. We observe that H is a Hamiltonian cycle (in KB ) if
and only if Ri ∪ Ci is a Hamiltonian cycle (in KB ) for each i ∈ [t]:
In the “if” direction, note that H is the result of deleting one edge each from t Hamiltonian
cycles, then adding edges between the endpoints of the resulting Hamiltonian paths so as to obtain
(t)
a Hamiltonian cycle in KB .
In the “only if” direction, note that the restriction of H to the i-th KB -copy for i ∈ [t] is a
Hamiltonian path between the vi1 and some neighbor. By adding back the edge between vi1 and its
neighbor and deleting the patch edges, we obtain a Hamiltonian cycle in each copy of KB .
The claim then follows from the definition of F = MB [I, I] and the Kronecker product.
Since F has full rank over Zp and p was required to be prime, the Kronecker power F⊗t also has
full rank, so we obtain:
Corollary 3.6. The matrix MtB [I
over Zp is at least |I|t .

t , I :t ]

has full rank over Zp . Consequently, the rank of MtB

In conclusion, by using F = M6 , we obtain that, for prime p 6= 2, the rank of Mn over Zp is at
least Ω(15n/6 ) = Ω(1.57n ). Using the larger initial matrices provided by Lemma 3.1, we obtain the
following stronger bounds:
Theorem 3.7. For prime p, the rank of Mn over Zp is at least
Ω(945n/10 ) = Ω(1.984n )

if p ∈
/ {2, 3},

Ω(3618n/12 ) = Ω(1.979n )

if p = 3,

Ω(9890n/12 ) = Ω(2.152n )

if p = 5,

Ω(9933

n/12

n

) = Ω(2.153 )

if p ∈ {7, 11, 13}.

The bounds can be improved by using larger initial matrices F, but we hit our computational
limit with the 10395 × 10395 matrix M12 . For this matrix, we could no longer compute determinants
of the relevant submatrices to determine their prime factors, but we could still compute the rank of
M12 for primes up to 13, thus obtaining the last three entries in Theorem 3.7.

4

The rank of the matchings connectivity matrix over the rational numbers

In this section we establish the first part of Theorem 1.3. For this we need some basics on the
representation theory of the symmetric group which we first briefly outline.
12

1 3 5 8
2 4 6
7
9
(a) Ferrers Diagram

· ·
· ·

(c) The partition (4, 3, 12 )
is not a hook

(b) Young Tableau

7 4 3 1
5 2 1
2
1
(d) Hook lengths

Fig. 4: Illustrations of basic notions from the representation theory of the symmetric group

4.1

The Representation Theory of the Symmetric Group

The representation theory of the symmetric group Sn is remarkable, as much of it may be explained
via the combinatorics of integer partitions and tableaux. We outline the relevant combinatorial
aspects of the theory, leaving the algebraic basics of finite group representation theory for Appendix B.
The reader is referred to [34] for a gentle but more thorough introduction.
P
Let λ = (λ1 , λ2 , · · · , λk ) ` n such that λ1 ≥ λ2 ≥ · · · ≥ λk and ki=1 λi = n denote an integer
partition of n. If j parts of the integer partition have the same size m, then we express them by
the shorthand mj . Let λ(n) denote the number of integer partitions of n. It is well-known that
there is a one-to-one correspondence between the irreducible representations of Sn and the integer
partitions of n. We let [[λ]] denote the irreducible representation of Sn corresponding to λ ` n.
For an integer partition λ ` n, the Ferrers diagram of λ is an associated left-justified tableau
that has λi cells in the ith row. Abusing notation, we let λ also refer the Ferrers diagram of λ ` n.
In Figure 4a the Ferrers diagram for (4, 3, 12 ) ` 9 is illustrated.
We obtain a standard Young tableau from a Ferrers diagram by labeling its cells with numbers
such that the numbers along each row are strictly increasing, and the numbers along each column
are strictly increasing. In Figure 4b a standard Young tableau of shape (4, 3, 12 ) is shown.
Let f λ denote the number of standard Young tableaux of shape λ ` n. There is an elegant
combinatorial formula for expressing f λ .
We say that a tableau λ covers a tableau µ if the cells of µ are contained in the cells of λ. A
hook is a tableau of shape (k, 1` ), equivalently, a tableau that does not cover the shape (22 ). The
partition (4, 3, 12 ) is not a hook, as it covers (22 ), illustrated in Figure 4c.
For each cell c ∈ λ of a Ferrers diagram, say at row i and column j, if we take c along with all
cells in row i to the right of c, and all cells in column j that lie below c, we obtain a hook (k, 1` ) for
some k, ` ∈ N. Let h(c) := k + ` denote the number of cells in this hook, the so-called hook length.
In Figure 4d, we have annotated each cell with its corresponding hook length. The following result
connects hook lengths with enumerating standard Young tableaux.
Theorem 4.1 (Hook Theorem [34]). f λ =

Q n!
c∈λ

h(c) .


For instance, it is easy to see using the hook formula that f λ = n−1
for any hook λ = (n−`, 1` ) ` n.
`
A classic result in the representation theory of the symmetric group Sn is that f λ equals the dimension
of the irreducible [[λ]] corresponding to λ.
Proposition 4.2 (Dimensions of Irreducibles of Sn [34]). f λ = dim[[λ]].

13

4.2

Relating rank to the number of Young tableaux

We proceed by studying M := Mk where we let k = 2n. Let A, B be a partition of the vertices of
K2n into two parts of size n. Consider the sub-matrix M0 of M induced by the perfect matchings of
K2n that are also bipartite perfect matchings with respect to the bipartition A, B. In [33], Raz and
Spieker show that the eigenspaces of M0 are in fact irreducible representations of Sn , and that the
eigenspaces corresponding to nonzero eigenvalues of M0 correspond to the hooks of length n. This
result paired with some elementary combinatorics implies the following theorem.
Theorem 4.3 (Raz & Spieker [33]).
0

rank(M ) =



2n − 2
(f ) =
.
n−1

X

λ 2

λ`n

λ does not cover (22 )


Since there are 12 2n
to partition V (K2n ) into two parts A, B of size n, this already gives an
2 ways
 
1 2n−2 2n
upper bound of 2 n−1 n on the rank of M. We will show this is almost tight.3 One of our key
technical theorems is the following exact formula for the rank of M.
Theorem 4.4. For any λ ` n, let us write 2λ = (2λ1 , 2λ2 , · · · , 2λk ) ` 2n. Then
X
rank(M) =
f 2λ .
λ`n

λ does not cover (23 )

This result can be seen as the non-bipartite analogue of Theorem 4.3. To prove it, we determine the
nonzero eigenvalues of M; however, this will require a fair amount of algebraic combinatorics, which
we now develop.
Let Hn denote the hyperoctahedral group of order n, equivalently, the group of permutations
σ ∈ S2n such that
{{σ(1), σ(2)}, {σ(3), σ(4)}, · · · , {σ(2n − 1), σ(2n)}} = {{1, 2}, {3, 4}, · · · , {2n − 1, 2n}}.
It is well-known that the set of perfect matchings of K2n can be written as M2n := S2n /Hn . Even
though S2n /Hn is not a group, these cosets possess a remarkable amount of algebraic structure.
Let R[M2n ] be the vector space of real-valued functions over perfect matchings, equivalently, the
space of real-valued functions over S2n that are Hn -invariant, that is, f (σ) = f (σh) ∀σ ∈ S2n , h ∈
Hn . In [36], Thrall showed this vector space admits the following decomposition into irreducible
representations of S2n .
L
Theorem 4.5 (Thrall ’42). R[M2n ] = λ`n [[2λ]].
A consequence of Thrall’s result is that M2n admits a symmetric association scheme, the so-called
perfect matching association scheme [14, Section 15.4].
Definition 4.6 (Symmetric Association Scheme). A collection of binary m×m matrices A0 , A1 , · · · , Ad
is a symmetric association scheme if the following axioms are satisfied.
3
Moreover, it can be verified experimentally that for some constant n the rank of M is strictly smaller than this
bound, but lower order terms will not be relevant for us.

14

1. A0 = I where I is the identity matrix.
Pd
2.
i=0 Ai = J where J is the all-ones matrix.
3. Ai = ATi for all i ∈ {1, 2, · · · , d}.
4. Ai Aj is a linear combination of A0 , A1 , · · · , Ad for all 0 ≤ i, j ≤ d.
5. Ai Aj = Aj Ai for all 0 ≤ i, j ≤ d.
We refer the reader to [3, 14] for a more thorough treatment of association schemes.
Recall that the union of any two perfect matchings is a disjoint union of cycles, which can be
represented by an integer partition of the form 2λ ` 2n where 2λ = (2λ1 , 2λ2 , · · · , 2λk ) for some
λ ` n. The perfect matching association scheme is simply the collection of M2n × M2n matrices
A := {Aλ }λ`n defined such that (Aλ )ij = 1 if i ∪ j ∼
= 2λ, and 0 otherwise.
Proposition 4.7. M ∼
= A(n) .
Since A is a symmetric association scheme, the eigenspaces of the Aλ ’s coincide, and are precisely
the irreducibles in the decomposition given by Thrall [14, Section 15.4]. In light of this, we can
take the distinct eigenvalues of these matrices as column vectors and collect them in a λ(n) × λ(n)
matrix P . For example, when n = 4, we have A = {A(4) , A(3,1) , A(2,2) , A(2,12 ) , A(14 ) }, and

P =

(4)



(3,1)







(2,2)
(2,12 )
(14 )

(4)

(3,1)

(2,2)

(2,12 )

(14 )

48
−8
−2
4
−6

32
4
−8
−2
8

12
−2
7
−2
3

12
5
2
−1
−6

1
1
1
1
1




.



For any λ ` n, we call Ωλ := {m ∈ M2n : m ∪ m∗ ∼
= 2λ} the λ-sphere, where
m∗ = {{1, 2}, {3, 4}, · · · , {2n − 1, 2n}}.
The following lemma gives a simple way to determine their size.
Lemma 4.8 ([23]). Let l(λ) Q
denote the number of parts of λ ` n, mi denote the number of parts of
λ that equal i, and set zλ := i≥1 imi mi !. Then
|Ωλ | =

2n n!
.
2l(λ) zλ

Note that the first row of P lists the sizes of the respective spheres. This is no coincidence, as each
Aλ has constant row sum |Ωλ |, and so its largest eigenvalue is |Ωλ | respectively [15]. It is known
that the entries of P are determined by the zonal spherical functions [29, Chapter VII], which can
be thought of as an analogue of irreducible characters in our association scheme setting.
Theorem 4.9 ([29]). Let ηλ be the eigenvalue of A(n) associated with the λ-eigenspace. Then
(n)

ηλ = |Ωλ |ωλ .
15

A result of Diaconis and Lander is the following explicit formula for determining the value of the
zonal spherical function ωλ evaluated on perfect matchings m ∈ Ω(n) .
Lemma 4.10 (Diaconis & Lander [29]). For any cell c ∈ λ ` n, let w(c) denote the number of cells
on the same row as c that lie strictly to the left of c, and let n(c) denote the number of cells on the
same column as c that lie strictly above c. Then
X
1
(n)
(2w(c) − n(c)),
ωλ = n−1
2
(n − 1)!
c∈λ

c6=(1,1)

where the sum runs over all cells except for the northwest-most cell (1, 1). In particular, we have
(n)
ωλ = 0 if and only if λ covers (23 ).
We are now in a position to prove Theorem 4.4.
Proof of Theorem 4.4. By Proposition 4.7, we have M = A(n) . Theorem 4.9 and Lemma 4.10
together imply that nonzero eigenvalues of M do not cover (23 ). Lemma 4.8 implies that spheres
are nonempty, thus these are precisely the nonzero eigenvalues of M. By Proposition 4.2 and
Theorem 4.5, the dimension of the eigenspace corresponding to ηλ is f 2λ , completing the proof.

4.3

Counting Young tableaux

Our combinatorial formula for the rank of the matchings connectivity matrix does not seem to
admit any particularly revealing closed-form; nevertheless, we can still get a good lower bound
on its rank. We say that 2λ ` 2n such that λ ` n is a domino hook if λ = (k, k, 1n−2k ) for some
0 ≤ k ≤ n. For example,

is the Ferrers diagram of the domino hook 2(4, 4, 15 ). Note that if 2λ ` 2n is a domino hook, then
λ does not cover (23 ). Using WZ-theory [32], Regev showed that the number of standard
Young

2n
1
tableaux of domino hook shape admits an elegant count. Recall that Cn = n+1
is
the
nth
n
√ 3/2
n
Catalan number, and that limn→∞ ((4 / πn )/Cn ) = 1, see [35].
Theorem 4.11 (Regev [2]).
X

Cn−1 Cn =

f 2λ .

2λ`2n

2λ domino hook

Now we can combine all work and finish the proof:
Proof of Theorem 1.3, first part. We have by Theorem 4.4 that
X
X
rank(Mn ) =
f 2λ ≥
f 2λ = Cn−1 Cn ≥ 4n /n3 ,
λ`n

λ does not cover (23 )

2λ`2n

2λ domino hook

where the inequality follows because if 2λ ` 2n is a domino hook, then λ does not cover (23 ).
16

Note that by the aforementioned upper bound of

5

1 2n−2
2 n−1



2n
n



, the lower bound is almost tight.

The reduction

This section is devoted to the proof of Theorem 1.2. We will show the following stronger lemma:
Lemma 5.1. Let p be prime and let rp ∈ R be such that logrp (rankp (Mk ))/k → c, where c ≥ 1, as
even k tends to infinity. Suppose that #HC modulo p on graphs with given path decomposition of
width pw can be solved in O∗ ((2 + rp − ε)pw ) time, for some ε > 0. Then there is an O∗ ((2 − ε0 )n )
time algorithm that counts the satisfying assignments of a given a CNF-formula on n variables
modulo p, for some ε0 > 0 depending on ε.
Lemma 5.1 is a generalization of Theorem 1.2 as in SETH we can without loss of generality
assume the number of satisfying solutions is at most one as mentioned in Section 2, so for the
decision version we can simply check whether the modular count equals 1 or not. Lemma 5.1 will be
used to prove Theorem 1.2. It should be noted that many of the gadgets used in the non-innovative
parts of this section are heavily based on the lower bound for the decision version from [11].

5.1

Illustrated outline of proof.

Before describing the reduction in detail, we first give an illustrated outline. For this, a basic
understanding of previous block propagation schemes as outlined in Section 1 will be advantageous.
We start with a high level description of the statement of Lemma 5.2. The 2n assignments of the
variables of the given CNF-formula ϕ are encoded by fingerprints that form a basis in the matrix
Hk . The larger such a basis, the more assignments one can encode for fixed k. Lemma 5.2 asserts
the existence of a certain graph G in which the number of partial solutions of a given fingerprint
equals 0 if the fingerprint encodes an assignment not satisfying ϕ and a fixed positive quantity
(depending on the fingerprint) otherwise. The boundary vertices L and R are partitioned into blocks
and the fingerprints will also have some block-structure for technical reasons reminiscent to the
block-propagation scheme. Confer the statement of Lemma 5.2 for the precise details.
In Figure 5a, we illustrate how the graph output by the reduction implied by Lemma 5.1 is
obtained from the graph G obtained by Lemma 5.2: The blocks GiL and GiR (whose unions we jointly
denote by GL respectively GR ) are added to G, where GiR has vertex set Ri common with G, and
GiL has vertex set Li common with G. Additionally, graphs GiL and Gi+1
L share a common vertex bi .
By Lemma 5.2, the graph G has A[fL , fR ] partial solutions for fingerprints fL and fR . The graph
GL has lf fingerprints and rf 0 fingerprints such that lT Ar equals the number of satisfying solutions
of ϕ modulo p. To establish this, for each fingerprint, certain partial solutions are allowed such that
two edgesets avoid creating subcycles only if they have combining fingerprints on L (or R). The
structure of the partial solutions is tailored so that combinations of partial solutions with combining
fingerprints can be extended in one (modulo p) way into a Hamiltonian cycle. For the latter part,
the vertices bi are used to connect parts from the subgraphs GiL . In Figure 5a, the edges present
in all partial solutions are displayed everywhere (where dashed edges will actually be redirected
to visit vertices with degree 0 or 2 in a fingerprint), and on the vertices Li ∪ Ri , a possible partial
solution in GiL , G, GiR is displayed. The edges li,1 li,2 and ri,1 ri,3 in G are rerouted to avoid creating
two subcycles if two matchings give exactly one cycle. If the fingerprint in both G1L and G1R matches
with that in G, l1,1 will be connected to r1,1 and l1,2 will be connected to r1,2 .

17

G1L

l1,1

r1,1

l1,2

r1,2

l1,3

r1,3

l1,4

r1,4

l1,5

r1,5

l1,1

l1,6

r1,6

l1,2

G1R

t1

b1

bq

G2L

l1,3
l2,1

r2,1

l2,2

r2,2

l2,3

r2,3

l2,4

r2,4

l2,5
l2,6

G

r1,1
r1,2

G1

r1,4

l1,4
t2

r2,1

l2,1

G2R

r2,2

l2,2

r2,5

l2,3

r2,6

l2,4

G2

r2,3
r2,4

t3

b2

r3,1

l3,1

bq−1
lq,1

GqL

r1,3

rq,1

lq,2

rq,2

lq,3

rq,3

lq,4

rq,4

lq,5

rq,5

lq,6

rq,6

l1,1

r1,1

s1,1

l1,2

r1,2

s1,2

l1,3

r1,3

s1,3

r3,2

l3,2
l3,3

G3

r3,3
r3,4

l3,4
t4

l1,4

r1,4

s1,4

l1,5

r1,5

s1,5

l1,6

GqR

(a) From Lemma 5.2 to Theorem 1.2

G1L

r1,6

G2R

s1,6

l1,7

r1,7

s1,7

l1,8

r1,8

s1,8

r4,1

l4,1

r4,2

l4,2
l4,3

G4

r4,3
r4,4

l4,4
b4

(b) Lemma 5.2, inductive step (c) Lemma 5.2, base case

Fig. 5: Illustrations of parts of the proof of Theorem 1.2.

18

In Figure 5b, we illustrate the inductive step of the proof of Lemma 5.2. This lemma states
that, for a CNF-formula ϕ = C1 ∧ . . . ∧ Cm on m clauses, there exists a graph such that the number
of partial solutions for certain fingerprints encodes the number of satisfying assignments of ϕ. The
proof of this lemma is by induction on m, so in the inductive step, we assume a graph GL is given
for ϕ0 = C1 ∧ . . . ∧ Cm−1 , and a graph GR for the CNF-formula Cm . The graphs GL and GR have a
certain block structure consisting of smaller graphs GiL and GiR , which allows us to basically restrict
attention to one block (i.e., a fingerprint of one block encodes a partial assignment of a block of
variables).4 Suppose the graphs GiL and GiR have boundary vertices L ∪ R and R ∪ S respectively.
Then we can see these graphs as matrices L and R of which an entry indexed by f, f 0 equals the
number of partial solutions on fingerprints f, f 0 in GiL (in which case f is on L and f 0 is on R),
and respectively the number of partial solutions on fingerprints f, f 0 in GiR (in which case f is on
R and f 0 is on S). Note the fingerprint of the partial solution in GiL on R and the fingerprint of
GiR on R also need to match as otherwise the union cannot give a partial solution in the graph
Gi ∪ GiR , and by our construction two partial solutions with matching fingerprint on R are also a
partial solution of Gi ∪ GiR . It follows that if we let A be the number of partial solutions in Gi ∪ GiR
indexed by fingerprint fL on L and fR on R, than this matrix can be computed as the matrix
multiplication LFR, where F is a full rank submatrix of the Hamiltonian fingerprint matrix by a set
of fingerprints that we restrict ourselves to. By using gadgets to ensure that L = CF−1 where C is a
diagonal matrix checking whether the assignment satisfies ϕ0 the inductive step can be carried out. In
Figure 5b the showed partial solution in G1L is derived from the fingerprint fL = (dL , ML ) in G1L with
−1
−1
6
d−1
L (1) = {l1,i }i=1 , dL (2) = {l1,8 }, dL (0) = {l1,7 } and ML = {l1,1 l1,2 , l1,3 l1,4 , l1,5 l1,6 } on L and from
1
the fingerprint fR = (dR , MR ) in GL with dR (v) = 2 − dL (v), and MR = {r1,1 r1,3 , r1,2 r1,5 , r1,4 l1,6 }
on L. If this (or a fingerprint of another block) encodes a partial assignment satisfying ϕ0 , there
will be F−1 [fL , fR ] partial solutions with fingerprint fL ∪ fR in G1L .
In Figure 5c we illustrate the base case of the proof of Lemma 5.2. The graph is partitioned into
q blocks G1 , . . . , Gq (with q = 4) in the example, and a fingerprint on Li = {li,j }{ j ≤ β} encodes
a partial assignment of a block of variables of the CNF-formula, which we consider to be a single
clause as m = 1 in the base case of the induction. A graphs Gi contains a top vertex ti and bottom
vertices bi , and the consecutive graphs overlap in the sense that bi+1 = ti . Partial solutions are
locally (that is, per Gi ) restricted such that i is the smallest integer with the property that the
partial solution encodes a fingerprint satisfying the clause if and only if the partial solution in Gi
has a fingerprint in which both ti and bi are of degree 2.

5.2

Pattern propagation using a rank lower bound

Let γ := γ(ε) ≥ 4 be even. Assume we are given a CNF-formula ϕ = C1 ∧ . . . ∧ Cm on variables
x1 , . . . , xn with n being a multiple of γ;5 let q = nγ . Partition the set {x1 , . . . , xn } into n/γ blocks
of size γ, denoted X1 , . . . , Xn/γ . Intuitively, we will represent the 2γ assignments of the block
of variables Xi by HC-fingerprints on groups of vertices in a bag of the to be constructed path
decomposition. We let Bl , Br be sets of HC-fingerprints on [β] such that H[Bl , Br ] has full rank over
p and if (dl , Mr ) ∈ Bl and (dr , Mr ) ∈ Br then
• dl (i), dr (i) equal 1 for i = 1, 2, 3, and
4

This is not completely true, as partial assignments must interact to check whether any partial assignment satisfies
a clause, but this does not turn out problematic.
5
Note that since γ is a constant this is easily established by adding at most γ dummy variables.

19

• {1, 3} ∈ Ml and {1, 2} ∈ Mr .
For i = 1, . . . , q we assume ηi is an injective function from Br to {0, 1}Xi which describes the encoded
partial assignment to the variable set Xi . Note this is only possible when |Br | ≥ 2γ , which we will
ensure in Subsection 5.5 when wrapping up the proof of Theorem 1.2. We let denote η denote the
natural extension of ηi , i.e. η(f1 , . . . , fn/γ ) = (η1 (f1 ), . . . , ηn/γ (fn/γ )). In the following, we refer to
H[Bl , Br ] as F, and also frequently use the q-th Kronecker power F⊗q . We also use F−1 (which is
indexed by Br and Bl respectively) and its Kronecker power (F−1 )⊗q = (F⊗q )−1 .
Lemma 5.2. Let L = L1 ∪· . . . ∪· Lq , R = R1 ∪· . . . ∪· Rq be disjoint sets with Li = {li,1 , . . . , li,β } and
Ri = {ri,1 , . . . , ri,β }. There exists a graph G(L, R, ϕ) = (V, E) with independent set L ∪ R ⊆ V such
that for every sequence of fingerprints


fL = (diL , MRi )) on Li i∈[q] and fR = (diR , MRi ) on Ri i∈[q] ,

Sq
q
i
i
i
the number of partial solutions in G for fingerprint f 0 =
i=1 dL ∪ dR , ∪i=1 Malt equals
(
(F⊗q )−1 [fL , fR ], if fL ∈ Brq , fR ∈ Blq and η(fL ) satisfies ϕ,
A[fL , fR ] :=
0,
otherwise.
i is the altered matching defined by M i = M i ∪ M i \ {l l , r r } ∪ {l r , l r }.
Here Malt
i,1 i,2 i,1 i,3
i,1 i,1 i,2 i,3
L
R
alt
Moreover, G has a path decomposition P of width β · q + O(β) starting in L and ending in R, and G
and P can be computed in polynomial time.

It may look counterintuitive (or like a typo) that fL ∈ Brq , but note that the subscripts l and r
denote that fingerprints in Bl will be used for partial solutions connecting vertices ‘to the left’ of a
certain vertex boundary, while fingerprints in Br will be used for partial solution ‘to the right’ of a
certain boundary (see Figure 5b). As L is the ‘left boundary’ of G connection made in G between
vertices in L will be ‘to the right’ of L so the matchings will be in Br .
We will prove Lemma 5.2 by induction on the number of clauses m. The bulk of our technical
efforts with gadgets will be to prove the following lemma for m = 1. On the other hand, for proving
the inductive step our new key insight of applying matrix inversion is crucial. We postpone the
technical proof of the base case m = 1 to Subsection 5.4 and first focus on the inductive step.
Proof of Lemma 5.2 (inductive step). Let ϕ = C1 ∧ . . . ∧ Cm be a CNF formula on n variables and
ϕ0 = C1 ∧ . . . ∧ Cm−1 . Let L = L1 ∪· . . . ∪· Lq , R = R1 ∪· . . . ∪· Rq , S = S1 ∪· . . . ∪· Sq be disjoint sets with
Li = {li,1 , . . . , li,β }, Ri = {ri,1 , . . . , ri,β } and Si = {si,1 , . . . , si,β }. Let Ĝ = (V̂ , Ê) = G(L, R, ϕ0 ) and
G̃ = (Ṽ , Ẽ) = G(R, S, Cm ) be graphs as given by the induction hypothesis.
Define G = (V̂ ∪ Ṽ , Ê ∪ Ẽ). We show G satisfies the conditions of Lemma 5.2 with ϕ, as required
to prove the inductive step. Note that Ê ∩ Ẽ = ∅ as V̂ ∩ Ṽ = R is an independent set in both
graphs. As V̂ ∩ Ṽ = R, the path decomposition of Ĝ ending in R and the path decomposition of G̃
starting in R can clearly be combined into a path decomposition of G of the same width. It remains
to show that for every sequence of fingerprints


fL = (diL , MLi ) on Li i∈[q] and fS = (diS , MSi ) on Si i∈[q] ,

Sq
q
i
i
i
the number of partial solutions H in G for fingerprint f =
i=1 dL ∪ dS , ∪i=1 Malt equals
(
(F⊗q )−1 [fL , fS ], if fL ∈ Brq , fS ∈ Blq and η(fL ) satisfies ϕ,
(1)
0,
otherwise.
20

i = M i ∪ M i \ {l l , s s } ∪ {l s , l s }. To show this, we first show the following:
Here Malt
i,1 i,2 i,1 i,3
i,1 i,1 i,2 i,3
L
S

Claim 1. The number of partial solutions in G for fingerprint f equals
X
(F⊗q )−1 [fL , fˆR ] · F⊗q [fˆR , f˜R ] · (F⊗q )−1 [f˜R , fS ].
fˆR ∈Bl⊗q ,f˜R ∈Br⊗q
η(fL )|=ϕ0 , η(f˜R )|=Cm

Proof. Let H be a partial solution in G for fingerprint f , let Ĥ = H ∩ Ê and H̃ = H ∩ Ẽ. By
construction of Ĝ and G̃, there are fingerprints fˆ and f˜ of the form
!
!
q
q
[
[
q
q
i
i
i
i
i
i
fˆ =
dL ∪ dˆR , ∪i=1 M̂alt , f˜ =
d˜R ∪ dS , ∪i=1 M̃alt ,
i=1

i=1

such that Ĥ is a partial solution in Ĝ for fˆ and H̃ is a partial solution in G̃ for f˜. Here the altered
matchings are of the form
i
M̂alt
= MLi ∪ M̂Ri \ {li,1 li,2 , ri,1 ri,3 } ∪ {li,1 ri,1 , li,2 ri,3 },
i
M̃alt
= MRi ∪ MSi \ {ri,1 ri,2 , si,1 si,3 } ∪ {ri,1 si,1 , ri,2 si,3 }.

As H is a partial solution in G we have dH (v) = 2 for all vertices in v ∈ R and thus dˆiR (j)+ d˜iR (j) = 2
i ∪ M̃ i
for every i, j. Moreover, H cannot contain a cycle as it is a partial solution and therefore M̂alt
alt
i
i
cannot contain a cycle for every i = 1, . . . , q. It follows that M̂R ∪ M̃R must form a single cycle: if
not, it contains at least two cycles as M̂Ri ∪ M̃Ri are perfect matchings on the same set of vertices,
i ∪ M̃ i . Thus in summary we
and a cycle not containing the vertex ri,1 will still be present in M̂alt
alt
q
have that if Ĥ is a partial solution in Ĝ for fingerprint fˆR = (∪i=1 dˆiR , ∪qi=1 M̂Ri ) on R and is H̃ is a
partial solution in G̃ for fingerprint f˜R = (∪qi=1 d˜iR , ∪qi=1 M̃Ri ) on R, then F⊗q [fˆR , f˜R ] = 1.
⊗q ˆ ˜
For the reverse direction we have that
Sq if Fi [fRi , fRq ] = i1,by the definition of the altered
matchings H indeed has fingerprint f =
i=1 dL ∪ dS , ∪i=1 Malt where
i
Malt
= MLi ∪ MSi \ {li,1 li,2 , si,1 si,3 } ∪ {li,1 si,1 , li,2 si,3 }.
i ), which is connected
To see this, note that in H, the vertex li,1 is connected to ri,1 (directly via M̂alt
i ), and l
i
to si,1 (directly via M̃alt
i,2 is connected to ri,3 (directly via M̂alt ), which is connected to ri,2
i
i
i ).
(indirectly via the path (M̂alt ∪ M̃alt ) ∩ R × R), which is connected to si,3 (directly via M̃alt
The claim follows by summing over all fˆR and f˜R such that η(fL ) |= ϕ0 and η(f˜R ) |= Cm (the
latter two properties follow by the properties of Ĝ and G̃).

By Claim 1 the number of partial solutions in G for fingerprint f equals A[fL , fS ], where
A = C(F⊗q )−1 F⊗q C0 (F⊗q )−1 = CC0 (F⊗q )−1 ,
and C, C0 are diagonal matrices defined by
(
1, if f = f 0 and η(f ) |= ϕ0
0
C[f, f ] =
0, otherwise
and

(
1, if f = f 0 and η(f 0 ) |= Cm
C [f, f ] =
0, otherwise.
0

0

and the inductive step follows as A[fL , fS ] equals (1).
21

3 3

4 4

v3

v4

v52

v6

v7

v8

v9

v1

v2

1 1

2 2

Fig. 6: Implementation of the label gadget. The four labels {1, 2, 3, 4} are depicted symbolically
with  , •, and ◦ respectively for reference in Figure 7.

5.3

Gadgets

In this section we introduce two general gadgets, adapted from previous constructions [11], that are
used in the final construction to obtain strong control on the number of Hamiltonian cycles. Both
gadgets accept parameters to be set in the final construction.
Label Gadget. The following gadget allows us to label incident edges of a vertex v and control
label combinations of the edges used in a Hamiltonian cycle.
Definition 5.3. A label gadget is a pair (v, λv ) where λv : I(v) → {1, 2, 3, 4} is a labeling of the
edges I(v) incident with v. A Hamiltonian cycle C is consistent with label gadget (v, λv ) if λv (e) = 2i
and λv (e0 ) = 2i − 1 for i ∈ {1, 2}, where e, e0 are the two edges of C incident with v.
When we use several label gadgets simultaneously, there will be several labelings and we say an e
edge has label l with respect to v if λv (e) = l. We will now show how to replace a label gadget in a
graph G with a certain graph to obtain G0 such that the number of Hamiltonian cycles in G0 equals
the number of Hamiltonian cycles in G consistent with (v, λv ). The graph is shown at the left-hand
side in Figure 6. That is, the vertex v is replaced by the displayed graph on vertices v1 , . . . , v9 and
each edge with label i = 1, . . . , 4 is connected to vi .
Any Hamiltonian cycle contains exactly two edges of the set of edges leaving the gadget and
these have either labels 1 and 2 or labels 3 and 4. This follows from a simple case analysis: If the
cycle enters the gadget in vertex v1 , it must continue with v5 , v3 . Then it cannot leave the gadget,
because then it is impossible to visit all six remaining vertices. Hence it must continue with v8 and
then v7 , v6 , v4 , v9 , and v2 are forced and the cycle uses edges labeled with 1 and 2. The cases where
it enters at a different vertex are symmetric.
Fingerprint Gadget. Now we present a general gadget allowing strong control on the fingerprints
of partial solutions. If B is a set of vertices, we let PB denote the set of all HC-fingerprints on B.
Definition 5.4 (Fingerprint Gadget). A fingerprint gadget with boundary B for a positive integer
sequence {mf }f ∈PB is a graph G0 = (V 0 , E 0 ) such that B ⊆ V and for every HC-fingerprint f ∈ PB
the number of partial solutions in G0 for f is exactly mf .

22

Lemma 5.5 (Fingerprint Gadget Implementation). Let G, B, {mf }f ∈PB as above. Assume there
exist at least 2 distinct fingerprints f such that mf 6= 0, and there exist a, b ∈ B such that if
f = (d,
6 0, we have ab ∈ M .6 There is a fingerprint gadget G0 for {mf }f ∈PB on
PM ) and mf =
O(|B| f ∈PB mf ) vertices with path decomposition of width |B| + O(1) that starts and ends in B.
Proof. We start with a formal definition of the graph G0 = (V 0 , E 0 ), which we define using label
gadgets. An illustrative example is provided in Figure 7.
1. Add to V 0 the set B and additionally two vertices a0 and c. Add a subdivided edge aa0 .7
Mi ))`i=1 be a sequence of fingerprints that contains each f ∈ PB exactly mf
2. Let (fi = (di ,P
times, so ` = f ∈PB mf .
3. For i = 1, . . . , `:
1
k
(a) Let d−1
i (2) = {ti , . . . , ti } be the vertices of degree 2 in di .
i
(b) Define a sequence of edges Ei = (eji )`j=i
to be an arbitrary ordering of the union of the
−1
0
edgeset of a path from a through di (2) to c and the edgeset Mi \ ab.

j+1
= tji tj+1
; let
• More formally, let e1i = a0 t1i ; for j = 1, . . . , k − 1 = |d−1
i (2)| − 1 let ei
i
k c, and let {ek+2 , . . . , e`i } = M \ ab, where ` = k + 1 + |M |.
ek+1
=
t
i
i
i
i
i
i
i

(c) For j = 1, . . . , `i :
• Let eji = uv. Add a label gadget pji with incident edges pji u with label 1 and pji v
with label 2.
• If j > 1, add an edge pj−1
pji with λpj−1 (e) = 4 and λpj (e) = 3.
i
i

(d) If i > 1, add an edge e = uv =
(e) If i > 2, add an edge e = uv =

`i−1 1
pi−1
pi
`i−2 1
pi−2
pi

i

with λu (e) = 4 and λv (e) = 3.
with λu (e) = 4 and λv (e) = 3.

4. For i = 1, 2, add an edge e = uv = cpi1 with λv (e) = 3.
5. For i = ` − 1, `, add an edge e = uv = p`i i b with λu (e) = 4.
Correctness. Let H be a partial solution in G0 consistent with all label gadgets. Note that H
contains the edges aa00 and a00 a0 as a00 has degree 2. Thus we see that a0 needs to be adjacent in H
to p1x for exactly one chosen x, as this vertex has no other neighbors. We claim that for every x
there is exactly one partial solution containing the edge a0 p1x and this partial solution has fingerprint
fx . Note that this is sufficient to prove the lemma, as it implies we have mf choices for x that lead
to fingerprint f .
To this end, suppose that H contains the edge a0 p1x , and let i 6= x. Then H cannot contain an
edge e incident to p1i satisfying λp1 (e) ∈ {1, 2} by the definition of a label gadget as it only has one
i
edge not incident to a0 with such a label. Thus H needs to contain edges incident to p1i with labels
3 and 4 with respect to p1i . But the only edge with label 4 is to p2i (if it exists) which has label 3
6

These are just technical conditions to facilitate the implementation of this gadget.
Formally, add another vertex a00 with only a and a0 as neighbors. Here a00 is a vertex of degree 2 with the sole
purpose of enforcing the edges a0 a00 and a00 a0 to be in a Hamiltonian cycle.
7

23

a

a00

p11

a0

c

p21

p31

p41

v1

p12

v2

v3

b

p22

p32

v4

p13

v5

p23

B \ {a, b}

Fig. 7: Example of the fingerprint gadget. Here B = {v1 , . . . , v5 , a, b} and mf equals one for
f = fi = (di , Mi ) (described in the next line), and zero otherwise. The vertices p1i represent
−1
fingerprint fi . Here d−1
1 (2) = {v1 , v2 }, M1 = {ab, v3 v4 }; d2 (2) = ∅, M2 = {ab, v2 v3 , v4 v5 };
j
d−1
3 (2) = ∅, M3 = {ab, v4 v5 }. The vertices pi are label gadgets, and the symbols denote the
labels 1, 2, 3, 4 as in Figure 6.
with respect to p2i . By propagation it follows that in H we have that for every pji the two edges
incident to pji must have label 3 and 4 with respect to pji .
Now we focus on p1x , . . . , p`xx . We see that p2x (if it exists) has only one incident edge with label 3
(with respect to p2x ) which is to p1x . Therefore the edges of H incident to p2x must have labels 1 and
2, and the same holds by propagation for all pjx . It follows that H has fingerprint fx : every vertex
in d−1
x (2) has indeed degree 2 as it is incident to two edges in the edges created in Step 3c from the
set Ex ; no edges incident to vertices in d−1
x (0) occur in H as they do not occur in Ex so they are
i
not adjacent to the vertices px , which are the only vertices with incident edges with label 1 or 2.
Moreover, for all edges in uv ∈ Mi \ ab we see H has the path upjx , pjx v as the edges incident to pjx
must have labels 1 and 2.
Summarizing, we saw that H must contain the paths p1i , . . . , p`i i for i 6= x and all edges with
labels 1 and 2 with respect to vertices pjx , and if it does it has the correct fingerprint if a and b are
connected to each other. It remains to show that (without creating subcycles) the paths can be
1+|d−1 (2)|

connected to one path from a to b visiting all vertices V 0 \ (B ∪ {px x
, . . . , p`xi ) in a unique way.
To see that this is the case, first note that a0 is connected to c via the edges e1x , . . . , ek+1
∈ Ei used
x
0 via the
in step 3b of the construction of G0 where k = |d−1
(2)|,
so
they
are
also
connected
in
G
x
`i
`i
1
k+1
1
vertices px , . . . , px . To connect the paths pi , . . . , pi for i =
6 x, note that pi can only be connected
j
0
to vertices pi0 with i > i as an incident edge of label 4 must be chosen. It follows that the only way
to complete the paths is to connect
• c to p11 if x 6= 1 or to p12 if x = 1,
• p`i i to
– p1i+1 , if x 6= i + 1 and i < `,
24

– p1i+2 , if x = i + 1 and i < ` − 1,
– b, if x = i + 1 and i = ` − 1,
– to b if i = `,
which connects a to b, as required.
Path Decomposition and Size. The claimed size bound holds trivially, as all label gadgets have
constant size. For the pathwidth bound, note that after removing B ∪ {a, b} the graph induced on
the vertices pji has constant pathwidth, as for every i, we have that {p`i i , p1i+1 } forms a separator
`
separating pji0 with i0 ≤ i from pji0 with i > i0 , and the graph between separators {pi i−1 , p1i } and
{p`i i , p1i+1 } has constant pathwidth, as it is a path of label gadgets, each of constant size. The
required path decomposition can thus be obtained by including B in every bag.

5.4

The base case of Lemma 5.2

We prove Lemma 5.2 for m = 1, so the CNF-formula is a single clause C1 . The graph output by the
reduction will consist of a graph Gi for 1 ≤ i ≤ q (recall q = n/γ). Each Gi contains ‘left boundary
vertices’ Li , and ‘right boundary vertices’ Ri , and additionally a ‘top vertex’ ti and ‘bottom vertex’
bi . The graphs Gi are glued together by unifying bi = ti−1 to get the graph G. The vertices ti and
bi are used to propagate whether an encoded partial assignment has satisfied the clause. We now
define the graph Gi . Recall from Subsection 5.2 that ηi is an injective function from Br to {0, 1}Xi .
Definition 5.6. Let bi , ti be two vertices. The graph Gi is the following instantiation of a fingerprint
gadget as implemented by Lemma 5.5 with boundary B = L ∪ R ∪ {b, t}, where we shorthand
L = Li , R = Ri , t = ti , b = bi . For every fingerprint fL = (dL , ML ) ∈ Br on L, fingerprint
i ), where M i =
fR = (dR , MR ) ∈ Bl on R and db , dt ∈ {0, 2}, denote f = (dL ∪ dR ∪ db ∪ dt , Malt
alt
i
i
ML ∪MS \{li,1 li,2 , ri,1 ri,3 }∪{li,1 ri,1 , li,2 ri,3 }. For each such combinations we define mf = F−1 [fL , fR ]
if at least one of the following conditions holds:
1. ηi (fL ) is an assignment of Xi satisfying clause C1 , and
(a) dt = db = 2, or
(b) both db = 2 and dt = 0 hold.
2. ηi (fL ) is an assignment of Xi not satisfying clause C1 , and
(a) exactly one the propositions dt = 2 and db = 2 holds.
For other f ∈ P(B), set mf = 0. Let Gi be the fingerprint gadget with boundary B for (mf )f ∈PB .
Proof of Lemma 5.2 (base case). We claim that the graph G has the properties of Lemma 5.2. Let
H be a partial solution which has fingerprint fLi on Li and fRi on Ri . Suppose that for every
i = 1, . . . , q, the assignment ηi (fLi ) to Xi does not satisfy C1 . Then exactly q of the vertices
t1 , . . . , tq , bq will have 2 edges from H incident to it so one vertex will have no incident edges in H
and therefore H cannot be a partial solution and does not contribute to the count.
Otherwise, let i be the smallest integer such that the assignment ηi (fLi ) to Xi satisfies C1 . It
follows that in fingerprint gadget Gi , H induces a partial solution for a fingerprint in which ti and
25

bi both have degree 2. Therefore, in the fingerprint gadget Gi0 with i0 < i, H induces a partial
solution for a fingerprint in which ti has degree 2 and bi has degree 0. Similarly in the fingerprint
gadget Gi0 with i0 > i, H induces a partial solution for a fingerprint in which ti has degree 0 and bi
has degree 2. Therefore, in this case the number of combinations of partial solutions of G1 , . . . , Gq
with the combined fingerprint is thus (F−1 )⊗q [fL , fR ] = (F⊗q )−1 [fL , fR ] by the constructions of the
graphs Gi , as required.
Pathwidth and Size. Let L0 = Rq+1 = ∅ for notational convenience. For a = 0, . . . , q + 1, define
S<a =

a−1
[

Li ∪ Ri ∪ {bi , ti },

Sa = ba ∪ ta ∪

i=1

q
[
i=a

Li ∪

a
[

Ri ,

S>a =

i=1

q
[

Li ∪ Ri ∪ {bi , ti }.

i=a+1

Note that Sa is a separator separating all vertices from S<a from all vertices from S>a Moreover,
S0 contains L and Sq+1 contains R. We construct a path decomposition containing the bags
S0 , . . . , Sq+1 in this order. It remains to show that this can be completed into a efficient path
decomposition by adding an appropriate path decompositions between bags Sa and Sa+1 . To see
this note that the vertices not in S<a and S>a must be in Ga and Ga admits a path decomposition
of width |B| + O(1) = β + O(1) starting in La and ending in Ra by Lemma 5.5. Thus in between
bags Sa and Sa+1 we can add bags with Sa and the path decomposition of Ga ; after the last bag of
this path decomposition we can forget all vertices of Ga except ba and Ra which are contained in
Sa+1 . We obtain a path decomposition of width qβ + O(β), as required.

5.5

Putting things together to prove Lemma 5.1

Proof of Lemma 5.1. We first finish off the construction of G. Let G0 = G(L, R, ϕ) as in Lemma 5.2.
Then do the following for i = 1, . . . , q:
0
1. Add a fingerprint gadget GR
i with boundary Ri to G that has one partial solution for every
fingerprint from Br on Ri .

2. Add vertices bi , ti to G0 , where bi = ti+1 for i < q and tq = b1 .
3. Add a fingerprint gadget GL
Li ∪ bi ∪ ti to G0 such that for every fingerprint
i with
P boundary
a
0
⊗q
−1
fi = (d, M ) ∈ Bl on Li , G has f l ∈Br (F ) [f l , f a ] partial solutions for the fingerpint
f = (d0 , M \ {li,1 li,3 } ∪ {li,1 ti , li,3 bi }),
on Li ∪ bi ∪ ti . Here d0 equals d with the addition that d0 (bi ) = d0 (ti ) = 1.
Number of solutions equals number of Hamiltonian cycles. Analogously to Claim 1, we first
show the following:
Claim 2. The number of Hamiltonian cycles of G equals
X
(F⊗q )−1 [f l , f a ]F⊗q [f a , f b ]A[f b , f c ]F⊗q [f c , f d ].
f a ,f c ∈Blq ,f l ,f b ,f d ∈Brq

26

(2)

R
Proof. Denote GL and GR for the union of the graphs GL
i and Gi , respectively. Let H be an
edgeset with fingerprint constructed from f a = (f1a , . . . , fqa ) in Step 3 on L in GL , and fingerprint
fL on L in G0 . By the construction of G0 , the fingerprint fL must be obtained from a fingerprint fa
by altering the matchings such that fa and fa match (indeed, as before, otherwise in one block two
cycles will be created and one of them will contain the edge {li,1 , li,3 } and thus not be altered so it
remains a subcycle). Similarly, if H has fingerprint fd on R in GR and fingerprint fR on R in G0 ,
fR must be obtained from a fingerprint fc by altering the matchings such that fc and fd match.
Conversely we claim that, if H is an edgeset with fingerprints constructed from f a in Step 3 on
L in GL , fL on L in G0 , fd on R in GR and a fingerprint obtained from f c on R in G0 by altering the
matching, and both f a and f b as well as f c and f d match, then H is automatically a Hamiltonian
cycle. To see this, first take into account the partial solution in G0 and GR . Similarly as in the
proof of Claim 1, it is easily seen that this gives a set of paths that connect li,1 with li,2 for every i
as the fingerprints f c and f d match. Taking also the partial solutions in GL into account and that
f a and f b match, we see that within each block GiL the partial solutions connect ti to bi (denoting
ti = bq ) and therefore the partial solutions combined give a Hamiltonian cycle.
a
By the way we
GL
i the number of partial solutions that have fingerprint f on L is
P constructed
⊗q
l
a
a
−1
multiplied with f l ∈Br (F ) [f , f ]. Therefore, by summing over all fingerprints f , f b , f c , f d
and counting number of partial solutions with these fingerprints as described in the fingerprint
gadgets we obtain that the number of Hamiltonian cycles equals the claimed quantity.

By the definition of A from Lemma 5.2, A = C(F⊗q )−1 with
(
1, if η(f ) |= ϕ,
C[f, f ] =
0, otherwise.
Thus, in matrix terms, (2) can be rewritten into
1T (F⊗q )−1 F⊗q C(F⊗q )−1 F⊗q 1 = 1T C1,
which is easily seen to be the number of assignments of X that satisfy ϕ modulo p, as required.
Pathwidth bound. Recall the graph G0 has pathwidth qβ + O(β). It is easy to see that the
R
additions of the graphs GL
i and Gi do not increase the pathwidth beyond this bound: We can
simply introduce and forget each GR
i separately at the end of the path decomposition. As similar
approach can be used for GL
in
the
start of the path decomposition where we each time only forget
i
the top vertex (except t1 ). Recall that q = n/γ. We will now set the parameters β and γ. We first
show that we can find the needed sufficiently large sets Bl and Br :
Lemma 5.7. Let rkp ∈ R be such that logrkp (rank(Mk ))/k → c, where c ≥ 1, as even k tends
to infinity. Then for any ε0 , there exists a large enough β and sets Bl , Br of fingerprints on [β]
of size at least (2 + rkp − ε0 )β such that Hβ [Bl , Br ] has full rank over p and if (dL , ML ) ∈ Bl and
(dR , MR ) ∈ Br then (i) dl (1), dr (1), dl (2) and dr (3) all equal 1, and (ii) {1, 3} ∈ Ml and {1, 2} ∈ Mr .
Proof. We have rank(Hβ ) ≥ (2 + rp − ε0 )β for large enough β by Fact 2.2, and by the same binomial
theorem argument as in Fact 2.2 we also have that sets of linearly independent rows and columns
exist consisting of fingerprints (d, M ) satisfying |d−1 (1)| ≥ 4. Then there must be a vertex matched
to the same vertices in the row index M1 and column index M2 in at least an 1/β 2 fraction of both
27

basis matchings by the pigeon principle. Denoting this vertex and its two frequent neighbors with
1, 2, 3 the claim follows.
Let ε̂ = ε/2, and pick β sufficiently large such that Lemma 5.7 ensures the sets Bl , Br of
fingerprints on [β] of size at least (2 + rkp − ε̂)β exist. To ensure the existence of the injective
encoding functions η1 , . . . , ηq , we pick γ such that 2γ < (2 + rkp − ε̂)β ; set γ as large as possible
under this constraint so that γ ≥ β log2 (2 + rkp − ε̂) − 1. The pathwidth of G will be at most
qβ + O(β) = (n/γ)β + O(β) ≤ n/(log2 (2 + rkp − ε̂) − 1/β) + O(β).
The running time of the assumed algorithm for counting the number of Hamiltonian cycles
modulo p of the created instance will thus be O∗ (2αn+O(β) ) = O∗ (2αn ) time where
α=

log2 (2 + rkp − ε)
,
log2 (2 + rkp − ε̂) − 1/β

which is smaller than 1 for sufficiently large β (which may depend on ε). Finally, it can be easily
checked that the graph G can trivially be constructed in time polynomial in the size of ϕ and p for
constant ε.

6

Conclusions

As future work, we suggest the problem of counting the connected induced subgraphs of a graph,
where one could try to exclude O∗ (2o(pw log pw) ) time algorithms. The connection matrix for this
problem is the meet matrix of the partition lattice, ordered by refinement, so that the coarsest
partition with one block is the smallest element. For this setting, the powerful technology of Möbius
functions (see e.g. [28]) can readily give rank lower bounds, but it is not a priori clear how to
construct the gadgets required for converting the rank bound into an algorithmic lower bound.
Another example could be the problem of counting Steiner Trees, which has an O∗ (5pw ) time
algorithm from [7], or the evaluation of graph polynomials such as the Tutte polynomial.
A further natural direction for future research is to find the optimal constant cp such that #HC
∗
pw
modulo p can be solved in O∗ (cpw
p ) time and not in O ((cp − ε) ) time for ε > 0. It is natural to
conjecture that cp = 2 + rp , where rp is the exponential base of the rank of Mk over Zp . However,
note that in [11], obtaining an algorithm from the rank upper bound was not trivial and, unlike the
lower bound from Theorem 1.3, it is not a priori clear how to use rank upper bounds as a black box.
The main reason is that we cannot seem to reduce the work related to M to constant-sized copies
as done in the proof of Theorem 1.3. Additionally, we need better lower bounds for the rank of Mk
over Zp , since the bounds from our paper are tight only over Q.

Acknowledgments
The authors thank anonymous reviewers for their valuable comments, and one reviewer in particular
for his thoroughness. Jesper acknowledges Marek Cygan for discussions on Section 5.

References
[1] Josh Alman and Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the
49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 641–652,
New York, NY, USA, 2017. ACM.
28

[2] Regev Amitai. Identities for the number of standard Young tableaux in some (k, l)-hooks.
Séminaire Lotharingien de Combinatoire, 63(3), 2010.
[3] Eiichi Bannai and Tatsuro Ito. Algebraic combinatorics I: association schemes. Mathematics
lecture note series. Benjamin/Cummings Pub. Co., 1984.
[4] Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput.,
43(1):280–299, 2014.
[5] Andreas Björklund and Thore Husfeldt. The parity of directed hamiltonian cycles. In 54th
Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October,
2013, Berkeley, CA, USA, pages 727–735. IEEE Computer Society, 2013.
[6] Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed hamiltonicity and outbranchings via generalized laplacians. In 44th International Colloquium on Automata, Languages,
and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 91:1–91:14, 2017.
[7] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single
exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput.,
243:86–111, 2015.
[8] Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity
theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.
[9] Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi. The complexity of unique k-SAT: An isolation lemma for k-CNFs. J. Comput. Syst. Sci., 74(3):386–393,
2008.
[10] Radu Curticapean and Mingji Xia. Parameterizing the permanent: Genus, apices, minors,
evaluation mod 2k . In IEEE 56th Annual Symposium on Foundations of Computer Science,
FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 994–1009, 2015.
[11] Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of
perfect matchings. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto,
CA, USA, June 1-4, 2013, pages 301–310, 2013.
[12] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij,
and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth
in single exponential time. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on
Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011,
pages 150–159. IEEE Computer Society, 2011.
[13] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation
of representative families with applications in parameterized and exact algorithms. J. ACM,
63(4):29:1–29:60, 2016.
[14] Chris Godsil and K. Meagher. Erdos-Ko-Rado Theorems: Algebraic Approaches. Cambridge
Studies in Advanced Mathematics. Cambridge University Press, 2015.
[15] Chris Godsil and Gordon Royle. Algebraic graph theory, volume 207 of Graduate Texts in
Mathematics. Springer-Verlag, New York, 2001.
29

[16] Jozef Gruska, editor. Mathematical Foundations of Computer Science 1977, 6th Symposium,
Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, volume 53 of Lecture
Notes in Computer Science. Springer, 1977.
[17] Godfrey H. Hardy and Edward M. Wright. An Introduction to the Theory of Numbers. Oxford
University Press, Oxford, sixth edition, 2008. Revised by D. R. Heath-Brown and J. H.
Silverman, With a foreword by Andrew Wiles.
[18] Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems.
Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.
[19] Russel Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst.
Sci., 62(2):367–375, 2001.
[20] Tomer Kotek and Johann A. Makowsky. Connection matrices and the definability of graph
parameters. In Computer Science Logic (CSL’12) - 26th International Workshop/21st Annual
Conference of the EACSL, CSL 2012, September 3-6, 2012, Fontainebleau, France, pages
411–425, 2012.
[21] Stefan Kratsch and Magnus Wahlström. Compression via matroids: A randomized polynomial
kernel for odd cycle transversal. ACM Trans. Algorithms, 10(4):20:1–20:15, 2014.
[22] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press,
New York, NY, USA, 1997.
[23] Nathan Lindzey. Erdős–Ko–Rado for perfect matchings. European Journal of Combinatorics,
65:130 – 142, 2017.
[24] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded
treewidth are probably optimal. In Dana Randall, editor, Proceedings of the Twenty-Second
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California,
USA, January 23-25, 2011, pages 777–789. SIAM, 2011.
[25] László Lovász. The rank of connection matrices and the dimension of graph algebras. Eur. J.
Comb., 27(6):962–970, 2006.
[26] László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications.
American Mathematical Society, 2012.
[27] László Lovász and Michael E. Saks. Lattices, Möbius functions and communication complexity.
In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York,
USA, 24-26 October 1988, pages 81–90. IEEE Computer Society, 1988.
[28] László Lovăsz and Michael Saks. Communication complexity and combinatorial lattice theory.
Journal of Computer and System Sciences, 47(2):322 – 349, 1993.
[29] Ian G. Macdonald. Symmetric functions and Hall polynomials. Oxford mathematical monographs. Clarendon Press, 1995.
[30] Jiřı́ Matoušek. Thirty-three miniatures: Mathematical and Algorithmic applications of Linear
Algebra, volume 53. American Mathematical Soc., 2010.
30

[31] Burkhard Monien. How to find long paths efficiently. North-Holland Mathematics Studies,
109:239 – 254, 1985. Analysis and Design of Algorithms for Combinatorial Problems.
[32] Marko Petkovsek, Herbert S. Wilf, and Doron Zeilberger. A = B. A K Peters Series. Taylor &
Francis, 1996.
[33] Ran Raz and Boris Spieker. On the ”log rank”-conjecture in communication complexity.
Combinatorica, 15(4):567–588, 1995.
[34] Bruce Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Graduate Texts in Mathematics. Springer New York, 2001.
[35] Richard P. Stanley. Enumerative Combinatorics:, volume 2 of Cambridge Studies in Advanced
Mathematics. Cambridge University Press, 2001.
[36] Robert M. Thrall. On symmetrized Kronecker powers and the structure of the free Lie ring.
American Journal of Mathematics, 64(1):pp. 371–388, 1942.
[37] Ryan Williams. The polynomial method in circuit complexity applied to algorithm design
(invited talk). In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference
on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014,
December 15-17, 2014, New Delhi, India, volume 29 of LIPIcs, pages 47–60. Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2014.
[38] Michal Wlodarczyk. Clifford algebras meet tree decompositions. In Jiong Guo and Danny
Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation,
IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 29:1–29:18.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

A

Proof of Theorem 1.1 from Theorem 1.2 and Theorem 1.3

We prove a slightly stronger consequence, namely, that there is an algorithm that counts the
satisfying assignments of a given a CNF-formula on n variables in O∗ ((2 − ε)n ) time for some ε > 0.
Let n be the number of variables of the given CNF-formula ϕ. The Chinese Remainder Theorem
(CRT) tells us that given the number of satisfying assignments
Q of ϕ modulo primes p1 , . . . , p` , we
can compute the number of satisfying solutions of ϕ as long as `i=1 pi ≥ 2n . By the Prime Number
Theorem [17, p. 494, Eq. (22.19.3)], there are at least r/ log2 r primes between r and 2r, and thus
Y
p ≥ rr/ log r ≥ 2Ω(r) .
r ≤ p prime ≤ 2r

It follows that for counting the number of satisfying assignments of a given CNF-formula, it is
sufficient to count the number of satisfying assignments modulo p for any p = Θ(n). We do this using
Lemma 5.1 combined with the algorithm for #HC. For fixed t we have that rankp (Mt ) = rank(Mt )
for large enough p (which can for example be shown by upper bounding the determinant of Mt by
t!). The assumed algorithm for #HC also counts the number of Hamiltonian cycles modulo p. By
Theorem 1.3 we have limp→∞ rp = 4 and Theorem 1.1 follows.

31

B

Finite Group Representation Theory

For a set X, let C[X] denote the vector space of dimension |X| of complex-valued functions from X.
A representation (φ, V ) of a finite group G is a homomorphism φ : G → GL(V ) where GL(V ) is the
group of dim V × dim V invertible matrices. We refer to (φ, V ) simply as φ when V is understood, or
as V when φ is understood. For any representation φ, we define its dimension to be dim φ := dim V .
Two representations ρ, φ are equivalent if ρ(g) and φ(g) are similar for all g ∈ G.
Let (φ, V ) be a representation of a finite group G, and let W ≤ V be a G-invariant subspace,
that is, φ(g)w ∈ W for all w ∈ W and for all g ∈ G. We say that (φ|W , W ) is a sub-representation
of φ where φ|W is the restriction of φ to the subspace W . A representation (φ, V ) is an irreducible
representation (or simply, an irreducible) if it has no proper sub-representations.
It is well-known that there is a one-to-one correspondence between the set of inequivalent
irreducibles of G and its conjugacy classes C, and that any representation V of G uniquely decomposes
as a finite direct sum of inequivalent irreducibles Vi of G:
V ∼
=

|C|
M

mi Vi

i=1

where mi is the multiplicity of Vi (the number of times that Vi occurs in the decomposition). Natural
representations of groups can be obtained by letting them act on sets. In particular, for any group
G acting on a set X, let (φ, C[X]) be the permutation representation of G on X defined such that
φ(g)[f (x)] = f (g −1 x)
for all g ∈ G, f ∈ C[X], and x ∈ X. If we let G act on itself (X = G), then we obtain the regular
representation, which admits the following decomposition into irreducibles:
C[G] ∼
=

|C|
M

(dim φi ) Vi

i=1

where (φi , Vi ) is the ith irreducible of G. Letting eg eh = egh over the standard basis {eg }g∈G of
C[G], we see that C[G] is an algebra, the so-called group algebra of G.
For any (irreducible) representation φ of G, the (irreducible) character χφ of φ is the map
χφ : G → C such that χφ (g) := Tr(φ(g)). Similar matrices have the same trace, thus the character
of a representation is a class function, that is, they are constant on conjugacy classes. Furthermore,
the characters of the set of all irreducible representations of a group G form an orthonormal basis
for the space of all class functions of C[G].

32

