# Homology and twisted $C^{*}$-algebras for self-similar actions and
Zappa–Szép products

Alexander Mundey<EMAIL_ADDRESS>and  Aidan Sims<EMAIL_ADDRESS>School
of Mathematics and Applied Statistics
University of Wollongong
NSW 2522
Australia

###### Abstract.

We study the categorical homology of Zappa–Szép products of small categories,
which include all self-similar actions. We prove that the categorical homology
coincides with the homology of a double complex, and so can be computed via a
spectral sequence involving homology groups of the constituent categories. We
give explicit formulae for the isomorphisms involved, and compute the homology
of a class of examples that generalise odometers. We define the
$C^{*}$-algebras of self-similar groupoid actions on $k$-graphs twisted by
$2$-cocycles arising from this homology theory, and prove some fundamental
results about their structure.

###### Key words and phrases:

Self-similar action; Zappa–Szép product; homology; twisted $C^{*}$-algebra;
$k$-graph

###### 2020 Mathematics Subject Classification:

18G15 (primary); 18A32, 46L05 (secondary)

This research was supported by Australian Research Council grant DP220101631.
The first author was supported by University of Wollongong AGEiS CONNECT grant
141765.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Matched pairs, Zappa–Szép products, and factorisation systems
    1. 3.1 Matched pairs
    2. 3.2 Extending matched pairs to composable tuples
    3. 3.3 Model matched pairs
    4. 3.4 Further examples
      1. 3.4.1 $k$-graphs
      2. 3.4.2 Self-similar actions
      3. 3.4.3 Graphs of groups and group actions on trees
  4. 4 Three homology theories for matched pairs
    1. 4.1 The categorical complex and categorical homology
    2. 4.2 The matched complex
    3. 4.3 The diagonal complex and diagonal homology
    4. 4.4 The total complex and total homology
  5. 5 Equivalence of homology theories
    1. 5.1 The natural chain maps
      1. 5.1.1 The map $\nabla$
      2. 5.1.2 The map $\Pi$
      3. 5.1.3 The map $\Psi$
    2. 5.2 The statement of the main theorem
    3. 5.3 Homological acyclicity of model matched pairs
    4. 5.4 Proof of the main theorem
    5. 5.5 Explicit formulas for the natural isomorphisms between homology theories
    6. 5.6 A spectral sequence and a Künneth Theorem
      1. 5.6.1 A spectral sequence
      2. 5.6.2 The Künneth Theorem for products of monoids
  6. 6 Examples and homology computations
    1. 6.1 Matched pairs involving path categories of directed graphs
    2. 6.2 Matched pairs involving bundles of monoids
    3. 6.3 Matched pairs involving integer bundles
    4. 6.4 Graphs of odometers
  7. 7 Twisted $C^{*}$-algebras of self-similar groupoid actions on $k$-graphs
    1. 7.1 Twists by categorical cocycles
    2. 7.2 Twists by total 2-cocycles

##  1\. Introduction

This paper achieves three main objectives:

  1. (1)

to introduce a unifying framework, which we call matched pairs of categories,
for self-similar actions, graphs of groups, Zappa–Szép products, and
$k$-graphs;

  2. (2)

to introduce homology and cohomology for matched pairs, and develop practical
tools for computing them; and

  3. (3)

to associate twisted $C^{*}$-algebras to self-similar groupoid actions on
$k$-graphs, and establish fundamental structure theorems for these
$C^{*}$-algebras.

Self-similar groups of automorphisms of trees were introduced in the early
1980s as models for new classes of groups. Grigorchuk used self-similar groups
to describe the first example of a finitely generated group with intermediate
growth [Gri80, Gri84], and Nekrashevych recently used them to produce the
first simple groups of intermediate growth [Nek18]. Self-similar groups have
been studied intensively ever since Grigorchuk’s work, including, since the
seminal work of Nekrashevych [Nek05], via their $C^{*}$-algebras. Nekrashevych
studies $C^{*}$-algebraic representations not just a self-similar group, but
of the entire self-similar system: a unitary representation of the group and a
Cuntz representation of the alphabet being acted upon. The resulting
$C^{*}$-algebra encodes information about the self-similar system through both
$K$-theory [Nek05] and KMS-data [LRRW14, EP17, LRRW18]. The former suggests
that homological invariants of self-similar actions could be a profitable
avenue of study.

Initially, self-similar actions were presented with an apparent asymmetry
between the role of the group and the role of the alphabet. But recent
generalisations [LRRW14, EP17, LRRW18, LY21, LawV22] make it increasingly
clear that the roles of the two objects are symmetric, and that self-similar
actions are closely related to Zappa–Szép products.

Introduced by Zappa [Zap42] and Szép [Sze50], Zappa–Szép products of groups
are a generalisation of semidirect products in which each of the two
constituent groups acts on the other; so both embed as (not necessarily
normal) subgroups of the product. Subsequent generalisations include
Zappa–Szép-style products of increasingly general pairs of algebraic objects:
[Bri05, Law08, LRRW14, BPRRW17, BKQS18, LRRW18, LawV22, PO22, DL23].

Here, we start with a _matched pair of categories_ : small categories
$\mathcal{C}$ and $\mathcal{D}$ with common object set, a left action
$(c,d)\mapsto c\triangleright d$ of $\mathcal{C}$ on $\mathcal{D}$ and a right
action $(c,d)\mapsto c\triangleleft d$ of $\mathcal{D}$ on $\mathcal{C}$
satisfying the compatibility conditions of [Zap42, Sze50]. Each such pair
determines a Zappa–Szép-product category $\mathcal{C}\bowtie\mathcal{D}$; this
can be viewed either “externally” as the fibred product
$\mathcal{D}\mathbin{{{}_{s}*_{r}}}\mathcal{C}$ under a suitable
multiplication, or “internally” as the universal category containing copies of
$\mathcal{C}$ and $\mathcal{D}$ with a strict factorisation system as in
[RW02] that implements $\triangleright$ and $\triangleleft$. All of the
algebraic product constructions mentioned above fit into this framework, as do
graphs of groups [Bas93, Ser80] and $k$-graphs [KP00]. Their $C^{*}$-algebraic
representations all boil down to representations, in the sense of Spielberg
[Spe20], of the associated Zappa–Szép-product category.

In the study of $C^{*}$-algebras associated to algebraic or combinatorial
objects, there is a well-established principle that interesting
$C^{*}$-algebraic properties emerge when we twist the multiplication by a
$\mathbb{T}$-valued $2$-cocycle. The archetypal examples are the
noncommutative tori $A_{\theta}$, which are obtained by twisting the
multiplication in unitary representations of $\mathbb{Z}^{k}$ by
$\mathbb{T}$-valued $2$-cocycles—which themselves are simply computed in terms
of characters (1-cocycles) on the constituent factors of $\mathbb{Z}$ in
$\mathbb{Z}^{k}$ [OPT80]. To generalise this to matched pairs we need both a
suitable definition of cohomology, and effective tools for computing it in
terms of the cohomology of the constituent categories.

For topological spaces $X$ and $Y$, the classical _Eilenberg–Zilber Theorem_
gives an isomorphism between the (singular) homology of the chain complex
$C_{\bullet}(X\times Y)$ and the total homology of the tensor product double
complex $C_{\bullet}(X)\operatorname{\otimes}_{\mathbb{Z}}C_{\bullet}(Y)$. We
take this as our inspiration for analysing homology of Zappa–Szép products. We
consider the classical categorical homology of
$\mathcal{C}\bowtie\mathcal{D}$: $n$-chains are $\mathbb{Z}$-linear
combinations of composable $n$-tuples, and boundary maps are alternating sums
of the maps obtained by deleting the first or last entry in a composable
tuple, or composing adjacent terms. We show that this homology can be computed
in terms of a double complex, called the _matched complex_ : its columns are
chain complexes for the homology of $\mathcal{D}$ with coefficients in modules
spanned by composable tuples in $\mathcal{C}$; and its rows are chain
complexes for the homology of $\mathcal{C}$ with coefficients in modules
spanned by composable tuples in $\mathcal{D}$. The matched complex
$C_{\bullet,\bullet}$ is not the tensor product
$C_{\bullet}(\mathcal{C})\operatorname{\otimes}_{\mathbb{Z}}C_{\bullet}(\mathcal{D})$,
but its terms are fibred products of a similar form.

The matched complex admits two natural homology theories—diagonal homology
$H^{\Delta}_{\bullet}(\mathcal{C},\mathcal{D})$ and total homology
$H^{\operatorname{Tot}}_{\bullet}(\mathcal{C},\mathcal{D})$. These are
isomorphic via explicit chain equivalences called the Eilenberg–Zilber map and
the Alexander–Whitney map. The total homology
$H^{\operatorname{Tot}}_{\bullet}(\mathcal{C},\mathcal{D})$, is defined in
terms of the homology of the constituent categories $\mathcal{C}$ and
$\mathcal{D}$. So to see that the categorical homology
$H^{\bowtie}_{\bullet}(\mathcal{C},\mathcal{D})$ of
$\mathcal{C}\bowtie\mathcal{D}$ suits our purposes, we use the method of
acyclic models to construct explicit chain equivalences between the chain
complex $C^{\bowtie}_{\bullet}(\mathcal{C},\mathcal{D})$ defining
$H^{\bowtie}_{\bullet}(\mathcal{C},\mathcal{D})$ and the diagonal chain
complex $C^{\Delta}_{\bullet}(\mathcal{C},\mathcal{D})$. Combined with the
Eilenberg–Zilber map, this gives a computable isomorphism
$H^{\operatorname{Tot}}_{\bullet}(\mathcal{C},\mathcal{D})\cong
H^{\bowtie}_{\bullet}(\mathcal{C},\mathcal{D})$. Dualising yields isomorphisms
$H^{\bullet}_{\operatorname{Tot}}(\mathcal{C},\mathcal{D};\mathbb{T})\cong
H^{\bullet}_{\bowtie}(\mathcal{C},\mathcal{D};\mathbb{T})$ in cohomology.

As an aside, this shows that if a category admits a strict factorisation
system, then its categorical homology can be computed in terms of that of the
embedded subcategories. This yields, for example, a potential iterative
approach to computing homology for $k$-graphs.

We use our results to compute the homology of a class of self-similar groupoid
actions on graphs that generalise the odometer. We calculate the homology in
terms of the two nonzero homology groups of the underlying graph $E$, and the
kernel and cokernel of an $E^{0}\times E^{1}$ matrix encoding the orders of
the odometers involved. _En passant_ , we establish useful general results
about homology for matched pairs in which one factor is the path category of a
directed graph, or a bundle of monoids, with stronger results when the monoids
are copies of $\mathbb{Z}$. These results would be well suited to computing
the homology of Exel–Pardo systems [EP17].

The main motivation for our work on homology is to study twisted
$C^{*}$-algebras of matched pairs. The point is that the natural definition of
a $C^{*}$-algebraic representation of a matched pair, as made clear by
Spielberg’s work [Spe20], is as a multiplicative map $\zeta\mapsto t_{\zeta}$
from its Zappa–Szép product category to a semigroup of partial isometries.
Consequently, the natural definition of a twisted representation is in terms
of a categorical $2$-cocycle $c$ on the Zappa–Szép product: we twist by the
formula $s_{\zeta}s_{\eta}=c(\zeta,\eta)s_{\zeta\eta}$. However, the total
homology (and cohomology) is a more computable theory, and clearly reflects
the decomposition of the Zappa–Szép product category into its constituent
components. Our main homology theorem allows us to define and analyse the
$C^{*}$-algebras in the natural way via categorical $2$-cocycles, but pass to
total cohomology when we wish to identify the possible twists for a given
matched pair or produce nontrivial cocycles in concrete examples.

We explore this in the context of matched pairs consisting of a groupoid
$\mathcal{G}$ and a row-finite $k$-graph $\Lambda$ with no sources (self-
similar actions of groupoids on such $k$-graphs). This covers a fairly general
class of examples with relatively complex cohomology, for which
$C^{*}$-algebraic representations in the sense of Spielberg of the associated
untwisted pair are well understood. Given a categorical $2$-cocycle $c\in
C^{2}_{\bowtie}(\mathcal{G},\Lambda;\mathbb{T})$, we define a universal
twisted Toeplitz algebra $\mathcal{T}C^{*}(\mathcal{G},\Lambda;c)$ and a
universal Cuntz–Krieger algebra $C^{*}(\mathcal{G},\Lambda;c)$ in both of
which all the generators are nonzero. We show that
$\mathcal{T}C^{*}(\Lambda,{\left.\kern-1.2ptc\vphantom{|}\right|_{\Lambda^{2}}})$
embeds in $\mathcal{T}C^{*}(\mathcal{G},\Lambda;c)$ and likewise that
$C^{*}(\Lambda,{\left.\kern-1.2ptc\vphantom{|}\right|_{\Lambda^{2}}})$ embeds
in $C^{*}(\mathcal{G},\Lambda;c)$. We also show that if $\mathcal{G}$ is
amenable then
$C^{*}(\mathcal{G},{\left.\kern-1.2ptc\vphantom{|}\right|_{\mathcal{G}^{2}}})$
embeds in $\mathcal{T}C^{*}(\mathcal{G},\Lambda;c)$, and that an addition
condition developed by Yusnitha [Yus23] ensures that it also embeds in
$C^{*}(\mathcal{G},\Lambda;c)$. We establish a gauge-invariant uniqueness
theorem for $C^{*}(\mathcal{G},\Lambda;c)$ and prove that cohomologous
$2$-cocycles yield isomorphic twisted $C^{*}$-algebras.

We then construct twisted $C^{*}$-algebras
$\mathcal{T}C^{*}_{\varphi}(\mathcal{G},\Lambda)$ and
$C^{*}_{\varphi}(\mathcal{G},\Lambda)$ associated to a total 2-cocycle
$\varphi\in C^{2}_{\operatorname{Tot}}(\mathcal{G},\Lambda;\mathbb{T})$. We
prove that our cochain equivalence $\Psi^{*}\colon
C^{2}_{\operatorname{Tot}}(\mathcal{G},\Lambda;\mathbb{T})\to
C^{2}_{\bowtie}(\mathcal{G},\Lambda;\mathbb{T})$ induces isomorphisms
$\mathcal{T}C^{*}_{\varphi}(\mathcal{G},\Lambda)\cong\mathcal{T}C^{*}(\mathcal{G},\Lambda,\Psi^{*}(\varphi))$
and $C^{*}_{\varphi}(\mathcal{G},\Lambda)\cong
C^{*}(\mathcal{G},\Lambda;\Psi^{*}(\varphi))$.

The paper is organised as follows. In Section 2 we establish some background:
on categories; on actions of one category on another; and on directed graphs
and their path categories.

In Section 3 we discuss matched pairs of small categories. We show that each
matched pair admits a Zappa–Szép product, and discuss internal and external
descriptions of this object and its relationship to strict factorisation
systems. We show how the actions in a matched pair extend to actions on the
categories of composable tuples in the categories involved. We give a number
of concrete examples of matched pairs, including the key _model matched pairs_
that serve as local models for composable tuples in arbitrary matched pairs.

In Section 4 we introduce the three homology theories for matched pairs. We
first introduce categorical homology of a small category, described in terms
of simplicial sets. We then introduce the _matched complex_ —a double complex
associated to a matched pair—in terms of a bisimplicial group, and show that
the assignment of the matched complex to a matched pair is functorial. We then
define the diagonal complex, the total complex, and the associated homology
theories of a matched pair.

In Section 5 we prove our main homology theorem: categorical homology, total
homology, and diagonal homology coincide. In Section 5.1, we describe the
three chain maps that appear in our main theorem: the first is the
Eilenberg–Zilber map for double complexes—we just give a formula for use in
computations; the other two, $\Pi\colon C^{\Delta}_{\bullet}\to
C^{\bowtie}_{\bullet}$ and $\Psi\colon C^{\bowtie}_{\bullet}\to
C^{\operatorname{Tot}}_{\bullet}$, are specific to our situation. In Section
5.2, we state the main theorem, Theorem 5.3, describe the Alexander–Whitney
map, which induces the inverse of the Eilenberg–Zilber map, and outline the
strategy of the proof. In Section 5.3, we show that our model matched pairs
are acyclic in both diagonal and categorical homology, and describe functors
from the Zappa–Szép-product categories of model matched pairs into
$\mathcal{C}\bowtie\mathcal{D}$ that realise all generators of each chain
complex. In Section 5.4 we invoke the method of acyclic models to characterise
chain equivalences between the diagonal and categorical complexes. In
Subsection 5.5 we show that the concrete chain maps described in Section 5.1
are such chain equivalences and describe their inverses. Finally, in Section
5.6, we describe a spectral sequence that computes the homology of a matched
pair, and a Künneth theorem for matched pairs of monoids.

In Section 6, we compute the homology of a concrete class of examples: “graphs
of odometers.” We consider a finite directed graph $E$ together with a
labelling $p\colon E^{1}\to\\{1,2,\dots\\}$ of its edges by strictly positive
integers. We build the augmented graph, $F$ that has a bundle
$\\{e\\}\times\mathbb{Z}/p(e)\mathbb{Z}$ of $p(e)$ parallel edges for each
edge $e\in E$. We consider a matched pair $(E^{0}\times\mathbb{Z},F^{*})$ in
which the copies of $\mathbb{Z}$ behave, collectively, like odometers. In
Section 6.1, we show that in a matched pair where the second factor is the
path category of a graph, only the first two rows of the second page of the
spectral sequence obtained above are nonzero. In Section 6.2, we show that for
matched pairs where the first factor is a bundle of monoids, the homology
groups each decompose as the direct sum of the corresponding homology groups
(with appropriate coefficients) of the monoids. In Section 6.3, we prove that
if the first factor is a bundle of copies of $\mathbb{Z}$, only the first two
columns of the spectral sequence are nonzero, and the homology of each column
is computable via a chain complex very similar to the bar resolution of
$\mathbb{Z}$. In Section 6.4 we restrict to graphs of odometers, and write
down an $E^{0}\times E^{1}$ matrix over $\mathbb{Z}$ whose kernel and
cokernel, together with the homology of the graph $E$, compute the homology of
the system (Theorem 6.15 and Corollary 6.16).

In Section 7, we consider twisted $C^{*}$-algebras associated to matched
pairs. Section 7.1 deals with twists by categorical cocycles, and establishes
some fundamental results about the associated $C^{*}$-algebras: we prove that
the generators are all nonzero and give sufficient conditions under which the
twisted $C^{*}$-algebra of $\mathcal{G}$ embeds in each of
$\mathcal{T}C^{*}(\mathcal{G},\Lambda;c)$ and $C^{*}(\mathcal{G},\Lambda;c)$
in Proposition 7.7; we prove our gauge-invariant uniqueness theorem, Corollary
7.10; and we show that the isomorphism classes of
$\mathcal{T}C^{*}(\mathcal{G},\Lambda;c)$ and $C^{*}(\mathcal{G},\Lambda;c)$
only depend on the cohomology class of $c$. Section 7.2 describes twists by
total cocycles, and shows that these correspond to twists by categorical
2-cocycles via the isomorphism of cohomology induced by our main theorem above
(Theorem 7.15).

##  2\. Preliminaries

Throughout this article, $\mathcal{C}$ and $\mathcal{D}$ denote small
categories. We identify each $\mathcal{C}$ with its set of morphisms and write
$\mathcal{C}^{0}\subseteq\mathcal{C}$ for the set of identity morphisms
(identified with objects). We write $r,s\colon\mathcal{C}\to\mathcal{C}^{0}$
for the maps assigning to $c\in\mathcal{C}$ (the identity morphisms at) its
codomain and domain. For $n\geq 1$, we write $\mathcal{C}^{n}$ for the set of
composable $n$-tuples in $\mathcal{C}$ and define
$r,s\colon\mathcal{C}^{n}\to\mathcal{C}^{0}$ by
$r(c_{1},\ldots,c_{n})=r(c_{1})$ and $s(c_{1},\ldots,c_{n})=s(c_{n})$. For
$x,\,y\in\mathcal{C}^{0}$ we write
$x\mathcal{C}^{n}\coloneqq\\{(c_{1},\ldots,c_{n})\mid r(c_{1})=x\\}$,
$\mathcal{C}^{n}y\coloneqq\\{(c_{1},\ldots,c_{n})\mid s(c_{n})=y\\}$, and
$x\mathcal{C}^{n}y\coloneqq x\mathcal{C}^{n}\cap\mathcal{C}^{n}y$.

If $\mathcal{C}^{0}=\mathcal{D}^{0}$ we define

$\mathcal{C}*\mathcal{D}\coloneqq\mathcal{C}\tensor*[_{s}]{*}{{}_{r}}\mathcal{D}=\\{(c,d)\in\mathcal{C}\times\mathcal{D}\mid
s(c)=r(d)\\}.$

If $\mathcal{C}$, $\mathcal{C}^{\prime}$, and $\mathcal{D}$ have the same
objects and $f\colon\mathcal{C}\to\mathcal{C}^{\prime}$ satisfies
$s(f(c))=f(s(c))$, then
$f*1_{\mathcal{D}}\colon\mathcal{C}*\mathcal{D}\to\mathcal{C}^{\prime}*\mathcal{D}$
is the map $(f*1_{\mathcal{D}})(c,d)\coloneqq(f(c),d)$. Similarly, if
$r(f(c))=r(c)$, then
$1_{\mathcal{D}}*f\colon\mathcal{D}*\mathcal{C}\to\mathcal{D}*\mathcal{C}^{\prime}$
is the map$(1_{\mathcal{D}}*f)(d,c)\coloneqq(d,f(c))$.

An _action_ of a category $\mathcal{C}$ on the left of a set $X$ consists of
maps $a\colon X\to\mathcal{C}^{0}$ and $\triangleright\colon\\{(c,x)\mid
s(c)=a(x)\\}\to X$ such that $a(x)\triangleright x$ and
$(c_{1}c_{2})\triangleright x=c_{1}\triangleright(c_{2}\triangleright x)$ for
all $(c_{1},c_{2})\in\mathcal{C}^{2}$ and $x\in X$ with $s(c_{2})=a(x)$. Right
actions are defined similarly, and correspond to left actions of the opposite
category $\mathcal{C}^{op}$. If $\mathcal{C}^{0}=\mathcal{D}^{0}$ we only
consider left actions for which $a=r\colon\mathcal{D}\to\mathcal{C}^{0}$, so
$\triangleright$ is a map
$\triangleright\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}$. Similarly, we
only consider right actions of $\mathcal{D}$ on $\mathcal{C}$ for which
$a=s\colon\mathcal{C}\to\mathcal{D}^{0}$.

A _groupoid_ $\mathcal{G}$ is a small category in which every morphism
$g\in\mathcal{G}$ has an inverse $g^{-1}\in\mathcal{G}$ such that
$gg^{-1}=r(g)$ and $g^{-1}g=s(g)$. The set of identity morphisms is called the
_unit space_ of $\mathcal{G}$. In this paper, $\mathcal{G}$ always denotes a
discrete groupoid.

A _directed graph_ is a quadruple $E=(E^{0},E^{1},r,s)$, consisting of
countable sets $E^{0}$ of _vertices_ and $E^{1}$ of _edges_ , and maps
$r\colon E^{1}\to E^{0}$ and $s\colon E^{1}\to E^{0}$ called the _range_ and
_source_ maps. For $n\geq 1$, we denote by
$E^{n}\coloneqq\\{\mu=\mu_{1}\cdots\mu_{n}\mid\mu_{i}\in
E^{1},\,s(e_{i})=r(e_{i+1})\\}$, the _paths of length $n$_ in the graph $E$.
If $\mu\in E^{m}$ and $\nu\in E^{n}$ with $s(\mu)=r(\nu)$, then
$\mu\nu\coloneqq\mu_{1}\cdots\mu_{m}\nu_{1}\cdots\nu_{n}\in E^{m+n}$ is the
_concatenation_ of $\mu$ and $\nu$. The range and source maps extend to
$E^{n}$: $r(\mu)=r(\mu_{1})$ and $s(\mu)=s(\mu_{n})$. We regard elements $v$
of $E^{0}$ as paths of length $0$ with $r(v)=s(v)=v$, and we extend
concatenation by the formula $r(\mu)\mu=\mu=\mu s(\mu).$

The _path category_ of a directed graph $E$ is the collection
$E^{*}\coloneqq\bigsqcup_{n=0}^{\infty}E^{n}$ of all finite paths in $E$. The
objects of $E^{*}$ are $E^{0}$, and the range and source maps on the $E^{n}$
extend to domain and codomain maps $r\colon E^{*}\to E^{0}$ and $s\colon
E^{*}\to E^{0}$. Composition is concatenation. We use $|\mu|$ to denote the
length of $\mu\in E^{*}$, so $|\mu|=n$ if and only if $\mu\in E^{n}$.

##  3\. Matched pairs, Zappa–Szép products, and factorisation systems

###  3.1. Matched pairs

In this subsection we introduce matched pairs of small categories and their
associated Zappa–Szép-product categories. We also examine how factorisation
rules and strict factorisation systems are related to these constructions.

######  Definition 3.1.

A _matched pair_ is a quadruple
$(\mathcal{C},\mathcal{D},\triangleright,\triangleleft)$ consisting of small
categories $\mathcal{C}$, $\mathcal{D}$ with
$\mathcal{C}^{0}=\mathcal{D}^{0}$, a left action
$\triangleright\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}$ of $\mathcal{C}$
on $\mathcal{D}$, and a right action
$\triangleleft\colon\mathcal{C}*\mathcal{D}\to\mathcal{C}$ of $\mathcal{D}$ on
$\mathcal{C}$ such that for all
$(c_{1},c_{2},d_{1},d_{2})\in\mathcal{C}^{2}*\mathcal{D}^{2}$,

  1. (MP1)

$s(c_{2}\triangleright d_{1})=r(c_{2}\triangleleft d_{1})$,

  2. (MP2)

$c_{2}\triangleright(d_{1}d_{2})=(c_{2}\triangleright
d_{1})((c_{2}\triangleleft d_{1})\triangleright d_{2})$, and

  3. (MP3)

$(c_{1}c_{2})\triangleleft d=(c_{1}\triangleleft(c_{2}\triangleright
d_{1}))(c_{2}\triangleleft d_{1})$.

We often just say that $(\mathcal{C},\mathcal{D})$ is a matched pair, and
suppress the actions $\triangleright,\triangleleft$.

The category ${\mathsf{MP}}$ of matched pairs has matched pairs as objects and
morphisms
$f=(f^{L},f^{R})\colon(\mathcal{C},\mathcal{D})\to(\mathcal{C}^{\prime},\mathcal{D}^{\prime})$
consisting of pairs of functors
$f^{L}\colon\mathcal{C}\to\mathcal{C}^{\prime}$ and
$f^{R}\colon\mathcal{D}\to\mathcal{D}^{\prime}$ such that for all
$(c,d)\in\mathcal{C}*\mathcal{D}$,

  1. (i)

$(f^{L}(c),f^{R}(d))\in\mathcal{C}^{\prime}*\mathcal{D}^{\prime}$,

  2. (ii)

$f^{L}(c)\triangleright f^{R}(d)=f^{R}(c\triangleright d)$, and

  3. (iii)

$f^{L}(c)\triangleleft f^{R}(d)=f^{L}(c\triangleleft d).$

######  Remark 3.2.

We are unsure of the provenance of the term _matched pair_. It is used for
various related notions: matched pairs of groupoids in [AA05]; and matched
pairs of Hopf algebras in [Sin72]. For matched pairs with
$\mathcal{C}^{0}\neq\mathcal{D}^{0}$, see [DL23, Definition 2.2].

Given a matched pair $(\mathcal{C},\mathcal{D})$, we define
$r\colon\mathcal{D}*\mathcal{C}\to\mathcal{C}^{0}$ and
$s\colon\mathcal{D}*\mathcal{C}\to\mathcal{C}^{0}$ by $r(d,c)\coloneqq r(d)$
and $s(d,c)\coloneqq s(c)$.

######  Definition 3.3.

Let $\mathcal{C}$ and $\mathcal{D}$ be small categories with
$\mathcal{C}^{0}=\mathcal{D}^{0}$. A _factorisation rule_ on
$(\mathcal{C},\mathcal{D})$ is a map
$\bowtie\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}*\mathcal{C}$ such that

  1. (FR1)

$r(c\bowtie d)=r(c)$ and $s(c\bowtie d)=s(d)$ for all
$(c,d)\in\mathcal{C}*\mathcal{D}$, and

  2. (FR2)

if $\mu_{\mathcal{C}}\colon\mathcal{C}^{2}\to\mathcal{C}$ and
$\mu_{\mathcal{D}}\colon\mathcal{D}^{2}\to\mathcal{D}$ denote the composition
maps, then the following diagrams commute:

${\mathcal{C}^{2}*\mathcal{D}}$${\mathcal{C}*\mathcal{D}*\mathcal{C}}$${\mathcal{D}*\mathcal{C}^{2}}$${\mathcal{C}*\mathcal{D}}$${\mathcal{D}*\mathcal{C}}$$\scriptstyle{\mu_{\mathcal{C}}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{C}}*\operatorname{{\bowtie}}}$$\scriptstyle{\operatorname{{\bowtie}}*1_{\mathcal{C}}}$$\scriptstyle{1_{\mathcal{D}}*\mu_{\mathcal{C}}}$$\scriptstyle{\operatorname{{\bowtie}}}$
${\mathcal{C}*\mathcal{D}^{2}}$${\mathcal{D}*\mathcal{C}*\mathcal{D}}$${\mathcal{D}^{2}*\mathcal{C}}$${\mathcal{C}*\mathcal{D}}$${\mathcal{D}*\mathcal{C}\hbox
to0.0pt{.}}$$\scriptstyle{1_{\mathcal{C}}*\mu_{\mathcal{D}}}$$\scriptstyle{\operatorname{{\bowtie}}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}}\\\
*\operatorname{{\bowtie}}}$$\scriptstyle{\mu_{\mathcal{D}}*1_{\mathcal{C}}}$$\scriptstyle{\operatorname{{\bowtie}}}$

The name _factorisation rule_ becomes clear in the context of Zappa–Szép
products (Definition 3.6). Matched pairs and factorisation rules are
equivalent in the following sense.

######  Lemma 3.4.

Let $\mathcal{C}$ and $\mathcal{D}$ be small categories with the same object
set. If $(\mathcal{C},\mathcal{D},\triangleright,\triangleleft)$ is a matched
pair, then the formula

$c\bowtie d\coloneqq(c\triangleright d,c\triangleleft d)$ (3.1)

determines a factorisation rule
$\bowtie\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}*\mathcal{C}$. Conversely,
if $\bowtie\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}*\mathcal{C}$ is a
factorisation rule and
$p_{\mathcal{D}}\colon\mathcal{D}*\mathcal{C}\to\mathcal{D}$ and
$p_{\mathcal{C}}\colon\mathcal{D}*\mathcal{C}\to\mathcal{C}$ are the
coordinate projections, then
$\triangleright\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}$ and
$\triangleleft\colon\mathcal{C}*\mathcal{D}\to\mathcal{C}$ given by

$c\triangleright d\coloneqq p_{\mathcal{D}}(c\bowtie d)\qquad\text{and}\qquad
c\triangleleft d\coloneqq p_{\mathcal{C}}(c\bowtie d)$ (3.2)

make $(\mathcal{C},\mathcal{D},\triangleright,\triangleleft)$ a matched pair.

###### Proof.

First suppose that
$\bowtie\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}*\mathcal{C}$ is a
factorisation rule. Define $\triangleright,\triangleleft$ by (3.2). Since
$c\bowtie d\in\mathcal{D}*\mathcal{C}$, (MP1) holds. The left-hand diagram of
(FR2) implies that

$\displaystyle((c_{1}c_{2})\triangleright d,(c_{1}c_{2})\triangleleft
d)=(c_{1}c_{2})\bowtie d=(c_{1}\triangleright(c_{2}\triangleright
d),(c_{1}\triangleleft(c_{2}\triangleright d))(c_{2}\triangleleft d)),$

so $\triangleright$ is a left action and (MP3) holds. Symmetrically,
$\triangleleft$ is a right action and (MP2) holds.

Now suppose that $(\mathcal{C},\mathcal{D},\triangleright,\triangleleft)$ is a
matched pair and define
$\bowtie\colon\mathcal{C}*\mathcal{D}\to\mathcal{D}*\mathcal{C}$ by (3.1).
Then $c\bowtie d\in\mathcal{D}*\mathcal{C}$ by (MP1). Since
$\triangleright,\,\triangleleft$ are actions $r(c\triangleright d)=r(c)$ and
$s(c\triangleleft d)=s(d)$, giving (FR1). For (FR2) we use (MP3) at the second
equality to compute,

$\displaystyle(c_{1}c_{2})\bowtie d$ $\displaystyle=(c_{1}c_{2}\triangleright
d,c_{1}c_{2}\triangleleft d)=(c_{1}\triangleright(c_{2}\triangleright
d),(c_{1}\triangleleft(c_{2}\triangleright d))(c_{2}\triangleleft d))$
$\displaystyle=(1_{\mathcal{D}}*\mu_{\mathcal{C}})\circ(\bowtie*1_{\mathcal{C}})\circ(1_{\mathcal{C}}*\bowtie)(c_{1},c_{2},d),$

and symmetrically
$c\bowtie(d_{1}d_{2})=(\mu_{d}*1_{\mathcal{C}})\circ(1_{\mathcal{D}}*\bowtie)\circ(\bowtie\circ
1_{\mathcal{D}})(c_{1},d_{2},d_{2})$. ∎

We use Lemma 3.4 without comment to move between matched pairs and
factorisation rules. Importantly, (MP1)–(MP3) give the fibre product
$\mathcal{D}*\mathcal{C}$ the structure of a category.

######  Lemma 3.5.

Suppose that $(\mathcal{C},\mathcal{D})$ is a matched pair and let
$\mu_{\mathcal{C}}$ and $\mu_{\mathcal{D}}$ denote the composition maps on
$\mathcal{C}$ and $\mathcal{D}$ respectively. Define
$\mu_{\bowtie}\colon(\mathcal{D}*\mathcal{C})^{2}\to\mathcal{D}*\mathcal{C}$
by

$\mu_{\bowtie}\coloneqq(\mu_{\mathcal{D}}*\mu_{\mathcal{C}})\circ(1_{\mathcal{D}}*\operatorname{{\bowtie}}*1_{\mathcal{C}}).$

Then for $(d_{1},c_{1}),\,(d_{2},c_{2})\in\mathcal{D}*\mathcal{C}$ such that
$s(c_{1})=r(d_{2})$,

$\mu_{\bowtie}((d_{1},c_{1}),(d_{2},c_{2}))=(d_{1}(c_{1}\triangleright
d_{2}),(c_{1}\triangleleft d_{2})c_{2}).$ (3.3)

Moreover, $\mathcal{D}*\mathcal{C}$ is a small category with
$(\mathcal{D}*\mathcal{C})^{0}=\mathcal{C}^{0}=\mathcal{D}^{0}$,
$r(d,c)\coloneqq r(d)$, $s(d,c)\coloneqq s(c)$, and composition
$(d_{1},c_{1})(d_{2},c_{2})\coloneqq\mu_{\bowtie}((d_{1},c_{1}),(d_{2},c_{2}))$.
The maps $\iota_{\mathcal{C}}\colon\mathcal{C}\to\mathcal{D}*\mathcal{C}$ and
$\iota_{\mathcal{D}}\colon\mathcal{D}\to\mathcal{D}*\mathcal{C}$ defined by
$\iota_{\mathcal{C}}(c)=(r(c),c)$ and $\iota_{\mathcal{D}}(d)=(d,s(d))$ are
faithful functors.

###### Proof.

Equation (3.3) follows from (3.1). For associativity, we calculate:

$\displaystyle\mu_{\bowtie}\big{(}(d_{1},c_{1},)$
$\displaystyle\mu_{\bowtie}((d_{2},c_{2}),(d_{3},c_{3}))\big{)}$
$\displaystyle=\mu_{\bowtie}\big{(}(d_{1},c_{1}),(d_{2}(c_{2}\triangleright
d_{3}),(c_{2}\triangleleft d_{3})c_{3})\big{)}$
$\displaystyle=\big{(}d_{1}(c_{1}\triangleright(d_{2}(c_{2}\triangleright
d_{3}))),c_{1}\triangleleft(d_{2}(c_{2}\triangleright
d_{3}))(c_{2}\triangleleft d_{3})c_{3}\big{)}$
$\displaystyle=\big{(}d_{1}(c_{1}\triangleright d_{2})((c_{1}\triangleleft
d_{2})c_{2}\triangleright d_{3}),((c_{1}\triangleleft
d_{2})\triangleleft(c_{2}\triangleright d_{3}))(c_{2}\triangleleft
d_{3})c_{3}\big{)}$ $\displaystyle=\big{(}d_{1}(c_{1}\triangleright
d_{2})((c_{1}\triangleleft d_{2})c_{2}\triangleright
d_{3}),(c_{1}\triangleleft d_{2}(c_{2}\triangleright
d_{3}))(c_{2}\triangleleft d_{3})c_{3}\big{)}$
$\displaystyle=\mu_{\bowtie}\big{(}d_{1}(c_{1}\triangleright
d_{2}),(c_{1}\triangleleft d_{2})c_{2},d_{3},c_{3}\big{)}$
$\displaystyle=\mu_{\bowtie}\big{(}\mu_{\bowtie}((d_{1},c_{1}),(d_{2},c_{2})),(d_{3},c_{3})\big{)}.$

For functoriality of $\iota_{\mathcal{C}}$ we calculate

$\displaystyle\mu_{\bowtie}(\iota_{\mathcal{C}}(c_{1}),\iota_{\mathcal{C}}(c_{2}))=(r(c_{1})(c_{1}\triangleright
s(c_{1})),(c_{1}\triangleleft
s(c_{1}))c_{2})=(r(c_{1}),c_{1}c_{2})=\iota_{\mathcal{C}}(c_{1}c_{2}).$

Functoriality of $\iota_{\mathcal{D}}$ follows analogously. Faithfulness is
clear. ∎

######  Definition 3.6.

We call the small category $\mathcal{D}*\mathcal{C}$ with the composition
$\mu_{\bowtie}$ of Lemma 3.5 the _Zappa–Szép product_ of $\mathcal{C}$ and
$\mathcal{D}$, and denote it $\mathcal{C}\bowtie\mathcal{D}$.

We identify $\mathcal{C}$ and $\mathcal{D}$ with the subcategories
$\iota_{\mathcal{C}}(\mathcal{C})$ and $\iota_{\mathcal{D}}(\mathcal{D})$ of
$\mathcal{C}\bowtie\mathcal{D}$. In particular, for
$(d,c)\in\mathcal{D}*\mathcal{C}$ we write
$dc\coloneqq(d,c)\in\mathcal{C}\bowtie\mathcal{D}$. So for
$c_{i}\in\mathcal{C}$ and $d_{i}\in\mathcal{D}$,

$d_{1}c_{1}d_{2}c_{2}=d_{1}(c_{1}\triangleright d_{2})(c_{1}\triangleleft
d_{2})c_{2}.$

######  Example 3.7.

If $\mathcal{C}$ is a small category, then $(\mathcal{C},\mathcal{C}^{0})$ is
a matched pair with actions $c\triangleright s(c)=r(c)$ and $c\triangleleft
s(c)=c$. We have
$\mathcal{C}\bowtie\mathcal{C}^{0}\cong\mathcal{C}\cong\mathcal{C}^{0}\bowtie\mathcal{C}$.

######  Example 3.8.

Suppose that $G$ and $H$ are groups and suppose that
$(G,H,\triangleright,\triangleleft)$ is a matched pair. Then $G\bowtie H$ is
the Zappa–Szép product of $G$ and $H$ from [Zap42, Sze50]. If $\triangleleft$
is the trivial right action of $H$ on $G$, then for $h_{i}\in H$ and $g_{i}\in
G$, we have

$(h_{1},g_{1})(h_{2},g_{2})=(h_{1}(g_{1}\triangleright h_{2}),g_{1}g_{2}),$

so $G\bowtie H$ is the semidirect product $G\ltimes H$.

Zappa–Szép products have the following universal property.

######  Proposition 3.9.

Suppose that $(\mathcal{C},\mathcal{D})$ is a matched pair, let $\mathcal{A}$
be a small category such that
$\mathcal{A}^{0}=\mathcal{C}^{0}=\mathcal{D}^{0}$, and suppose that
$j_{\mathcal{C}}\colon\mathcal{C}\to\mathcal{A}$ and
$j_{\mathcal{D}}\colon\mathcal{D}\to\mathcal{A}$ are functors satisfying

$j_{\mathcal{C}}(c)j_{\mathcal{D}}(d)=j_{\mathcal{D}}(c\triangleright
d)j_{\mathcal{C}}(c\triangleleft d)$ (3.4)

for all $(c,d)\in\mathcal{C}*\mathcal{D}$. Then there exists a unique functor
$j_{\mathcal{C}}\bowtie
j_{\mathcal{D}}\colon\mathcal{C}\bowtie\mathcal{D}\to\mathcal{A}$ such that
$(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})\circ\iota_{\mathcal{C}}=j_{\mathcal{C}}$ and
$(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})\circ\iota_{\mathcal{D}}=j_{\mathcal{D}}$. If $\mathcal{B}$ is
a small category with $\mathcal{B}^{0}=\mathcal{C}^{0}$ and
$k_{\mathcal{C}}:\mathcal{C}\to\mathcal{B}$ and
$k_{\mathcal{D}}:\mathcal{D}\to\mathcal{B}$ are functors satisfying (3.4) and
with the same universal property, then $k_{\mathcal{C}}\bowtie
k_{\mathcal{D}}$ is an isomorphism
$\mathcal{C}\bowtie\mathcal{D}\to\mathcal{B}$.

###### Proof.

Define $j_{\mathcal{C}}\bowtie
j_{\mathcal{D}}\colon\mathcal{C}\bowtie\mathcal{D}\to\mathcal{A}$ by
$(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})(d,c)=j_{\mathcal{D}}(d)j_{\mathcal{C}}(c)$. Clearly,
$(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})\circ\iota_{\mathcal{C}}=j_{\mathcal{C}}$ and
$(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})\circ\iota_{\mathcal{D}}=j_{\mathcal{D}}$. For functoriality
we compute,

$\displaystyle(j_{\mathcal{C}}\bowtie j_{\mathcal{D}})(d_{1}c_{1}d_{2}c_{2})$
$\displaystyle=j_{\mathcal{D}}(d_{1})j_{\mathcal{D}}(c_{1}\triangleright
d_{2})j_{\mathcal{C}}(c_{1}\triangleleft d_{2})j_{\mathcal{C}}(c_{2})$
$\displaystyle=j_{\mathcal{D}}(d_{1})j_{\mathcal{C}}(c_{1})j_{\mathcal{D}}(d_{2})j_{\mathcal{C}}(c_{2})=(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})(d_{1}c_{1})\,(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})(d_{2}c_{2}).$

If $f\colon\mathcal{C}\bowtie\mathcal{D}\to\mathcal{A}$ is a functor
satisfying $f\circ\iota_{\mathcal{C}}=j_{\mathcal{C}}$ and
$f\circ\iota_{\mathcal{D}}=j_{\mathcal{D}}$, then
$f(dc)=f(\iota_{\mathcal{D}}(d)\iota_{\mathcal{C}}(c))=j_{\mathcal{D}}(d)j_{\mathcal{C}}(c)=(j_{\mathcal{C}}\bowtie
j_{\mathcal{D}})(dc)$. If $(\mathcal{B},k_{\mathcal{C}},k_{\mathcal{D}})$ has
the same universal property, then that universal property applied to
$\iota_{\mathcal{C}}$ and $\iota_{\mathcal{D}}$ yields a functor
$\theta:\mathcal{B}\to\mathcal{C}\bowtie\mathcal{D}$ inverse to
$k_{\mathcal{C}}\bowtie k_{\mathcal{D}}$. ∎

######  Corollary 3.10.

The assignment $(\mathcal{C},\mathcal{D})\mapsto\mathcal{C}\bowtie\mathcal{D}$
is functorial: given a matched-pair morphism
$(h^{L},h^{R})\colon(\mathcal{C},\mathcal{D})\to(\mathcal{C}^{\prime},\mathcal{D}^{\prime})$,
there is a functor
$h\colon\mathcal{C}\bowtie\mathcal{D}\to\mathcal{C}^{\prime}\bowtie\mathcal{D}^{\prime}$
such that $h(dc)=h^{R}(d)h^{L}(c)$ for all $(d,c)\in\mathcal{D}*\mathcal{C}$.
This functor satisfies
$h\circ\iota_{\mathcal{C}}=\iota_{\mathcal{C}^{\prime}}\circ h^{L}$ and
$h\circ\iota_{\mathcal{D}}=\iota_{\mathcal{D}^{\prime}}\circ h^{R}$.
Conversely, if
$h\colon\mathcal{C}\bowtie\mathcal{D}\to\mathcal{C}^{\prime}\bowtie\mathcal{D}^{\prime}$
is a functor such that $h(\mathcal{C})\subseteq\mathcal{C}^{\prime}$ and
$h(\mathcal{D})\subseteq\mathcal{D}^{\prime}$, then
$(h|_{\mathcal{C}},h|_{\mathcal{D}})\colon(\mathcal{C},\mathcal{D})\to(\mathcal{C}^{\prime},\mathcal{D}^{\prime})$
is a matched pair morphism.

###### Proof.

To obtain $h$, apply Proposition 3.9 to $\iota_{\mathcal{C}}\circ h^{L}$ and
$\iota_{\mathcal{D}}\circ h^{R}$. The second statement follows from a one-line
calculation. ∎

As with groups, we can take either an “external” or an “internal” view of
Zappa–Szép products of categories. Recall that a _wide subcategory_ of a
category $\mathcal{E}$ is a subcategory containing $\mathcal{E}^{0}$.

######  Definition 3.11.

A _strict factorisation system_ for a category $\mathcal{E}$ is a pair
$[\mathcal{D},\mathcal{C}]$ of wide subcategories of $\mathcal{E}$ such that
for every $e\in\mathcal{E}$ there are unique $d\in\mathcal{D}$ and
$c\in\mathcal{C}$ satisfying $e=dc$.

######  Remark 3.12.

Factorisation systems are related to distributive laws on monads: strict
factorisation systems are equivalent to distributive laws in the category of
spans [RW02, Theorem 3.8].

######  Proposition 3.13.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. Then
$[\mathcal{D},\mathcal{C}]$ is a strict factorisation system for
$\mathcal{C}\bowtie\mathcal{D}$. Conversely, let $[\mathcal{D},\mathcal{C}]$
be a strict factorisation system for a small category $\mathcal{E}$. For
$(c,d)\in\mathcal{C}*\mathcal{D}$, let $c\triangleright d\in\mathcal{D}$ and
$c\triangleleft d\in\mathcal{C}$ be the unique elements such that
$cd=(c\triangleright d)(c\triangleleft d)$. Then
$(\mathcal{C},\mathcal{D},\triangleright,\triangleleft)$ is a matched pair and
$(d,c)\mapsto dc$ is an isomorphism
$\mathcal{C}\bowtie\mathcal{D}\cong\mathcal{E}$.

###### Proof.

Suppose that $(\mathcal{C},\mathcal{D})$ is a matched pair. Since
$\mathcal{C}\bowtie\mathcal{D}=\mathcal{D}*\mathcal{C}$ as sets, each
$e\in\mathcal{C}\bowtie\mathcal{D}$ factors uniquely as $e=dc$.

Conversely, suppose that $[\mathcal{D},\mathcal{C}]$ is a unique factorisation
system for $\mathcal{E}$ and fix
$(c_{1},c_{2},d_{1},d_{2})\in\mathcal{C}^{2}*\mathcal{D}^{2}$. Let
$d^{\prime},\,d^{\prime\prime},\,d^{\prime\prime\prime}\in\mathcal{D}$ and
$c^{\prime},\,c^{\prime\prime},\,c^{\prime\prime\prime}\in\mathcal{C}$ be the
unique elements such that $c_{1}c_{2}d_{1}=d^{\prime}c^{\prime}$,
$c_{2}d_{1}=d^{\prime\prime}c^{\prime\prime}$, and
$c_{1}d^{\prime\prime}=d^{\prime\prime\prime}c^{\prime\prime\prime}$. Then
$d^{\prime\prime\prime}(c^{\prime\prime\prime}c^{\prime\prime})=c_{1}d^{\prime\prime}c^{\prime\prime}=c_{1}c_{2}d_{1}=d^{\prime}c^{\prime}$,
so uniqueness of factorisations gives $(c_{1}c_{2})\triangleright
d_{1}=d^{\prime}=d^{\prime\prime\prime}=c_{1}\triangleright
d^{\prime\prime}=c_{1}\triangleright(c_{2}\triangleright d_{1})$. So
$\triangleright$ is an action of $\mathcal{C}$ on $\mathcal{D}$.

Now let $d^{\prime},\,d^{\prime\prime},\,d^{\prime\prime\prime}\in\mathcal{D}$
and $c^{\prime},\,c^{\prime\prime},\,c^{\prime\prime\prime}\in\mathcal{C}$ be
the unique elements such that $c_{2}d_{1}d_{2}=d^{\prime}c^{\prime}$,
$c_{2}d_{1}=d^{\prime\prime}c^{\prime\prime}$, and
$c^{\prime\prime}d_{2}=d^{\prime\prime\prime}c^{\prime\prime\prime}$. Then
$d^{\prime\prime}d^{\prime\prime\prime}c^{\prime\prime\prime}=d^{\prime}c^{\prime}$,
so uniqueness of factorisations gives
$c_{2}\triangleright(d_{1}d_{2})=d^{\prime}=d^{\prime\prime}d^{\prime\prime\prime}=(c_{2}\triangleright
d_{1})(c^{\prime\prime}\triangleright d_{2})=(c_{2}\triangleright
d_{1})((c_{2}\triangleleft d_{1})\triangleright d_{2})$, verifying (MP2).

Symmetrically, $\triangleleft$ defines a right action of $\mathcal{D}$ on
$\mathcal{C}$ satisfying (MP3). Condition (MP1) follows from the composition
laws in $\mathcal{E}$. ∎

######  Remark 3.14.

Proposition 3.13 says that the internal and external views of Zappa–Szép
products are equivalent. Given a matched pair $(\mathcal{C},\mathcal{D})$ we
can equivalently: (a) build the concrete product
$\mathcal{C}\bowtie\mathcal{D}$; or (b) say that $\mathcal{E}$ is a Zappa–Szép
product if it contains copies of $\mathcal{D}$ and $\mathcal{C}$ as wide
subcategories such that $[\mathcal{D},\mathcal{C}]$ is a strict factorisation
system implementing the given actions.

For $C^{*}$-algebraic representations à la Speilberg [Spe20] it is important
to know when a small category $\mathcal{C}$ is _left cancellative_ in the
sense that if $c_{1}c_{2}=c_{1}c_{3}$, then $c_{2}=c_{3}$. The following lemma
provides a sufficient condition under which Zappa–Szép products are left
cancellative.

######  Lemma 3.15.

If $(\mathcal{C},\mathcal{D})$ is matched pair in which $\mathcal{C}$ and
$\mathcal{D}$ are both left cancellative and for each $c\in\mathcal{C}$ the
map $c\triangleright{\cdot}\colon s(c)\mathcal{D}\to r(c)\mathcal{D}$ is
injective, then $\mathcal{C}\bowtie\mathcal{D}$ is left cancellative.

###### Proof.

Suppose that $d_{1}c_{1},d_{2}c_{2}\in\mathcal{C}\bowtie\mathcal{D}$ satisfy
$d_{1}c_{1}d_{2}c_{2}=d_{1}c_{1}d_{3}c_{3}$. Then $d_{1}(c_{1}\triangleright
d_{2})=d_{1}(c_{1}\triangleright d_{3})$ in $\mathcal{D}$ and
$(c_{1}\triangleleft d_{2})c_{2}=(c_{1}\triangleleft d_{3})c_{3}$ in
$\mathcal{C}.$ Since $\mathcal{D}$ is left cancellative, $c_{1}\triangleright
d_{2}=c_{1}\triangleright d_{3}$, and so injectivity of the left action gives
$d_{2}=d_{3}$. Consequently, $(c_{1}\triangleleft
d_{2})c_{2}=(c_{1}\triangleleft d_{2})c_{3}$. Left cancellation in
$\mathcal{C}$ implies that $c_{2}=c_{3}$, so $\mathcal{C}\bowtie\mathcal{D}$
is left cancellative. ∎

######  Example 3.16.

If $\mathcal{C}$ is a groupoid then it acts cancellatively on both itself and
$\mathcal{D}$ because it has inverses. So $\mathcal{C}\bowtie\mathcal{D}$ is
left-cancellative whenever $\mathcal{D}$ is.

###  3.2. Extending matched pairs to composable tuples

We define homology for matched pairs in terms of associated categories of
composable tuple, so it is important to understand how $\triangleright$ and
$\triangleleft$ extend to these categories.

######  Definition 3.17.

The _free category_ (or _path category_) of a small category $\mathcal{C}$ is
the category $\mathcal{C}^{*}$ with morphisms $\bigcup_{k\geq
0}\mathcal{C}^{k}$, identity morphisms $\mathcal{C}^{0}$, and composition (for
non-identity morphisms) given by concatenation.

######  Remark 3.18.

There is a subtlety here. The set $\mathcal{C}^{1}$ of 1-tuples in
$\mathcal{C}^{*}$ contains the 1-tuples $\\{(v)\mid v\in\mathcal{C}^{0}\\}$,
but this disjoint from $\mathcal{C}^{0}\subseteq\mathcal{C}^{*}$. This is
reflected in the composition law: for $v\in\mathcal{C}^{0}$ and
$(c_{1},\ldots,c_{k})\in\mathcal{C}^{k}$ with $r(c_{1})=v$, we have
$v(c_{1},\ldots,c_{k})=(c_{1},\ldots,c_{k})$ while
$(v)(c_{1},\ldots,c_{k})=(v,c_{1},\ldots,c_{k})$.

######  Lemma 3.19.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. Define
$\bowtie_{n}\colon\mathcal{C}*\mathcal{D}^{n}\to\mathcal{D}^{n}*\mathcal{C}$
inductively by $\bowtie_{1}\coloneqq\bowtie$, and

$\bowtie_{n}\coloneqq(1_{\mathcal{D}^{n-1}}*\bowtie)\circ(1_{\mathcal{C}}*\bowtie_{n-1})$

for $n\geq 2$. Define
$\bowtie_{*}\colon\mathcal{C}*\mathcal{D}^{*}\to\mathcal{D}^{*}*\mathcal{C}$
by
${\left.\kern-1.2pt{{}\operatorname{{\bowtie}}_{*}{}}\\!\vphantom{|}\right|_{\mathcal{C}*\mathcal{D}^{n}}}\coloneqq{}\operatorname{{\bowtie}}_{n}{}$.
Then

  1. (i)

for each $n\geq 1$ and $1\leq p<n$,

$\operatorname{{\bowtie}}_{n}=(1_{\mathcal{D}^{n-p}}*\operatorname{{\bowtie}}_{p})\circ(\operatorname{{\bowtie}}_{n-p}*1_{\mathcal{D}^{p}}),$
(3.5)

  2. (ii)

$\bowtie_{*}$ is a factorisation rule, and

  3. (iii)

if $\mu_{\mathcal{D}}\colon\mathcal{D}^{*}\to\mathcal{D}$ is the map
$\mu_{\mathcal{D}}(d_{1},d_{2},\ldots,d_{n})=d_{1}d_{2}\cdots d_{n}$, then
$(1_{\mathcal{C}},\mu_{\mathcal{D}})\colon(\mathcal{C},\mathcal{D}^{*})\to(\mathcal{C},\mathcal{D})$
is a matched-pair morphism.

###### Proof.

(i) When $n=1$, we have $p=1$, so (3.5) is vacuous. For $n\geq 2$, equation
(3.5) holds for $p=1$ by definition of $\bowtie_{n}$. Fix $n_{0}\geq 2$ and
$1\leq p_{0}\leq n_{0}$, and suppose inductively, that (3.5) holds for all
$n<n_{0}$ and $1\leq p<p_{0}$. In the diagram

${{\mathcal{C}*\mathcal{D}^{n_{0}}}}$${{\mathcal{D}^{n_{0}-p_{0}}*\mathcal{C}*\mathcal{D}^{p_{0}}}}$${{\mathcal{D}^{n_{0}}*\mathcal{C}}}$${{\mathcal{D}^{n_{0}-p_{0}+1}*\mathcal{C}*\mathcal{D}^{p_{0}-1}}}$$\scriptstyle{\operatorname{{\bowtie}}_{n_{0}-p_{0}}*1_{\mathcal{D}^{p_{0}}}}$$\scriptstyle{1_{\mathcal{D}^{n_{0}-p_{0}}}*\operatorname{{\bowtie}}_{p_{0}}}$$\scriptstyle{\operatorname{{\bowtie}}_{n_{0}-p_{0}+1}*1_{\mathcal{D}^{p-1}}}$$\scriptstyle{1_{\mathcal{D}^{n_{0}-p_{0}+1}}*\operatorname{{\bowtie}}_{p_{0}-1}}$$\scriptstyle{1_{\mathcal{D}^{n_{0}-p_{0}}}*\operatorname{{\bowtie}}*1_{\mathcal{D}^{p_{0}-1}}}$

the left-hand triangle commutes by the inductive definition of
$\bowtie_{n_{0}-p_{0}}$, and the right-hand triangle commutes by induction
since $p_{0}<n_{0}$. Since $p_{0}-1<p_{0}$, the composition of the maps along
the bottom of the triangle is $\bowtie_{n_{0}}$ by induction. So (3.5) holds
for all $n$ and $p$.

(ii) A routine induction verifies (FR1). To see that the first diagram of
(FR2) for $\bowtie_{*}$ commutes, consider the following diagram.

${\mathcal{C}^{2}*\mathcal{D}^{n+1}}$${\mathcal{C}*\mathcal{D}^{n+1}*\mathcal{C}}$${\mathcal{D}^{n+1}*\mathcal{C}^{2}}$${\mathcal{C}*\mathcal{D}^{n}*\mathcal{C}*\mathcal{D}}$${\mathcal{D}^{n}*\mathcal{C}*\mathcal{D}*\mathcal{C}}$${\mathcal{D}^{n}*\mathcal{C}^{2}*\mathcal{D}}$${\mathcal{C}*\mathcal{D}^{n+1}}$${\mathcal{D}^{n}*\mathcal{C}*\mathcal{D}}$${\mathcal{D}^{n+1}*\mathcal{C}}$$\scriptstyle{\mu_{\mathcal{C}}*1_{\mathcal{D}^{n+1}}}$$\scriptstyle{1_{\mathcal{C}}*\bowtie_{n+1}}$$\scriptstyle{1_{\mathcal{C}}*\bowtie_{n}*1_{\mathcal{D}}}$$\scriptstyle{\bowtie_{n+1}*1_{\mathcal{C}}}$$\scriptstyle{\bowtie_{n}*1_{\mathcal{D}*\mathcal{C}}}$$\scriptstyle{1_{\mathcal{D}^{n+1}}*\mu_{\mathcal{C}}}$$\scriptstyle{1_{\mathcal{C}*\mathcal{D}^{n}}*\bowtie}$$\scriptstyle{\bowtie_{n}*1_{\mathcal{C}*\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}^{n}}*\bowtie}$$\scriptstyle{1_{\mathcal{D}^{n}}*\mu_{\mathcal{C}}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}^{n}*\mathcal{C}}*\bowtie}$$\scriptstyle{\bowtie_{n}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}^{n}}*\bowtie}$

The central diamond clearly commutes, the top-left and top-right triangles
commute by the definition of $\bowtie_{n+1}$, and the bottom-right pentagon
commutes by (FR2) for $\bowtie$. The composition of the maps along the bottom
row of the diagram is $\bowtie_{n+1}$ by definition. So the whole diagram
commutes if and only if the bottom-left pentagon commutes. An induction now
shows that the first diagram of (FR2) commutes for $\bowtie_{*}$.

For $m,n\neq 0$, the multiplication map
$\mu_{\mathcal{D}^{*}}\colon\mathcal{D}^{m}*\mathcal{D}^{n}\to\mathcal{D}^{m+n}$
is the obvious bijection. So the second diagram of (FR2) commutes by (i).
Hence, $\bowtie_{*}$ is a factorisation rule.

(iii) By Lemma 3.4 and Corollary 3.10, it suffices to show that
$(\mu_{\mathcal{D}}*1_{\mathcal{C}})\circ\bowtie_{n}\colon\mathcal{C}*\mathcal{D}^{n}\to\mathcal{D}*\mathcal{C}$
and
$\bowtie\circ(1_{\mathcal{C}}*\mu_{\mathcal{D}})\colon\mathcal{C}*\mathcal{D}^{n}\to\mathcal{D}*\mathcal{C}$
are equal for all $n$. For $n=1$ this is trivial, so suppose equality holds
for $n-1$, and consider the following diagram.

${{\mathcal{C}*\mathcal{D}^{n}}}$${{\mathcal{D}^{n-1}*\mathcal{C}*\mathcal{D}}}$${{\mathcal{D}^{n}*\mathcal{C}}}$${{\mathcal{C}*\mathcal{D}^{2}}}$${{\mathcal{D}*\mathcal{C}*\mathcal{D}}}$${{\mathcal{D}^{2}*\mathcal{C}}}$${{\mathcal{C}*\mathcal{D}}}$${{\mathcal{D}*\mathcal{C}}}$$\scriptstyle{\operatorname{{\bowtie}}_{n-1}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}^{n-1}}*\bowtie}$$\scriptstyle{1_{\mathcal{C}}*\mu_{\mathcal{D}}*1_{\mathcal{D}}}$$\scriptstyle{\mu_{\mathcal{D}}*1_{\mathcal{C}*\mathcal{D}}}$$\scriptstyle{\mu_{\mathcal{D}}*1_{\mathcal{D}*\mathcal{C}}}$$\scriptstyle{\operatorname{{\bowtie}}*1_{\mathcal{D}}}$$\scriptstyle{1_{\mathcal{D}}*\bowtie}$$\scriptstyle{1_{\mathcal{C}}*\mu_{\mathcal{D}}}$$\scriptstyle{\operatorname{{\bowtie}}}$$\scriptstyle{\mu_{\mathcal{D}}*1_{\mathcal{C}}}$

The bottom pentagon commutes by (FR2) for $\bowtie$. The top-right square
clearly commutes. The top left square commutes by the inductive hypothesis,
and so the whole diagram commutes. The composition along the top row is equal
to $\bowtie_{n}$, and the composition along the left and right columns are
$1_{\mathcal{C}}*\mu_{\mathcal{D}}$ and $\mu_{\mathcal{D}}*1_{\mathcal{C}}$.
So
$(\mu_{\mathcal{D}}*1_{\mathcal{C}})\circ\bowtie_{n}=\bowtie\circ(1_{\mathcal{C}}*\mu_{\mathcal{D}})$.
∎

Lemmas 3.19 and 3.4 imply that $(\mathcal{C},\mathcal{D}^{*})$ is a matched
pair. The left action of $\mathcal{C}$ on $\mathcal{D}^{k}$ is given
explicitly by

$\displaystyle c\triangleright(d_{1},\ldots,d_{k})$
$\displaystyle\coloneqq(c\triangleright d_{1},(c\triangleleft
d_{1})\triangleright(d_{2},\ldots,d_{k}))$ $\displaystyle=(c_{1}\triangleright
d_{1},(c_{1}\triangleleft d_{1})\triangleright
d_{2},(c_{1}\triangleleft(d_{1}d_{2}))\triangleright
d_{3},\ldots,(c_{1}\triangleleft(d_{1}\cdots d_{k-1}))\triangleright d_{k}).$

and the right action of $\mathcal{D}^{k}$ on $\mathcal{C}$ is given by
$c\triangleleft(d_{1},\ldots,d_{k})=c\triangleleft(d_{1}\cdots d_{k}).$

We can also define
${{}\leftindex_{n}{\bowtie{}}}\colon\mathcal{C}^{n}*\mathcal{D}\to\mathcal{D}*\mathcal{C}^{n}$
inductively by ${{}\leftindex_{1}{\bowtie{}}}\coloneqq\bowtie$, and

$(c_{1},\ldots,c_{n})\leftindex_{n}{\bowtie{}}d=(\bowtie*1_{\mathcal{C}^{n-1}})((c_{2},\ldots,c_{n})\leftindex_{n-1}{\bowtie{}}d),$

and then
$\leftindex_{*}{\bowtie{}}\colon\mathcal{C}^{*}*\mathcal{D}\to\mathcal{D}*\mathcal{C}^{*}$
by
${\left.\kern-1.2pt\leftindex_{*}{\bowtie{}}\vphantom{|}\right|_{\mathcal{C}^{n}*\mathcal{D}}}=\leftindex_{n}{\bowtie{}}$.
Lemma 3.19 applied to opposite categories implies that
$\leftindex_{*}{\bowtie{}}$ is a factorisation rule with properties analogous
to those of $\bowtie_{*}$. The left action of $\mathcal{C}^{k}$ on
$\mathcal{D}$ is given by $(c_{1},\ldots,c_{k})\triangleright d=(c_{1}\cdots
c_{k})\triangleright d$ and the right action of $\mathcal{D}$ on
$\mathcal{C}^{k}$ is given by

$\displaystyle(c_{1},\ldots,c_{k})\triangleleft d$
$\displaystyle=((c_{1},\ldots,c_{k-1})\triangleleft(c_{k}\triangleright
d),c_{k}\triangleleft d)$ $\displaystyle=(c_{1}\triangleleft((c_{2}\cdots
c_{k})\triangleright
d),\ldots,c_{k-2}\triangleleft((c_{k-1}c_{k})\triangleright
d),c_{k-1}\triangleleft(c_{k}\triangleright d),c_{k}\triangleleft d).$

Since $(\mathcal{C}^{*},\mathcal{D})$ is itself a matched pair,
$(\mathcal{C}^{*},\mathcal{D}^{*})$ can also be equipped with the structure of
a matched pair via Lemma 3.19.

######  Proposition 3.20.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. For $m,n\geq 1$ define
$\bowtie_{m,n}\colon\mathcal{C}^{m}*\mathcal{D}^{n}\to\mathcal{D}^{n}*\mathcal{C}^{m}$
inductively by
$\bowtie_{1,n}\coloneqq{}\bowtie_{n}\colon\mathcal{C}*\mathcal{D}^{n}\to\mathcal{D}^{n}*\mathcal{C}$
and

$\bowtie_{m,n}\coloneqq(\bowtie_{n}*1_{\mathcal{C}^{m-1}})\circ(1_{\mathcal{C}}*\bowtie_{m-1,n}).$

Define
$\bowtie_{*,*}\colon\mathcal{C}^{*}*\mathcal{D}^{*}\to\mathcal{D}^{*}*\mathcal{C}^{*}$
by
${\bowtie_{*,*}}|^{\mbox{}}_{\mathcal{C}^{m}*\mathcal{D}^{n}}={\bowtie_{m,n}}$.
Then

  1. (i)

$\bowtie_{*,*}$ is a factorisation rule, and

  2. (ii)

$(\mu_{\mathcal{C}},\mu_{\mathcal{D}})\colon(\mathcal{C}^{*},\mathcal{D}^{*})\to(\mathcal{C},\mathcal{D})$
is a matched-pair morphism.

###### Proof.

That $(\mathcal{C},\mathcal{D}^{*})$ is a matched pair, together with an
additional application of Lemma 3.19, gives (i). Two applications of Lemma
3.19(iii) give (ii). ∎

We often write
$\bowtie\colon\mathcal{C}^{*}*\mathcal{D}^{*}\to\mathcal{D}^{*}*\mathcal{C}^{*}$
for the map $\bowtie_{*,*}$ of Proposition 3.20, which implies that
$\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$ is a category with strict
factorisation system $[\mathcal{D}^{*},\mathcal{C}^{*}]$. We identify
$\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$ as a set with
$\mathcal{D}^{*}*\mathcal{C}^{*}$. For each composable $k$-tuple
$\gamma\in\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$ there exist $p_{i},q_{i}\geq
0$ such that
$\gamma\in\mathcal{D}^{p_{1}}*\mathcal{C}^{q_{1}}*\cdots*\mathcal{D}^{p_{k}}*\mathcal{C}^{q_{k}}$;
its product belongs to
$\mathcal{D}^{p_{1}+\cdots+p_{k}}*\mathcal{C}^{q_{1}+\cdots+q_{k}}$.

The map $\bowtie_{m,n}$ can be computed in any order in the following sense.

######  Corollary 3.21.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. For each $1\leq p<m$ and
$1\leq q<n$, the diagram

${{\mathcal{C}^{m}*\mathcal{D}^{n}}}$${{\mathcal{D}^{n}*\mathcal{C}^{m}}}$${{\mathcal{C}^{m-p}*\mathcal{D}^{q}*\mathcal{C}^{p}*\mathcal{D}^{n-q}}}$${{\mathcal{D}^{q}*\mathcal{C}^{m-p}*\mathcal{D}^{n-q}*\mathcal{C}^{p}}}$$\scriptstyle{\operatorname{{\bowtie}}_{m,n}}$$\scriptstyle{1_{\mathcal{C}^{m-p}}*\operatorname{{\bowtie}}_{p,q}*1_{\mathcal{D}^{n-q}}}$$\scriptstyle{1_{\mathcal{D}^{q}}*\operatorname{{\bowtie}}_{m-p,n-q}*1_{\mathcal{C}^{p}}}$$\scriptstyle{\operatorname{{\bowtie}}_{m-p,q}*\operatorname{{\bowtie}}_{p,n-q}}$
(3.6)

commutes.

###### Proof.

Elements of
$\mathcal{C}^{m}*\mathcal{D}^{n}=\mathcal{C}^{m-p}*\mathcal{C}^{p}*\mathcal{D}^{q}*\mathcal{D}^{n-q}$
may considered as composable 4-tuples in
$\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$. Since the 3-map composition around
the bottom of (3.6) is an iterated product in
$\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$, uniqueness of factorisation implies
that the diagram commutes. ∎

Corollary 3.21 gives
$\bowtie_{m,n}=(1_{\mathcal{D}^{n-1}}*\bowtie_{m,1})\circ(\bowtie_{m,n-1}*1_{\mathcal{D}}).$
So we could also have applied Lemma 3.19 to $(\mathcal{C},\mathcal{D}^{*})$ to
obtain the matched-pair structure on $(\mathcal{C}^{*},\mathcal{D}^{*})$ of
Proposition 3.20.

###  3.3. Model matched pairs

We introduce a class of model categories that will play a central role in our
computation of homology (Theorem 5.3) below.

Let $X_{n}\coloneqq\\{(p,q)\in\mathbb{N}\times\mathbb{N}\mid 0\leq p+q\leq
n\\}$. We denote elements of $X_{n}$ using bold font. Given $\mathbf{a}\in
X_{n}$ we write $\mathbf{a}=(a_{L},a_{R})$ to indicate the left and right
coordinates of $\mathbf{a}$.

######  Definition 3.22.

Let $\Gamma_{n}=\\{(\mathbf{a},\mathbf{b})\in X_{n}\times X_{n}\mid a_{L}\leq
b_{L}\text{ and }a_{R}\geq b_{R}\\}$. Define $r,s\colon\Gamma_{n}\to X_{n}$ by
$r(\mathbf{a},\mathbf{b})=\mathbf{a}$ and
$s(\mathbf{a},\mathbf{b})=\mathbf{b}.$ Identify $X_{n}$ with
$\\{(\mathbf{a},\mathbf{a})\mid\mathbf{a}\in X_{n}\\}$.

With composition defined by
$(\mathbf{a},\mathbf{b})(\mathbf{b},\mathbf{c})\coloneqq(\mathbf{a},\mathbf{c})$,
the set $\Gamma_{n}$ is a small category. It can also be realised as the
Zappa–Szép product of the path categories of two graphs. Let $E_{n}$ be the
directed graph with $E_{n}^{0}=X_{n}$ and $E_{n}^{1}=\\{e_{p,q}\colon(p,q)\in
X_{n}\text{ and }p+q<n\\}$, with $r(e_{p,q})=(p,q)$ and $s(e_{p,q})=(p+1,q)$.
Let $F_{n}$ be the directed graph with $F_{n}^{0}=X_{n}$ and
$F_{n}^{1}=\\{f_{p,q}\colon(p,q)\in X_{n}\text{ and }p+q<n\\}$, with
$s(f_{p,q})=(p,q)$ and $r(f_{p,q})=(p,q+1)$. We draw $E_{n}$ and $F_{n}$ using
coloured arrows (blue and solid for $E$, red and dashed for $F$).

$E_{3}$$(0,0)$$(3,0)$$(0,3)$$e_{0,0}$$e_{1,0}$$e_{2,0}$$e_{0,1}$$e_{1,1}$$e_{0,2}$
$F_{3}$$(0,0)$$(3,0)$$(0,3)$$f_{0,0}$$f_{0,1}$$f_{0,2}$$f_{1,0}$$f_{1,1}$$f_{2,0}$

Let $\mathcal{F}_{n}\coloneqq F_{n}^{*}$ and $\mathcal{E}_{n}\coloneqq
E_{n}^{*}$ denote the path categories of $F_{n}$ and $E_{n}$, respectively.

######  Lemma 3.23.

The subcategory $\\{((p,q),(p^{\prime},q))\mid p\leq p^{\prime}\leq n,\,q\leq
n\\}$ of $\Gamma_{n}$ is isomorphic to $\mathcal{E}_{n}$ and the subcategory
$\\{((p,q),(p,q^{\prime}))\mid p\leq n,\,n\geq q\geq q^{\prime}\\}$ is
isomorphic to $\mathcal{F}_{n}$. Moreover, $[\mathcal{F}_{n},\mathcal{E}_{n}]$
is a strict factorisation system for $\Gamma_{n}$; the pair
$(\mathcal{E}_{n},\mathcal{F}_{n})$ is a matched pair, with

$e_{p,q}\triangleright f_{p+1,q-1}=f_{p,q-1}\quad\text{and}\quad
e_{p,q}\triangleleft f_{p+1,q-1}=e_{p,q-1};$

and $\Gamma_{n}\cong\mathcal{E}_{n}\bowtie\mathcal{F}_{n}$.

###### Proof.

Since $\mathcal{E}_{n}$ is freely generated by $E_{n}$, the map
$e_{p,q}\mapsto((p,q),(p+1,q))$ identifies $\mathcal{E}_{n}$ with
$\\{((p,q),(p^{\prime},q))\mid p\leq p^{\prime}\\}$. Similarly,
$\mathcal{F}_{n}\cong\\{((p,q),(p,q^{\prime}))\mid q\geq q^{\prime}\\}$ via
$f_{p,q}\mapsto((p,q+1),(p,q))$.

Both $\mathcal{E}_{n}$ and $\mathcal{F}_{n}$ are clearly wide subcategories.
For each $(\mathbf{a},\mathbf{b})\in\Gamma_{n}$,
$\alpha\coloneqq((a_{L},a_{R}),(a_{L},b_{R}))$ and
$\beta\coloneqq((a_{L},b_{R}),(b_{L},b_{R}))$ are the unique elements of
$\mathcal{F}_{n}$ and $\mathcal{E}_{n}$, respectively such that
$(\mathbf{a},\mathbf{b})=\alpha\beta$. So $[\mathcal{F}_{n},\mathcal{E}_{n}]$
is a strict factorisation system for $\Gamma_{n}$.

The remaining statements follow from Proposition 3.13. ∎

######  Definition 3.24.

We refer to the matched pairs $(\mathcal{E}_{n},\mathcal{F}_{n})$ as _model
matched pairs_.

Each $\Gamma_{n}$ can be visualised as a commuting diagram incorporating both
$E_{n}$ and $F_{n}$.

$\Gamma_{0}$$(0,0)$ $\Gamma_{1}$$(0,0)$$(1,0)$$(0,1)$$e_{0,0}$$f_{0,0}$
$\Gamma_{2}$$(0,0)$$(2,0)$$(0,2)$$e_{0,0}$$e_{1,0}$$e_{0,1}$$f_{0,0}$$f_{0,1}$$f_{1,0}$
$\Gamma_{3}$$(0,0)$$(3,0)$$(0,3)$$e_{0,0}$$e_{1,0}$$e_{2,0}$$e_{0,1}$$e_{1,1}$$e_{0,2}$$f_{0,0}$$f_{0,1}$$f_{0,2}$$f_{1,0}$$f_{1,1}$$f_{2,0}$
(3.7)

For each $n$, we draw $E_{n}$ and $F_{n}$ on the same vertex set. Each picture
in (3.7) is a commuting diagram in the corresponding $\Gamma_{n}$. A morphism
$(\mathbf{a},\mathbf{b})\in\Gamma_{n}$ is equal to the composition of any of
the paths in (3.7) from the vertex at $\mathbf{b}$ to the one at $\mathbf{a}$.

The matched pairs $(\mathcal{E}_{n},\mathcal{F}_{n})$ are—in the following
sense— _free_ in the category ${\mathsf{MP}}$.

######  Lemma 3.25.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. For every
$\gamma=(d_{0}c_{0},\ldots,d_{n-1}c_{n-1})\in(\mathcal{C}\bowtie\mathcal{D})^{n}$,
there is a unique matched pair morphism
$h_{\gamma}\colon(\mathcal{E}_{n},\mathcal{F}_{n})\to(\mathcal{C},\mathcal{D})$
such that for all $0\leq k<n$,

$h_{\gamma}^{L}(e_{k,n-1-k})=c_{k}\quad\text{and}\quad
h_{\gamma}^{R}(f_{k,n-1-k})=d_{k}.$ (3.8)

Moreover, every matched pair morphism
$(\mathcal{E}_{n},\mathcal{F}_{n})\to(\mathcal{C},\mathcal{D})$ is of this
form.

###### Proof.

For each $0\leq k<n$ let $d_{k,n-1-k}\coloneqq d_{k}$ and
$c_{k,n-1-k}\coloneqq c_{k}$, and for each $0\leq p+q<n-1$ define
$d_{p,q}\in\mathcal{D}$ and $c_{p,q}\in\mathcal{C}$ inductively by
$d_{p,q}\coloneqq c_{p,q+1}\triangleright d_{p+1,q}$ and $c_{p,q}\coloneqq
c_{p,q+1}\triangleleft d_{p+1,q}$. Since $\mathcal{E}_{n}$ is freely generated
by edges, there is a unique functor
$h_{\gamma}^{L}\colon\mathcal{E}_{n}\to\mathcal{C}$ satisfying
$h_{\gamma}^{L}(e_{p,q})=c_{p,q}$ for all $0\leq p+q<n$. Similarly there is a
unique functor $h_{\gamma}^{R}\colon\mathcal{F}_{n}\to\mathcal{D}$ satisfying
$h_{\gamma}^{R}(f_{p,q})=d_{p,q}$. Since $d_{p,q}c_{p,q}=c_{p,q+1}d_{p+1,q}$,
it follows that $h_{\gamma}=(h_{\gamma}^{L},h_{\gamma}^{R})$ is a morphism of
matched pairs.

For uniqueness, fix a matched pair morphism
$h\colon(\mathcal{E}_{n},\mathcal{F}_{n})\to(\mathcal{C},\mathcal{D})$. Then
$h^{L}(e_{p,q})=h^{L}(e_{p,q+1}\triangleleft
f_{p+1,q})=h^{L}(e_{p,q+1})\triangleleft h^{R}(f_{p+1,q})$ and similarly
$h^{R}(f_{p,q})=h^{L}(e_{p,q+1})\triangleright h^{R}(f_{p+1,q})$. Since
$h^{L}\colon\mathcal{E}_{n}\to\mathcal{C}$ and
$h^{R}\colon\mathcal{F}_{n}\to\mathcal{D}$ are functors, $h^{L}$ and $h^{R}$
are determined by the values $h^{L}(e_{k,n-1-k})$ and $h^{R}(f_{k,n-1-k})$ for
$0\leq k<n$. So $h_{\gamma}$ is uniquely determined by (3.8). ∎

Corollary 3.10 says that $h_{\gamma}$ is the unique functor
$\Gamma_{n}\to\mathcal{C}\bowtie\mathcal{D}$ such that
$h_{\gamma}(f_{k,n-1-k}e_{k,n-1-k})=d_{k}c_{k}$ for all $0\leq k<n$.

###  3.4. Further examples

####  3.4.1. $k$-graphs

Here we describe $k$-graphs [KP00] using matched pairs. The generalisations of
higher-rank graphs of [LawV22] also fit into our framework, but we do not
discuss them here.

######  Definition 3.26.

A _$k$ -graph_ is a countable category $\Lambda$ together with a functor
$d\colon\Lambda\to\mathbb{N}^{k}$, called the _degree map_ , which satisfies
the following factorisation property: if $d(\lambda)=m+n$, then there exist
unique elements $\mu,\nu\in\Lambda$ such that $\lambda=\mu\nu$, $d(\mu)=m$ and
$d(\nu)=n$. For each $n\in\mathbb{N}^{k}$, we define $\Lambda^{n}\coloneqq
d^{-1}(n)$.

We show that every $(k_{1}+k_{2})$-graph is a Zappa–Szép product of a
$k_{1}$-graph and a $k_{2}$-graph.

######  Lemma 3.27.

Fix $k_{1},k_{2}\in\mathbb{N}$ and let $\Sigma$ be a $(k_{1}+k_{2})$-graph.
Let $\Lambda\coloneqq d^{-1}(\mathbb{N}^{k_{1}}\times\\{0\\})$ regarded as a
$k_{1}$-graph, and let $\Gamma\coloneqq
d^{-1}(\\{0\\}\times\mathbb{N}^{k_{2}})$ regarded as a $k_{2}$-graph. There
are unique actions $\triangleright$ of $\Lambda$ on $\Gamma$ and
$\triangleleft$ of $\Gamma$ on $\Lambda$ such that
$\lambda\gamma=(\lambda\triangleright\gamma)(\lambda\triangleleft\gamma)$ in
$\Sigma$ for all composable pairs $(\lambda,\gamma)\in\Lambda*\Gamma$. These
make $(\Lambda,\Gamma,\triangleright,\triangleleft)$ a matched pair, and
$(\gamma,\lambda)\mapsto\gamma\lambda$ is an isomorphism
$\Lambda\bowtie\Gamma\to\Sigma$. We have
$d(\lambda\triangleright\gamma)=d(\gamma)$ and
$d(\lambda\triangleleft\gamma)=d(\lambda)$ for all $\lambda,\gamma$.

###### Proof.

Everything except the final statement follows the factorisation property and
Proposition 3.13. The final statement follows from the factorisation property.
∎

We now describe a converse to Lemma 3.27. An _edge_ in a $k$-graph is a path
$e$ such that $d(e)$ is a standard generator of $\mathbb{N}^{k}$. We write
$E(\Lambda)$ for the set of edges of $\Lambda$. Let
$\Sigma,\Lambda,\Gamma,\triangleright$ and $\triangleleft$ be as in Lemma
3.27, and write $d_{\Lambda}\colon\Lambda\to\mathbb{N}^{k_{1}}$ and
$d_{\Gamma}\colon\Gamma\to\mathbb{N}^{k_{2}}$ for the degree functors. Then

  1. (K1)

$s(\nu\triangleright\mu)=r(\nu\triangleleft\mu)$ for all $(\nu,\mu)\in
E(\Lambda)*E(\Gamma)$;

  2. (K2)

$\nu_{1}\nu_{2}\triangleleft\mu=(\nu_{1}\triangleleft(\nu_{2}\triangleright\mu))(\nu_{2}\triangleleft\mu)$
for all $(\nu_{1},\nu_{2},\mu)\in E(\Lambda)*E(\Lambda)*E(\Gamma)$,

  3. (K3)

$\nu\triangleright\mu_{1}\mu_{2}=(\nu\triangleright\mu_{1})((\nu\triangleleft\mu_{1})\triangleright\mu_{2})$
for all $(\nu,\mu_{1},\mu_{2})\in E(\Lambda)*E(\Gamma)*E(\Gamma)$,

  4. (K4)

$d_{\Gamma}(\nu\triangleright\mu)=d_{\Gamma}(\mu)$ and
$d_{\Lambda}(\nu\triangleleft\mu)=d_{\Lambda}(\nu)$ for all $(\nu,\mu)\in
E(\Lambda)*E(\Gamma)$, and

  5. (K5)

for each $(\mu,\nu)\in E(\Gamma)*E(\Lambda)$ there exists a unique
$\mu^{\prime}\in E(\Gamma)$ and $\nu^{\prime}\in E(\Lambda)$ such that
$\mu=\nu^{\prime}\triangleright\mu^{\prime}$ and
$\nu=\nu^{\prime}\triangleleft\mu^{\prime}$.

######  Lemma 3.28.

Let $\Lambda$ be a $k_{1}$-graph and let $\Gamma$ be a $k_{2}$-graph such that
$\Lambda^{0}=\Gamma^{0}$. Suppose that
$\triangleright\colon\Lambda*\Gamma\to\Gamma$ and
$\triangleleft\colon\Lambda*\Gamma\to\Gamma$ are actions satisfying (K1)–(K5).
Then $(\Lambda,\Gamma)$ is a matched pair, and the map
$d\colon\Lambda\bowtie\Gamma\to\mathbb{N}^{k_{1}+k_{2}}$ given by
$d(\gamma,\lambda)=(d_{\Lambda}(\lambda),d_{\Gamma}(\gamma))$ makes
$\Lambda\bowtie\Gamma$ into a $(k_{1}+k_{2})$-graph.

###### Proof.

Let $E$ be directed graph with edges $E^{1}=E(\Lambda)\sqcup E(\Gamma)$,
vertices $E^{0}=\Lambda^{0}=\Gamma^{0}$ and range and source maps inherited
from $\Lambda$ and $\Gamma$. Define $c\colon
E^{1}\to\\{1,\dots,k_{1}+k_{2}\\}$ by $c(\alpha)=i$ if
$\alpha\in\Lambda^{e_{i}}$ and $c(\alpha)=k_{1}+j$ if
$\alpha\in\Gamma^{e_{j}}$, which we regard as a colouring of $E^{1}$ by
$k_{1}+k_{2}$ colours. Define a collection of squares in the sense of [HRSW13,
LarV22] by $\alpha\beta\sim\beta^{\prime}\alpha^{\prime}$ if

  * •

$\alpha\beta=\beta^{\prime}\alpha^{\prime}$ in one of $\Lambda$ or $\Gamma$,
or

  * •

$\alpha\in E(\Lambda)$ and $\beta\in E(\Gamma)$ and
$\alpha\triangleright\beta=\beta^{\prime}$ and
$\alpha\triangleleft\beta=\alpha^{\prime}$, or

  * •

$\alpha\in E(\Gamma)$ and $\beta\in E(\Lambda)$ and
$\alpha^{\prime}\triangleright\beta^{\prime}=\beta$ and
$\alpha^{\prime}\triangleleft\beta^{\prime}=\alpha$.

The factorisation properties and (K5) ensure that this is a complete
collection of squares.

We claim that this is an associative collection of squares. For this we must
check that if $\alpha,\beta,\gamma\in E^{1}$ are composable and of distinct
colours, and if

$\displaystyle\alpha\beta$ $\displaystyle\sim\beta_{1}\alpha_{1},$
$\displaystyle\alpha_{1}\gamma$ $\displaystyle\sim\gamma_{1}\alpha_{2},$ and
$\displaystyle\beta_{1}\gamma_{1}$ $\displaystyle\sim\gamma_{2}\beta_{2};$ and
$\displaystyle\beta\gamma$ $\displaystyle\sim\gamma^{1}\beta^{1},$
$\displaystyle\alpha\gamma^{1}$ $\displaystyle\sim\gamma^{2}\alpha^{1},$ and
$\displaystyle\alpha^{1}\beta^{1}$ $\displaystyle\sim\beta^{2}\alpha^{2};$

then $\alpha^{2}=\alpha_{2}$, $\beta^{2}=\beta_{2}$ and
$\gamma^{2}=\gamma_{2}$.

If $\alpha,\beta,\gamma$ all belong to either $\Lambda$ or $\Gamma$, this
follows from associativity of composition, so we just need to consider when
this is not the case. We treat the case where $\alpha\in\Lambda$ and
$\beta,\gamma\in\Gamma$; the calculations for the other cases are similarly
straightforward. We have

$\beta_{1}=\alpha\triangleright\beta,\quad\alpha_{1}=\alpha\triangleleft\beta,\quad\gamma_{1}=\alpha_{1}\triangleright\gamma,\quad\alpha_{2}=\alpha_{1}\triangleleft\gamma,\text{
and }\quad\beta_{1}\gamma_{1}=\gamma_{2}\beta_{2}\text{ in $\Gamma$}.$

That is,
$\gamma_{2}\beta_{2}=(\alpha\triangleright\beta)((\alpha\triangleleft\beta)\triangleright\gamma)=\alpha\triangleright(\beta\gamma)$,
and
$\alpha_{2}=(\alpha\triangleleft\beta)\triangleleft\gamma=\alpha\triangleleft(\beta\gamma)$.
Similarly,

$\beta\gamma=\gamma^{1}\beta^{1},\quad\gamma^{2}=\alpha\triangleright\gamma^{1},\quad\alpha^{1}=\alpha\triangleleft\gamma^{1},\quad\beta^{2}=\alpha^{1}\triangleright\beta^{1},\text{
and }\quad\alpha^{2}=\alpha^{1}\triangleleft\beta^{1}.$

That is,
$\gamma^{2}\beta^{2}=\alpha\triangleright(\gamma^{1}\beta^{1})=\alpha\triangleright(\beta\gamma)$,
and
$\alpha^{2}=(\alpha\triangleleft\gamma^{1})\triangleleft\beta^{1}=\alpha\triangleleft(\gamma^{1}\beta^{1})=\alpha\triangleleft(\beta\gamma)$.
So $\gamma^{2}\beta^{2}=\gamma_{2}\beta_{2}$ forcing $\gamma^{2}=\gamma_{2}$
and $\beta^{2}=\beta_{2}$ by uniqueness of factorisations in $\Gamma$, and
$\alpha^{2}=\alpha_{2}$.

By [HRSW13, Theorem 4.4] there is a unique $(k_{1}+k_{2})$-graph $\Sigma$ with
skeleton $E$ and the specified factorisation rules. Lemma 3.27, yields a
$k_{1}$-graph $\Lambda^{\prime}$ and a $k_{2}$-graph $\Gamma^{\prime}$ such
that $\Sigma\cong\Lambda^{\prime}\bowtie\Gamma^{\prime}$. By construction,
$\Lambda^{\prime}$ has the same skeleton and factorisation rules as $\Lambda$
so they are isomorphic by [HRSW13, Theorem 4.5] (see also [LarV22]), and
likewise $\Gamma^{\prime}\cong\Gamma$. These isomorphisms intertwine the
actions of $\Lambda^{\prime}$ and $\Gamma^{\prime}$ on one another with those
of $\Lambda$ and $\Gamma$. ∎

Taken together, Lemmas 3.27 and 3.28 prove the following.

######  Proposition 3.29.

Let $\Gamma$ be a $k_{1}$-graph and let $\Lambda$ be a $k_{2}$-graph with
actions $\triangleright\colon\Lambda*\Gamma\to\Gamma$ and
$\triangleleft\colon\Lambda*\Gamma\to\Gamma$ satisfying (K1)–(K5). The
Zappa–Szép product $\Lambda\bowtie\Gamma$ is a $(k_{1}+k_{2})$-graph.
Moreover, every $(k_{1}+k_{2})$-graph $\Pi$ is isomorphic to the Zappa–Szép
product of the $k_{1}$-graph $\Lambda=d^{-1}(\mathbb{N}^{k+1}\times\\{0\\})$
and the $k_{2}$-graph $\Gamma=d^{-1}(\\{0\\}\times\mathbb{N}^{k_{2}})$ with
actions satisfying (K1)–(K5).

####  3.4.2. Self-similar actions

We discuss self-similar actions of groupoids on $k$-graphs as in [ABRW19].
These include self-similar actions of groupoids and of groups on graphs as in
[Nek05, EP17, LRRW14, LRRW18]. We show that each such self-similar action
determines a matched pair in which the left action respects the degree map.
Later we will study $C^{*}$-algebras associated to such matched pairs; the
framework of matched pairs allows us to dispense with the faithfulness
condition traditionally imposed in the study of self-similar actions.

Recall that an edge in a $k$-graph is a path $f$ with $d(f)=e_{i}$ for some
$i\leq k$.

######  Definition 3.30 ([LRRW18, Definition 3.3]).

Let $\Lambda$ be a $k$-graph and let $\mathcal{G}$ be a groupoid with
$\mathcal{G}^{0}=\Lambda^{0}$. A _faithful self-similar action_ of
$\mathcal{G}$ on $\Lambda$ is a left action
$\cdot\colon\mathcal{G}*\Lambda\to\Lambda$ of $\mathcal{G}$ on $\Lambda$ such
that

  1. (SSA1)

for each $n\in\mathbb{N}^{k}$ and $g\in\mathcal{G}$, we have
$g\cdot(s(g)\Lambda^{n})=r(g)\Lambda^{n}$, and

  2. (SSA2)

$s(g_{1})=s(g_{2})$ and $g_{1}\cdot\mu=g_{2}\cdot\mu$ for all $\mu\in
s(g_{1})\Lambda$, then $g_{1}=g_{2}$.

  3. (SSA3)

for every $g\in\mathcal{G}$ and every edge $e\in s(g)\Lambda$ there exists
$h\in s(e)\mathcal{G}$ such that $g\cdot(e\mu)=(g\cdot e)(h\cdot\mu)$ for all
$\mu\in s(e)\Lambda$.

######  Remark 3.31.

If $\mathcal{G}$ acts self-similarly on $\Lambda$ then (SSA2) implies that
there is a unique $h$ satisfying (SSA3). We denote this element by
${\left.\kern-1.2ptg\vphantom{|}\right|_{e}}$ and call it the _restriction_ of
$g$ to $\mu$.

As discussed immediately after Definition 3.3 in [ABRW19], the map
$g\mapsto{\left.\kern-1.2ptg\vphantom{|}\right|_{e}}$ extends to a map
$(g,\mu)\mapsto{\left.\kern-1.2ptg\vphantom{|}\right|_{\mu}}$ from
$\mathcal{G}*\Lambda$ to $\Lambda$ by the recursive formula
${\left.\kern-1.2ptg\vphantom{|}\right|_{e\mu}}={\left.\kern-1.2pt({\left.\kern-1.2ptg\vphantom{|}\right|_{e}})\vphantom{|}\right|_{({\left.\kern-1.2ptg\vphantom{|}\right|_{e}})\cdot\mu}}$.

######  Proposition 3.32.

Let $\Lambda$ be a $k$-graph and $\mathcal{G}$ a groupoid with
$\mathcal{G}^{0}=\Lambda^{0}$. Suppose that
$\cdot\colon\mathcal{G}*\Lambda\to\Lambda$ is a faithful self-similar action.
Define $\triangleright\colon\mathcal{G}*\Lambda\to\Lambda$ by
$g\triangleright\mu=g\cdot\mu$ and
$\triangleleft\colon\mathcal{G}*\Lambda\to\mathcal{G}$ by
$g\triangleleft\mu={\left.\kern-1.2ptg\vphantom{|}\right|_{\mu}}$. Then
$(\mathcal{G},\Lambda,\triangleright,\triangleleft)$ is a matched pair such
that

  1. (i)

if $g_{1}\triangleright\mu=g_{2}\triangleright\mu$ for all $\mu\in
s(g_{1})\Lambda$, then $g_{1}=g_{2}$, and

  2. (ii)

$d(g\triangleright\mu)=d(\mu)$ for all $(g,\mu)\in\mathcal{G}*\Lambda$.

Conversely, if $(\mathcal{G},\Lambda,\triangleright,\triangleleft)$ is a
matched pair satisfying (i) and (ii), then $\triangleright$ defines a faithful
self-similar action of $\mathcal{G}$ on $\Lambda$ with restriction map
${\left.\kern-1.2ptg\vphantom{|}\right|_{\mu}}\coloneqq g\triangleleft\mu$.

###### Proof.

First suppose that $\cdot\colon\mathcal{G}*\Lambda\to\Lambda$ is a faithful
self-similar action. That $d(g\triangleright\mu)=d(\mu)$ for all
$(g,\mu)\in\mathcal{G}*\Lambda$ follows from (SSA1), and [ABRW19, Lemma 3.4]
implies that $(\mathcal{G},\Lambda)$ is a matched pair. Condition (i) follows
from (SSA2).

Conversely, suppose that $(\mathcal{G},\Lambda)$ is a matched pair satisfying
(i) and (ii). Then for each $g\in\mathcal{G}$ and each edge $e\in
s(g)\Lambda$, the element $h\coloneqq g\triangleright\mu$ satisfies (SSA3).
The condition (MP2) gives (SSA3). That $d(g\triangleright\mu)=d(\mu)$ for all
$(g,\mu)\in\mathcal{G}*\Lambda$ implies that $g\triangleright\cdot$ restricts
to a map $g\triangleright\cdot\colon s(g)\Lambda^{n}\to r(g)\Lambda^{n}$.
Invertibility of $g$ implies that these maps are bijective, giving (SSA1).
Condition (i) implies (SSA2). ∎

Motivated by Proposition 3.32 we introduce a generalisation of the faithful
self-similar actions of [ABRW19] (this is related to the definition in
[LY21]).

######  Definition 3.33.

A _self-similar action of a groupoid on a $k$-graph_ is a matched pair
$(\mathcal{G},\Lambda)$ in which $\mathcal{G}$ is a groupoid, $\Lambda$ is a
$k$-graph, and $d(g\triangleright\mu)=d(\mu)$ for all
$(g,\mu)\in\mathcal{G}*\Lambda$.

######  Example 3.34.

Let $E=(E^{0},E^{1},r,s)$ be a directed graph as in Section 2. Then $E^{*}$ is
a $1$-graph with degree map given by the length functor. Moreover, every
$1$-graph is of this form. The definition of a faithful self-similar action of
$\mathcal{G}$ on $E^{*}$ as above reduces to the definition of a self-similar
action of a groupoid on a graph in [LRRW18]. This in turn generalises the
self-similar groups of automorphisms of trees discussed in, for example,
[Nek05] (these correspond to the case where $E$ has just one vertex). The
definitions in [EP17] and [Yus23], which do not impose a faithfulness
condition, are also instances Definition 3.33 with $k=1$.

####  3.4.3. Graphs of groups and group actions on trees

An _undirected graph_
$\Gamma=(\Gamma^{0},\Gamma^{1},r,s,\overline{\,\cdot\,})$ is a directed graph
endowed with a map $\overline{\,\cdot\,}\colon\Gamma^{1}\to\Gamma^{1}$ such
that $\overline{\overline{e}}=e\neq\overline{e}$ and $r(\overline{e})=s(e)$
for all $e$.

######  Definition 3.35.

A _graph of groups_ is a pair $(\Gamma,G)$ consisting of: an undirected graph
$\Gamma$; assignments $v\mapsto G_{v}$ and $e\mapsto G_{e}$ of a group to each
$v\in\Gamma^{0}$ and $e\in\Gamma^{1}$, such that $G_{e}=G_{\overline{e}}$ for
all $e\in\Gamma^{1}$; and injective homomorphisms $\alpha_{e}\colon G_{e}\to
G_{r(e)}$ for each $e\in\Gamma^{1}$.

The Bass–Serre Theorem [Bas93, Ser80] describes a duality between graphs of
groups and edge-reversal-free actions of groups on trees.

Building on the observations of [MR21, Theorem 5.4], we show that every graph
of groups $(\Gamma,G)$ gives rise to a matched pair. For each
$e\in\Gamma^{1}$, let $\Sigma_{e}$ be a complete set of coset representatives
for $G_{r(e)}/\alpha_{e}(G_{e})$. We assume that $1_{G_{r(e)}}\in\Sigma_{e}$
so $1_{G_{r(e)}}$ is the representative of the coset $\alpha_{e}(G_{e})$.
There is a natural action of $G_{r(e)}$ on $\Sigma_{e}$: we define $g\cdot\mu$
to be the coset representative of $g\mu$ for all $g\in G_{r(e)}$ and
$\mu\in\Sigma_{e}$.

Consider the groupoid $\mathcal{G}=\bigsqcup_{e\in\Gamma^{1}}G_{e}$, a bundle
of groups over $\Gamma^{1}$. Define a directed graph $E$ by
$E^{0}\coloneqq\Gamma^{1}$,

$E^{1}\coloneqq\\{e\mu
f\mid\mu\in\Sigma_{e},\,ef\in\Gamma^{2},\,e=\overline{f}\implies\mu\neq
1_{G_{r(e)}}\\},$

$r(e\mu f)=e$, and $s(e\mu f)=f$. We identify each $E^{n}$ with

$\\{e_{0}\mu_{1}e_{1}\mu_{2}e_{2}\cdots\mu_{n}e_{n}\mid\mu_{i}\in\Sigma_{e_{i}},\,e_{0}\ldots
e_{n}\in\Gamma^{n+1},\,e_{i-1}=\overline{e_{i}}\implies\mu_{i}\neq
1_{r(e_{i})}\\}.$

Consider the path category $E^{*}$ of $E$. We show that $(\mathcal{G},E^{*})$
can be made into matched pair (indeed, a self-similar groupoid action as in
Example 3.34).

Fix $ef\in\Gamma^{2}$, $g\in G_{e}$ and $\mu\in\Sigma_{f}$. Then
$g\blacktriangleright\mu\coloneqq\alpha_{\overline{e}}(g)\cdot\mu\in\Sigma_{f}$
and
$g\blacktriangleleft\mu\coloneqq\alpha_{f}^{-1}((g\blacktriangleright\mu)^{-1}\alpha_{\overline{e}}(g)\mu)\in
G_{f}$ are the unique elements such that
$\alpha_{\overline{e}}(g)\mu=(g\blacktriangleright\mu)\alpha_{f}(g\blacktriangleleft\mu)$.

As in the proof of Proposition 3.13, for $g_{1},g_{2}\in G_{e}$, we have
$(g_{1}g_{2})\blacktriangleright\mu=g_{1}\cdot(g_{2}\blacktriangleright\mu)$
and
$(g_{1}g_{2})\blacktriangleleft\mu=(g_{1}\blacktriangleleft(g_{2}\blacktriangleright\mu))(g_{2}\blacktriangleleft\mu)$.
We define a left action $\triangleright\colon\mathcal{G}*E^{*}\to E^{*}$
inductively by

$g\triangleright
e_{0}\mu_{1}e_{1}\mu_{2}e_{2}\cdots\mu_{n}e_{n}=(e_{0}(g\blacktriangleright\mu_{1})e_{1})((g\blacktriangleleft\mu_{1})\triangleright
e_{1}\mu_{2}e_{2}\cdots\mu_{n}e_{n}),$

and a right action $\triangleleft\colon\mathcal{G}*E^{*}\to\mathcal{G}$
inductively by

$g\triangleleft
e_{0}\mu_{1}e_{1}\mu_{2}e_{2}\cdots\mu_{n}e_{n}=(g\blacktriangleleft\mu_{1})\triangleleft
e_{1}\mu_{2}e_{2}\cdots\mu_{n}e_{n}.$

It is straightforward to verify that these actions turn $(\mathcal{G},E^{*})$
into a matched pair. Moreover, $\triangleright,\triangleleft$ satisfy
(SSA1)–(SSA3) so $\mathcal{G}$ acts self-similarly on $E^{*}$.

##  4\. Three homology theories for matched pairs

We describe three homology theories associated to a matched pair (the last two
via a double complex). We show in Section 5 that they all coincide up to
natural isomorphism.

###  4.1. The categorical complex and categorical homology

######  Definition 4.1.

Let $\mathcal{C}$ be a small category. For each $k\geq 0$ let
$C_{k}(\mathcal{C})\coloneqq\mathbb{Z}\mathcal{C}^{k}$ be the free abelian
group generated by composable $k$-tuples. We write $[c_{0},\ldots,c_{k}]\in
C_{k+1}(\mathcal{C})$ for the generator corresponding to
$(c_{0},\ldots,c_{k})\in\mathcal{C}^{k+1}$. For $k\geq 1$ define $d_{k}\colon
C_{k+1}(\mathcal{C})\to C_{k}(\mathcal{C})$ by

$d_{k}[c_{0},\ldots,c_{k}]=[c_{1},\ldots,c_{k}]+\Big{(}\sum_{i=1}^{k}(-1)^{i}[c_{0},\ldots,c_{i-1}c_{i},\ldots,c_{k}]\Big{)}+(-1)^{k+1}[c_{0},\ldots,c_{k-1}]$

and define $d_{0}\colon C_{1}(\mathcal{C})\to C_{0}(\mathcal{C})$ by
$d_{0}[c]=[s(c)]-[r(c)]$. Then $(C_{\bullet}(\mathcal{C}),d_{\bullet})$ is a
chain complex, and its homology, $H_{\bullet}(\mathcal{C})$, is called the
_categorical homology of $\mathcal{C}$_.

For an abelian group $A$, let
$C^{k}(\mathcal{C};A)\coloneqq\operatorname{Hom}(C_{k}(\mathcal{C}),A)$.
Define $d^{k}\colon C^{k}(\mathcal{C};A)\to C^{k+1}(\mathcal{C};A)$ by
$d^{k}(f)=f\circ d_{k}$. Then $(C^{\bullet}(\mathcal{C};A),d^{\bullet})$ is a
cochain complex, and its cohomology, $H^{\bullet}(\mathcal{C};A)$, is called
the _categorical cohomology of $\mathcal{C}$ with coefficients in $A$_.

There are more-sophisticated definitions of categorical cohomology in terms of
projective resolutions of $\mathcal{C}$-modules (cf. [GK18]). Our definition
amounts to fixing a resolution, analogous to the _bar resolution_ for group
homology (cf. [Wei94, §6.5]), of a constant functor $\mathcal{C}\to A$ (see
[GK18, Proposition 2.4])

######  Definition 4.2.

The _categorical homology_ , denoted
$H^{\bowtie}_{\bullet}(\mathcal{C},\mathcal{D})$, of a matched pair
$(\mathcal{C},\mathcal{D})$ is the categorical homology of the Zappa–Szép
product category $\mathcal{C}\bowtie\mathcal{D}$. For each $k\geq 0$,
$H_{k}^{\bowtie}\colon{\mathsf{MP}}\to{\mathsf{Ab}}$ is functor defined by the
composition
$(\mathcal{C},\mathcal{D})\mapsto\mathcal{C}\bowtie\mathcal{D}\mapsto
H_{k}(\mathcal{C}\bowtie\mathcal{D})$.

For an abelian group $A$, the _categorical cohomology of
$(\mathcal{C},\mathcal{D})$ with coefficients in $A$_, denoted
$H_{\bowtie}^{\bullet}(\mathcal{C},\mathcal{D};A)$, is the categorical
cohomology of $\mathcal{C}\bowtie\mathcal{D}$ with coefficients in $A$.

We work with simplicial groups rather than chain complexes (see [Wei94, Ch.8])
to simplify calculations. The Dold–Kan Theorem [Wei94, Theorem 8.4.1] gives an
equivalence of categories between simplicial abelian groups and chain
complexes of abelian groups.

For each $k\geq 1$ and $0\leq i\leq k+1$ we define the _face map_
$\partial_{k}^{i}\colon C_{k+1}(\mathcal{C})\to C_{k}(\mathcal{C})$ by

$\partial_{k}^{i}[c_{0},\ldots,c_{i},\ldots,c_{k}]=\begin{cases*}[c_{1},\ldots,c_{k}]&if
$i=0$\\\ [c_{0},\ldots,c_{i-1}c_{i},\ldots,c_{k}]&if $1\leq i\leq k$\\\
[c_{0},\ldots,c_{k-1}]&if $i=k+1$.\end{cases*}$ (4.1)

We also define $\partial_{0}^{0}[c]=[s(c)]$ and $\partial_{0}^{1}[c]=[r(c)]$.
In particular, $d_{k}=\sum_{i=0}^{k+1}(-1)^{k}\partial_{k}^{i}$.

To work with degeneracy maps, we use the following—slightly non-
standard—notation.

######  Notation 4.3.

If $(c_{1},\ldots,c_{k})\in\mathcal{C}^{k}$ is a composable $k$-tuple, and
$0\leq i\leq k$, then we define

$\displaystyle(c_{1},\ldots,c_{i-1},\\_,c_{i+1},\ldots,c_{k})$
$\displaystyle\coloneqq(c_{1},\ldots,c_{i-1},s(c_{i-1}),c_{i+1},\ldots,c_{k})$
$\displaystyle=(c_{1},\ldots,c_{i-1},r(c_{i+1}),c_{i+1},\ldots,c_{k})\in\mathcal{C}^{k-1}.$

The identity morphism represented by any given instance of $\\_$ is determined
by either of the neighbouring entries.

For each $k\geq 1$ and $0\leq i\leq k$ we define the _degeneracy map_
$\sigma_{k}^{i}\colon C_{k}(\mathcal{C})\to C_{k+1}(\mathcal{C})$ by

$\sigma_{k}^{i}[c_{0},\ldots,c_{k-1}]=\begin{cases*}[\\_,c_{0},\ldots,c_{k-1}]&if
$i=0$,\\\ [c_{0},\ldots,c_{i-1},\\_,c_{i},\ldots,c_{k-1}]&if $0<i<k$,\\\
[c_{0},\ldots,c_{k-1},\\_]&if $i=k$,\end{cases*}$

with $\sigma_{0}^{0}[x]=[x]$ for $x\in\mathcal{C}^{0}$. These and the
$\partial_{j}^{i}$ satisfy the _simplicial identities_ :

$\displaystyle\partial_{k-1}^{i}\partial_{k}^{j}$
$\displaystyle=\partial^{j-1}_{k-1}\partial_{k}^{i}\quad\text{if }i<j$
$\displaystyle\sigma^{i}_{k+1}\sigma^{j}_{k}$
$\displaystyle=\sigma^{j+1}_{k+1}\sigma^{i}_{k}\quad\text{if }i\leq j,\text{
and}$ $\displaystyle\partial^{i}_{k}\sigma^{j}_{k}$
$\displaystyle=\begin{cases}\sigma^{j-1}_{k}\partial_{k}^{i}&\text{if }i<j\\\
\operatorname{id}_{C_{k}(\mathcal{C})}&\text{if }i=j\text{ or }i=j+1\\\
\sigma^{j}_{k}\partial^{i-1}_{k}&\text{if }i>j+1,\end{cases}$

so $(C_{\bullet}(\mathcal{C}),\partial,\sigma)$ is a simplicial abelian group.

If $(\mathcal{C},\mathcal{D})$ is a matched pair, then Proposition 3.20 gives
an action of $\mathcal{C}$ on each $\mathcal{D}^{k+1}$. For
$(c,d)\in\mathcal{C}*\mathcal{D}^{k+1}$, we write $c\triangleright[d]$ for the
generator $[c\triangleright d]$ of $C_{k+1}(\mathcal{D})$. Similarly if
$(c,d)\in\mathcal{C}^{k+1}*\mathcal{D}$ we write $[c]\triangleleft d$ for the
generator $[c\triangleleft d]$.

######  Lemma 4.4.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair and take $k\in\mathbb{N}$.
For $0<i\leq k+1$ and for $(c,d)\in\mathcal{C}*\mathcal{D}^{k+1}$, we have
$\partial^{i}_{k}(c\triangleright[d])=c\triangleright\partial^{i}_{k}[d]$ in
$C_{k}(\mathcal{D})$. Similarly, for $0\leq j<k+1\in\mathbb{N}$ and
$(c,d)\in\mathcal{C}^{k+1}*\mathcal{D}$, we have
$\partial^{j}_{k}([c]\triangleleft d)=\partial^{j}_{k}[c]\triangleleft d$ in
$C_{k}(\mathcal{C})$.

###### Proof.

We prove the first statement; the second follows symmetrically. Since $i>0$,
we have

$\displaystyle c\triangleright\partial_{k}^{i}[d]$
$\displaystyle=c\triangleright[d_{0},\dots,d_{i}d_{i+1},\dots,d_{k}]$
$\displaystyle=\big{[}c\triangleright d_{0},(c\triangleleft
d_{0})\triangleright d_{1},\dots,(c\triangleleft d_{0}\dots
d_{i-1})\triangleright d_{i}d_{i+1},\dots,(c\triangleleft(d_{0}\dots
d_{k-1}))\triangleright d_{k}\big{]}$ $\displaystyle=\big{[}c\triangleright
d_{0},(c\triangleleft d_{0})\triangleright d_{1},\dots,\big{(}(c\triangleleft
d_{0}\dots d_{i-1})\triangleright d_{i}\big{)}\big{(}(c\triangleleft
d_{0}\dots d_{i})\triangleright d_{i+1}\big{)},$ $\displaystyle\hskip
120.00018pt\dots,(c\triangleleft(d_{0}\dots d_{k-1}))\triangleright
d_{k}\big{]}$ $\displaystyle=\partial_{k}^{i}\big{[}c\triangleright
d_{0},(c\triangleleft d_{0})\triangleright d_{1},\dots,\big{(}(c\triangleleft
d_{0}\dots d_{i-1})\triangleright d_{i}),\big{(}(c\triangleleft d_{0}\dots
d_{i})\triangleright d_{i+1}\big{)},$ $\displaystyle\hskip
120.00018pt\dots,(c\triangleleft(d_{0}\dots d_{k-1}))\triangleright
d_{k}\big{]}$ $\displaystyle=\partial_{k}^{i}(c\triangleright[d]).\qed$

######  Remark 4.5.

Lemma 4.4 is _only_ valid for $i>0$ and $j<k+1$. The left action of
$\mathcal{C}$ on $\mathcal{D}^{k+1}$ does not commute with $\partial^{0}_{k}$,
and the right action of $\mathcal{D}$ on $\mathcal{C}^{k+1}$ does not commute
with $\partial^{k+1}_{k}$.

###  4.2. The matched complex

We associate a double complex to each matched pair
$(\mathcal{C},\mathcal{D})$. For $p,\,q\geq 0$, regard elements of
$\mathcal{C}^{p}*\mathcal{D}^{q}$ as composable tuples in
$(\mathcal{C}\bowtie\mathcal{D})^{p+q}$, whose first $p$ terms belong to
$\mathcal{C}\subseteq\mathcal{C}\bowtie\mathcal{D}$ and whose remaining $q$
terms belong to $\mathcal{D}\subseteq\mathcal{C}\bowtie\mathcal{D}$.

Let
$C_{p,q}(\mathcal{C},\mathcal{D})\coloneqq\mathbb{Z}(\mathcal{C}^{p}*\mathcal{D}^{q})$,
the free abelian group generated by $\mathcal{C}^{p}*\mathcal{D}^{q}$. Let
$\triangleright$ be the action of $\mathcal{C}$ on $\mathcal{D}^{q}$ of Lemma
3.19. Define _horizontal face maps_ $\partial_{p,q}^{h,i}\colon
C_{p+1,q}(\mathcal{C},\mathcal{D})\to C_{p,q}(\mathcal{C},\mathcal{D})$ as
follows. For $q\geq 1$,

$\partial_{p,q}^{h,i}[c_{0},\ldots,c_{p},d_{0},\ldots,d_{q-1}]=\begin{cases}[c_{1},\ldots,c_{p},d_{0},\ldots,d_{q-1}]&\text{if
}i=0\\\ [c_{0},\ldots,c_{i-1}c_{i},\ldots,c_{p},d_{0},\ldots,d_{q-1}]&\text{if
}1\leq i\leq p\\\
[c_{0},\ldots,c_{p-1},c_{p}\triangleright(d_{0},\ldots,d_{q-1})]&\text{if
}i=p+1,\end{cases}$

while $\partial_{p,0}^{h,i}\coloneqq\partial_{p}^{i}\colon
C_{p+1}(\mathcal{C})\to C_{p}(\mathcal{C})$ as in (4.1). For $0\leq i\leq p$
we define the _horizontal degeneracy maps_ $\sigma_{p,q}^{h,i}\colon
C_{p,q}(\mathcal{C},\mathcal{D})\to C_{p+1,q}(\mathcal{C},\mathcal{D})$ by

$\sigma^{h,i}_{p,q}[c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{q-1}]=[c_{0},\ldots,c_{i},\\_,c_{i+1},\ldots,c_{p-1},d_{0},\ldots,d_{q-1}].$

For each $q\geq 0$, the tuple
$(C_{\bullet,q}(\mathcal{C},\mathcal{D}),\partial^{h}_{\bullet,q},\sigma^{h}_{\bullet,q})$
is a simplicial abelian group.

Let $\triangleleft$ be the action of $\mathcal{D}$ on $\mathcal{C}^{*}$ of
Lemma 3.19. Define _vertical face maps_ $\partial_{p,q+1}^{v,j}\colon
C_{p,q+1}(\mathcal{C},\mathcal{D})\to C_{p,q}(\mathcal{C},\mathcal{D})$ as
follows. For $p>0$,

$\partial_{p,q}^{v,j}[c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{q}]=(-1)^{p}\begin{cases}[(c_{0},\ldots,c_{p-1})\triangleleft
d_{0},d_{1},\ldots,d_{q}]&\text{if }j=0\\\
[c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{j-1}d_{j},\ldots,d_{q}]&\text{if }1\leq
j\leq q\\\ [c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{q-1}]&\text{if
}j=q+1,\end{cases}$

while $\partial_{0,q}^{v,i}\coloneqq\partial_{q}^{i}\colon
C_{q+1}(\mathcal{D})\to C_{q}(\mathcal{D})$ as in (4.1). For $0\leq j\leq q$
we define _vertical degeneracy maps_ $\sigma_{p,q}^{v,j}\colon C_{p,q}\to
C_{p,q+1}$ by

$\sigma^{v,j}_{p,q}[c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{q-1}]=(-1)^{p}[c_{0},\ldots,c_{p-1},d_{0},\ldots,d_{j},\\_,d_{j+1},d_{q-1}].$

Then
$(C_{p,\bullet}(\mathcal{C},\mathcal{D}),\partial^{v}_{p,\bullet},\sigma^{v}_{p,\bullet})$
is also a simplicial abelian group.

For the next result, recall from [Wei94, §8.5] that a bisimplicial abelian
group is a quintuple
$(C_{\bullet,\bullet},\partial^{h},\partial^{v},\sigma^{h},\sigma^{v})$
consisting of abelian groups $C_{p,q}$ and homomorphisms
$\partial^{h,i}_{p,q}\colon C_{p+1,q}\to C_{p,q}$, $\sigma^{h,i}_{p,q}\colon
C_{p,q}\to C_{p+1,q}$, $\partial^{v,j}_{p,q}\colon C_{p,q+1}\to C_{p,q}$, and
$\sigma^{v,j}_{p,q}\colon C_{p,q}\to C_{p,q+1}$ such that each
$(C_{p,\bullet},\partial^{v}_{p,\bullet},\sigma^{v}_{p,\bullet})$ and each
$(C_{\bullet,q},\partial^{h}_{\bullet,q},\sigma^{h}_{\bullet,q})$ is a
simplicial group, and

$\partial_{p,q}^{v,i}\partial_{p,q+1}^{h,j}=-\partial_{p,q}^{h,j}\partial_{p+1,q}^{v,i}\quad\text{and}\quad\sigma_{p+1,q}^{v,i}\sigma_{p,q}^{h,j}=-\sigma_{p,q+1}^{h,j}\sigma_{p,q}^{v,i}.$

######  Proposition 4.6.

The quintuple
$(C_{\bullet,\bullet},\partial^{h},\partial^{v},\sigma^{h},\sigma^{v})$ is a
bisimplicial group. Define

$d_{p,q}^{h}=\sum_{i=0}^{p+1}(-1)^{i}\partial_{p,q}^{h,i}\colon C_{p+1,q}\to
C_{p,q}\quad\text{and}\quad
d_{p,q}^{v}=\sum_{i=0}^{q+1}(-1)^{i}\partial_{p,q}^{v,i}\colon C_{p,q+1}\to
C_{p,q}.$

Then

${{C_{0,2}}}$${{C_{1,2}}}$${{C_{2,2}}}$${{C_{0,1}}}$${{C_{1,1}}}$${{C_{2,1}}}$${{C_{0,0}}}$${{C_{1,0}}}$${{C_{2,0}}}$$\scriptstyle{d^{v}_{0,1}}$$\scriptstyle{d^{v}_{1,1}}$$\scriptstyle{d^{h}_{0,2}}$$\scriptstyle{d^{v}_{2,1}}$$\scriptstyle{d^{h}_{1,2}}$$\scriptstyle{d^{v}_{0,0}}$$\scriptstyle{d^{v}_{1,0}}$$\scriptstyle{d^{h}_{0,1}}$$\scriptstyle{d^{v}_{2,0}}$$\scriptstyle{d^{h}_{1,1}}$$\scriptstyle{d^{h}_{0,0}}$$\scriptstyle{d^{h}_{1,0}}$
(4.2)

is a first-quadrant double chain complex satisfying $d^{h}d^{v}=-d^{v}d^{h}$.

###### Proof.

Fix $p,q\geq 0$ and fix $i\leq p+1$ and $j\leq q+1$. We must show that
$\partial_{p,q}^{v,i}\partial_{p,q+1}^{h,j}=-\partial_{p,q}^{h,j}\partial_{p+1,q}^{v,i}$.
Fix $[c_{0},\dots,c_{p};d_{0},\dots,d_{q}]\in C_{p+1,q+1}$. If $i\not=p+1$ or
$j\not=0$, then $\partial_{p,q}^{v,i}$ and $\partial_{p,q+1}^{h,j}$
concatenate or delete nonadjacent coordinates, as do $\partial_{p,q}^{h,j}$
and $\partial_{p+1,q}^{v,i}$, and so the factors of $(-1)^{p}$ and
$(-1)^{p+1}$ in $\partial_{p,q}^{v,i}$ and $\partial_{p+1,q}^{v,i}$ give the
desired anticommutation relation. If $i=p+1$ and $j=0$, then

$\displaystyle\partial_{p,q}^{v,0}\partial_{p,q+1}^{h,p+1}([c_{0},\dots,c_{p};d_{0},\dots,d_{q}])$
$\displaystyle=\partial_{p,q}^{v,0}([(c_{0},\dots,c_{p})\triangleleft
d_{0};d_{1},\dots,d_{q}])$
$\displaystyle=\partial_{p,q}^{v,0}([(c_{0},\dots,c_{p-1})\triangleleft(c_{p}\triangleright
d_{0}),c_{p}\triangleleft d_{0};d_{1},\dots,d_{q}])$
$\displaystyle=(-1)^{p}[(c_{0},\dots,c_{p-1})\triangleleft(c_{p}\triangleright
d_{0});(c_{p}\triangleleft d_{0})\triangleright(d_{1},\dots,d_{q})],$

and

$\displaystyle\partial_{p,q}^{h,p+1}\partial_{p+1,q}^{v,0}([c_{0},\dots,c_{p};d_{0},\dots,d_{q}])$
$\displaystyle=(-1)^{p+1}\partial_{p,q}^{v,0}([c_{0},\dots,c_{p-1};c_{p}\triangleright(d_{0},\dots,d_{q})])$
$\displaystyle=(-1)^{p+1}\partial_{p,q}^{v,0}([c_{0},\dots,c_{p-1};c_{p}\triangleright
d_{0},(c_{p}\triangleleft d_{0})\triangleright(d_{1},\dots,d_{q})])$
$\displaystyle=(-1)^{p+1}[(c_{0},\dots,c_{p-1})\triangleleft(c_{p}\triangleright
d_{0});(c_{p}\triangleleft d_{0})\triangleright(d_{1},\dots,d_{q})],$

which gives the desired relation. It follows that $d^{v}d^{h}=-d^{h}d^{v}$.

The anticommutation relation
$\sigma_{p+1,q}^{v,i}\sigma_{p,q}^{h,j}=-\sigma_{p,q+1}^{h,j}\sigma_{p,q}^{v,i}$
also follows from direct computation. Routine calculation shows that (4.2) is
a first-quadrant double chain complex. ∎

######  Definition 4.7.

We call the double chain complex
$(C_{\bullet,\bullet}(\mathcal{C},\mathcal{D}),d^{h},d^{v})$ the _matched
complex_ of the matched pair $(\mathcal{C},\mathcal{D})$.

######  Lemma 4.8.

The assignment $C_{\bullet,\bullet}$ of a matched complex to each matched pair
is a functor from the category ${\mathsf{MP}}$ of matched pairs to the
category of double complexes of Abelian groups.

###### Proof.

Matched-pair morphisms intertwine the face and degeneracy maps
$\partial_{p,q}^{\bullet,i}$ and $\sigma_{p,q}^{\bullet,i}$. ∎

######  Notation 4.9.

For the remainder of the paper we frequently omit the subscripts on face maps,
degeneracy maps and boundary maps. For example, $\partial^{h,i}$ denotes any
of the maps $\partial^{h,i}_{p,q}$; the values of $p$ and $q$ should be clear
from context.

There are two chain complexes associated to each double complex: the _diagonal
complex_ and the _total complex_ [Wei94, §8.5].

###  4.3. The diagonal complex and diagonal homology

Let $(C_{\bullet,\bullet}(\mathcal{C},\mathcal{D}),d^{h},d^{v})$ be the
matched complex of a matched pair $(\mathcal{C},\mathcal{D})$. For each $k\geq
0$, let

$C_{k}^{\Delta}(\mathcal{C},\mathcal{D})\coloneqq
C_{k,k}(\mathcal{C},\mathcal{D})$

and define $\partial^{\Delta,i}_{k}\colon
C_{k+1}^{\Delta}(\mathcal{C},\mathcal{D})\to
C_{k}^{\Delta}(\mathcal{C},\mathcal{D})$ and $\sigma^{\Delta,i}_{k}\colon
C_{k}^{\Delta}(\mathcal{C},\mathcal{D})\to
C_{k+1}^{\Delta}(\mathcal{C},\mathcal{D})$ by

$\partial^{\Delta,i}_{k}\coloneqq\partial^{h,i}_{k,k}\partial^{v,i}_{k+1,k}\quad\text{and}\quad\sigma^{\Delta,i}_{k}\coloneqq\sigma^{v,i}_{k+1,k}\sigma^{h,i}_{k,k}.$

Then
$(C_{\bullet}^{\Delta}(\mathcal{C},\mathcal{D}),\partial^{\Delta},\sigma^{\Delta})$
is a simplicial group [Wei94, §8.5]. Let
$d^{\Delta}_{k}\coloneqq\sum_{i=0}^{k+1}(-1)^{i}\partial^{\Delta,i}_{k}$.

######  Definition 4.10.

The _diagonal complex_ of $(\mathcal{C},\mathcal{D})$ is the chain complex
$(C_{\bullet}^{\Delta}(\mathcal{C},\mathcal{D}),d^{\Delta}_{\bullet})$. We
denote the homology of this chain complex by
$H^{\Delta}_{\bullet}(\mathcal{C},\mathcal{D})$.

###  4.4. The total complex and total homology

Let $(C_{\bullet,\bullet}(\mathcal{C},\mathcal{D}),d^{h},d^{v})$ be the
matched complex of a matched pair $(\mathcal{C},\mathcal{D})$. For each $k\geq
0$, let

$C_{k}^{\operatorname{Tot}}(\mathcal{C},\mathcal{D})\coloneqq\bigoplus_{p+q=k}C_{p,q}(\mathcal{C},\mathcal{D}).$

Define $d^{\operatorname{Tot}}_{k}\colon
C_{k+1}^{\operatorname{Tot}}(\mathcal{C},\mathcal{D})\to
C_{k}^{\operatorname{Tot}}(\mathcal{C},\mathcal{D})$ by
$d^{\operatorname{Tot}}_{k}\coloneqq d_{k}^{v}+d_{k}^{h}$.

######  Definition 4.11.

The _total complex_ of $(\mathcal{C},\mathcal{D})$ is the chain complex
$(C_{\bullet}^{\operatorname{Tot}}(\mathcal{C},\mathcal{D}),d^{\operatorname{Tot}}_{\bullet})$.
We denote the homology of this complex by
$H^{\operatorname{Tot}}_{\bullet}(\mathcal{C},\mathcal{D})$.

##  5\. Equivalence of homology theories

In this section we prove that the homology theories for matched pairs
introduced in Subsections 4.1, 4.3, and 4.4 coincide. Specifically, we
describe natural chain maps that induce isomorphisms between them and between
the dual cohomology theories. We also give formulae for their inverses. The
main result is Theorem 5.3. We start by defining the maps involved.

###  5.1. The natural chain maps

We begin by describing explicit formulae for natural chain maps $\nabla\colon
C_{\bullet}^{\operatorname{Tot}}\to C_{\bullet}^{\Delta}$, $\Pi\colon
C_{\bullet}^{\Delta}\to C_{\bullet}^{\bowtie}$, and $\Psi\colon
C_{\bullet}^{\bowtie}\to C_{\bullet}^{\operatorname{Tot}}$.

####  5.1.1. The map $\nabla$

The map $\nabla\colon C_{\bullet}^{\operatorname{Tot}}\to
C_{\bullet}^{\Delta}$ is the _Eilenberg–Zilber map_ [Wei94, § 8.5.4]. For
$p,q\in\mathbb{N}$ a _$(p,q)$ -shuffle_ is a permutation $\beta$ of
$\\{1,\ldots,p+q\\}$ such that

$\beta(1)<\beta(2)<\cdots<\beta(p)\quad\text{ and
}\quad\beta(p+1)<\beta(p+2)<\cdots<\beta(p+q).$

We write $\operatorname{Sh}(p,q)$ for the collection of all $(p,q)$-shuffles,
and $\operatorname{sgn}(\beta)$ for the sign of a permutation $\beta$. The
$(p,q)$-component $\nabla_{p,q}\colon C_{p,q}\to C_{p+q}^{\Delta}$ of the
Eilenberg–Zilber map is

$\nabla_{p,q}=\sum_{\beta\in\operatorname{Sh}(p,q)}\operatorname{sgn}(\beta)\,\sigma^{h,\beta(p+q)}_{p+q-1,p+q}\circ\cdots\circ\sigma^{h,\beta(p+1)}_{p,p+q}\circ\sigma^{v,\beta(p)}_{p,p+q-1}\circ\cdots\circ\sigma^{v,\beta(1)}_{p,q}.$
(5.1)

####  5.1.2. The map $\Pi$

We describe $\Pi\colon C_{\bullet}^{\Delta}\to C_{\bullet}^{\bowtie}$. For
$k\geq 1$ define
$\bowtie^{k}\colon(\mathcal{C}*\mathcal{D})^{k}\to(\mathcal{D}*\mathcal{C})^{k}$
by

$\bowtie^{k}(c_{1},d_{1},\ldots,c_{k},d_{k})\coloneqq(c_{1}\bowtie
d_{1},\ldots,c_{k}\bowtie d_{k}).$

Set $\Pi_{0}=\operatorname{id}_{\mathcal{C}^{0}}$ and inductively define
$\Pi_{k}\colon\mathcal{C}^{k}*\mathcal{D}^{k}\to(\mathcal{C}\bowtie\mathcal{D})^{k}=(\mathcal{D}*\mathcal{C})^{k}$
for $k\geq 1$ by

$\Pi_{k}\coloneqq\operatorname{{\bowtie}}^{k}\circ(1_{\mathcal{C}}*\Pi_{k-1}*1_{\mathcal{D}}).$
(5.2)

These extend to homomorphisms $\Pi_{k}\colon
C^{\Delta}_{k}(\mathcal{C},\mathcal{D})\to
C^{\bowtie}_{k}(\mathcal{C},\mathcal{D})$. For example,

$\displaystyle\Pi_{1}[c_{1},d_{1}]$ $\displaystyle=[c_{1}\triangleright
d_{1},c_{1}\triangleleft d_{1}]$
$\displaystyle\Pi_{2}[c_{1},c_{2},d_{1},d_{2}]$
$\displaystyle=[c_{1}c_{2}\triangleright
d_{1},c_{1}\triangleleft(c_{2}\triangleright d_{1}),(c_{2}\triangleleft
d_{1})\triangleright d_{2},c_{2}\triangleleft d_{1}d_{2}]$
$\displaystyle\Pi_{3}[c_{1},c_{2},c_{3},d_{1},d_{2},d_{3}]$
$\displaystyle=[c_{1}c_{2}c_{3}\triangleright
d_{1},c_{1}\triangleleft(c_{2}c_{3}\triangleright
d_{1}),(c_{2}c_{3}\triangleleft d_{1})\triangleright d_{2},$
$\displaystyle\qquad\qquad c_{2}\triangleleft(c_{3}\triangleright
d_{1}d_{2}),(c_{3}\triangleleft d_{1}d_{2})\triangleright
d_{3},c_{3}\triangleleft d_{1}d_{2}d_{3}].$

An induction on $k$, using that matched-pair morphisms respect left and right
actions, shows that the $\Pi_{k}$ extend to natural transformations
$\Pi_{k}\colon C_{k}^{\Delta}\to C_{k}^{\bowtie}$.

######  Remark 5.1.

The map $\Pi_{k}$ can be described diagrammatically. We represent elements of
$\mathcal{C}$ by blue vertices, and elements of $\mathcal{D}$ by red vertices;
vertical lines are identity morphisms; and crossings are applications of
$\bowtie$:

$\displaystyle[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{3}}]$
$\displaystyle[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{3}\triangleright
d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}\triangleleft
d_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{3}}]$
$\displaystyle[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{2}c_{3}\triangleright
d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}\triangleleft(c_{3}\triangleright
d_{1})},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(c_{3}\triangleleft
d_{1})\triangleright
d_{2}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}\triangleleft
d_{1}d_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{3}}]$
$\displaystyle\Pi_{3}[c_{1},c_{2},c_{3},d_{1},d_{2},d_{3}].$

So starting with an element of $\mathcal{C}^{k}*\mathcal{D}^{k}$, we apply
$\bowtie$ to pairs of adjacent terms wherever possible until we obtain an
element of $(\mathcal{D}*\mathcal{C})^{k}$.

####  5.1.3. The map $\Psi$

We now define $\Psi\colon C_{\bullet}^{\bowtie}\to
C_{\bullet}^{\operatorname{Tot}}$. For $q\geq 0$ define
$\tau^{q}\colon(\mathcal{D}\bowtie\mathcal{C})^{q}\to\mathcal{D}^{q}*\mathcal{C}^{q}$
as follows: regard
$(d_{1}c_{1},\ldots,d_{q}c_{q})\in(\mathcal{D}\bowtie\mathcal{C})^{q}$ as a
composable $q$-tuple in $\mathcal{C}^{*}\bowtie\mathcal{D}^{*}$. By
Proposition 3.20 there exist unique $d^{\prime}\in\mathcal{D}^{q}$ and
$c^{\prime}\in\mathcal{C}^{q}$ such that
$(d_{1}c_{1})\cdots(d_{q}c_{q})=d^{\prime}c^{\prime}\in\mathcal{C}^{p}\bowtie\mathcal{D}^{q}$.
For instance,

$(d_{1}c_{1})(d_{2}c_{2})(d_{3}c_{3})=(d_{1},c_{1}\triangleright
d_{2},((c_{1}\triangleleft d_{2})c_{2})\triangleright
d_{3},c_{1}\triangleleft(d_{2}(c_{2}\triangleright d_{3})),c_{2}\triangleleft
d_{3},c_{3})\in\mathcal{D}^{3}*\mathcal{C}^{3}.$

We define
$\tau^{q}(d_{1}c_{1},\ldots,d_{q}c_{q})\coloneqq(d^{\prime},c^{\prime})$.

######  Remark 5.2.

We can describe $\tau^{q}$ via a diagram using the same conventions as in
Remark 5.1. For example $\tau^{3}$ is represented by the diagram

$\displaystyle({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{2}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{3}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}})$
$\displaystyle({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{1}\triangleright
d_{2}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}\triangleleft
d_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{2}\triangleright
d_{3}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}\triangleleft
d_{3}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}})$
$\displaystyle({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c_{1}\triangleright
d_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}((c_{1}\triangleleft
d_{2})c_{2})\triangleright
d_{3}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}\triangleleft(d_{2}(c_{2}\triangleright
d_{3}))},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{2}\triangleleft
d_{3}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{3}})$

The maps $\tau^{q}$ for $q\geq 3$ can be visualised similarly.

For $p,q\geq 0$ let
$\rho_{p,q}\colon\mathcal{D}^{p}*\mathcal{C}^{p}*\mathcal{D}^{q}*\mathcal{C}^{q}\to\mathcal{C}^{p}*\mathcal{D}^{q}$
denote the projection onto the middle two factors. Define
$\Psi_{p,q}\colon(\mathcal{C}\bowtie\mathcal{D})^{p+q}\to\mathcal{C}^{p}*\mathcal{D}^{q}$
by

$\Psi_{p,q}=\rho_{p,q}\circ(\tau_{p}*\tau_{q})$

and extend it to a homomorphism $\Psi_{p,q}\colon
C_{p+q}^{\bowtie}(\mathcal{C},\mathcal{D})\to
C_{p,q}(\mathcal{C},\mathcal{D})$. For example, we can represent
$\Psi_{3,2}[d_{1},c_{1},\ldots,d_{5},c_{5}]$ diagrammatically by

$[{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},\dots,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{5}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{5}}]$$(\tau^{3}*\tau^{2})([{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},\dots,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{5}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{5}}])$$\Psi_{3,2}([{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{1}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{1}},\dots,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}d_{5}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{5}}])$

(crossed vertices like  indicate omission of the corresponding entries).

We now define $\Psi_{k}\colon C_{k}^{\bowtie}(\mathcal{C},\mathcal{D})\to
C_{k}^{\operatorname{Tot}}(\mathcal{C},\mathcal{D})$ by

$\Psi_{k}=\sum_{p+q=k}\Psi_{p,q}.$ (5.3)

Explicit formulae for low-degree terms are given by

$\displaystyle\Psi_{1}[d_{1}c_{1}]$
$\displaystyle=\Psi_{1,0}[d_{1}c_{1}]+\Psi_{0,1}[d_{1}c_{1}]=[c_{1}]+[d_{1}]$
$\displaystyle\Psi_{2}[d_{1}c_{1},d_{2}c_{2}]$
$\displaystyle=[c_{1}\triangleleft
d_{2},c_{2}]+[c_{1};d_{2}]+[d_{1},c_{1}\triangleright d_{2}]$
$\displaystyle\Psi_{3}[d_{1}c_{1},d_{2}c_{2},d_{3}c_{3}]$
$\displaystyle=[d_{1},c_{1}\triangleright d_{2},((c_{1}\triangleleft
d_{2})c_{2})\triangleright d_{3}]+[c_{1};d_{2},c_{2}\triangleright d_{3}]$
$\displaystyle\qquad+[c_{1}\triangleleft
d_{2},c_{2};d_{3}]+[c_{1}\triangleleft(d_{2}(c_{2}\triangleright
d_{3})),c_{2}\triangleleft d_{3},c_{3}].$

It is routine to verify that the $\Psi_{k}$ extend to natural transformations
$\Psi_{k}\colon C_{k}^{\bowtie}\to C_{k}^{\operatorname{Tot}}$.

###  5.2. The statement of the main theorem

We state our main homology theorem and outline the proof. We write
${\mathsf{Ch}}_{\bullet}$ for the category of abelian chain complexes and
chain maps.

######  Theorem 5.3.

The formulae (5.1), (5.2), and (5.3) determine natural chain equivalences such
that the diagram

${{C_{\bullet}^{\Delta}}}$${{C_{\bullet}^{\operatorname{Tot}}}}$${{C_{\bullet}^{\bowtie}}}$$\scriptstyle{\nabla}$$\scriptstyle{\Pi}$$\scriptstyle{\Psi}$
(5.4)

commutes up to natural chain homotopy. They induce natural isomorphisms

$H^{\bowtie}_{\bullet}\cong H^{\Delta}_{\bullet}\cong
H^{\operatorname{Tot}}_{\bullet}$

of functors from ${\mathsf{MP}}$ to ${\mathsf{Ch}}_{\bullet}$. In particular,
for any matched pair $(\mathcal{C},\mathcal{D})$,

$H^{\bowtie}_{k}(\mathcal{C},\mathcal{D})\cong
H^{\Delta}_{k}(\mathcal{C},\mathcal{D})\cong
H^{\operatorname{Tot}}_{k}(\mathcal{C},\mathcal{D}).$

Before commencing the proof of this theorem, we record a corollary. Recall
that for us, given a chain complex $(C_{\bullet},d_{\bullet})$ and an abelian
group $A$, the cohomology with coefficients in $A$ is the cohomology of the
dual cochain complex $(\operatorname{Hom}(C_{\bullet},A),d_{\bullet}^{*})$.

######  Corollary 5.4.

For any fixed abelian group $A$, the duals of the natural chain maps $\nabla$,
$\Pi$, and $\Psi$ induce natural isomorphisms

$H^{\bullet}_{\bowtie}(\,\cdot\,;A)\cong
H^{\bullet}_{\Delta}(\,\cdot\,;A)\cong
H^{\bullet}_{\operatorname{Tot}}(\,\cdot\,;A)$

of cohomology functors with coefficients in $A$.

###### Proof.

Dualising all the maps in a chain homotopy diagram yields a cochain homotopy.
∎

That $\nabla$ induces a natural isomorphism is the content of a general form
of the Eilenberg–Zilber Theorem. Following [Wei94, §8.5.4] the
_Alexander–Whitney map_ $\Delta\colon C_{\bullet}^{\Delta}\to
C_{\bullet}^{\operatorname{Tot}}$ is defined as follows: for $p,q$ such that
$p+q=n$, define $\Delta_{p,q}\colon C_{n}^{\Delta}\to C_{p,q}$ by

$\Delta_{p,q}\coloneqq\underbrace{\partial_{p+1}^{h}\cdots\partial_{n}^{h}}_{q\text{
terms}}\circ\underbrace{\partial_{0}^{v}\cdots\partial_{0}^{v}}_{p\text{
terms}}.$

Then the map $\Delta$ is defined by

$\Delta\coloneqq\bigoplus_{p+q=n}\Delta_{p,q}.$ (5.5)

######  Theorem 5.5 ([Wei94, Theorem 8.5.1]).

The map $\nabla\colon C_{\bullet}^{\operatorname{Tot}}\to
C_{\bullet}^{\Delta}$ of (5.1) induces a natural isomorphism
$H^{\Delta}_{\bullet}\cong H^{\operatorname{Tot}}_{\bullet}$, with inverse
induced by the map $\Delta\colon C_{\bullet}^{\Delta}\to
C_{\bullet}^{\operatorname{Tot}}$ of (5.5).

Given Theorem 5.5, to prove Theorem 5.3 it suffices to establish the natural
isomorphism $H^{\bowtie}_{\bullet}\cong H^{\Delta}_{\bullet}$. To do this we
fill out a diagram

${{C_{\bullet}^{\Delta}}}$${{C_{\bullet}^{\operatorname{Tot}}}}$${{C_{\bullet}^{\bowtie}}}$$\scriptstyle{\Delta}$$\scriptstyle{\nabla}$$\scriptstyle{\Pi}$

$\scriptstyle\Pi$

$\scriptstyle\Psi$

$\scriptstyle{\Psi}$ (5.6)

of natural chain equivalences that commutes up to natural chain homotopy. We
use the _method of acyclic models_ (see [Rot88] for instance). The details
occupy Subsections 5.3 and 5.4.

We show in Section 5.3 that the model matched pairs
$(\mathcal{E}_{2k},\mathcal{F}_{2k})$ satisfy
$H_{p}^{\bowtie}(\mathcal{E}_{2k},\mathcal{F}_{2k})=0=H_{p}^{\Delta}(\mathcal{E}_{2k},\mathcal{F}_{2k})$
for all $p\geq 1$. So we can use these as the models in the method of acyclic
models. We deduce that there exist natural chain equivalences between
$C_{\bullet}^{\bowtie}$ and $C_{\bullet}^{\Delta}$ that induce natural
isomorphisms on homology, and show how to recognise when given chain maps do
the job.

In Subsection 5.5, we show that (5.2) and (5.3) are such chain maps. We also
give explicit formulae for the remaining maps
$\rotatebox[origin={c}]{180.0}{$\Pi$}\coloneqq\nabla\circ\Psi$ and
$\rotatebox[origin={c}]{180.0}{$\Psi$}\coloneqq\Pi\circ\nabla$.

###  5.3. Homological acyclicity of model matched pairs

The proof of Theorem 5.3 hinges on properties of the homology of the model
matched pairs $(\mathcal{E}_{n},\mathcal{F}_{n})$. Recall that the object set
of $\Gamma_{n}\cong\mathcal{E}_{n}*\mathcal{F}_{n}$ is
$X_{n}=\\{\mathbf{a}=(a_{L},a_{R})\in\mathbb{N}\times\mathbb{N}\mid 0\leq
a_{L}+a_{R}\leq n\\}$. Each morphism of $\Gamma_{n}$ is a pair
$(\mathbf{a},\mathbf{b})\in X_{n}\times X_{n}$ such that $a_{L}\leq b_{L}$ and
$a_{R}\geq b_{R}$.

The map $r\times s\colon\Gamma_{n}\to X_{n}\times X_{n}$ is injective. Hence,

$\Gamma_{n}^{k}\ni(\gamma_{1},\ldots,\gamma_{k})\mapsto(r(\gamma_{1}),s(\gamma_{1}),s(\gamma_{2}),\ldots,s(\gamma_{k}))\in
X_{n}^{(k)}.$ (5.7)

is a bijective correspondence between $\Gamma_{n}^{k}$ and

$X_{n}^{(k)}\coloneqq\\{(\mathbf{a}_{0},\mathbf{a}_{1},\ldots,\mathbf{a}_{k})\mid\mathbf{a}_{i}\in
X_{n},\,a_{i,L}\leq a_{i+1,L},\text{ and }a_{i,R}\geq a_{i+1,R}\text{ for all
}i\\}.$

Since $C^{\bowtie}_{k}(\mathcal{E}_{n},\mathcal{F}_{n})$ is the free group
$\mathbb{Z}\Gamma_{n}^{k}$, we have
$C^{\bowtie}_{k}(\mathcal{E}_{n},\mathcal{F}_{n})\cong\mathbb{Z}X_{n}^{(k)}.$

Let $\langle\mathbf{a}_{0},\ldots,\mathbf{a}_{k}\rangle$ denote the generator
of $\mathbb{Z}X_{n}^{(k)}$ corresponding to
$(\mathbf{a}_{0},\ldots,\mathbf{a}_{k})\in X_{n}^{(k)}$. Using carats to
denote elision of coordinates, the face and degeneracy maps on
$C_{k}^{\bowtie}(\mathcal{E}_{n},\mathcal{F}_{n})$ are

$\partial^{\bowtie,i}_{k}\langle\mathbf{a}_{0},\ldots,\mathbf{a}_{k}\rangle=\langle\mathbf{a}_{0},\ldots,\widehat{\mathbf{a}}_{i},\ldots,\mathbf{a}_{k}\rangle\quad\text{and}\quad\sigma^{\bowtie,i}_{k}\langle\mathbf{a}_{0},\ldots,\mathbf{a}_{k}\rangle=\langle\mathbf{a}_{0},\ldots,\mathbf{a}_{i},\mathbf{a}_{i},\ldots,\mathbf{a}_{k}\rangle.$

A chain complex $(C_{\bullet},d_{\bullet})$ is _acyclic_ if
$H_{0}(C_{\bullet},d_{\bullet})\cong\mathbb{Z}$ and
$H_{k}(C_{\bullet},d_{\bullet})=0$ for $k\geq 1$.

Recall that an _initial object_ in a category $\mathcal{C}$ is an object
$v\in\mathcal{C}^{0}$ such that $w\mathcal{C}v$ has precisely one element for
each $w\in\mathcal{C}^{0}$.

The following is well-known, but could not find an explicit reference.

######  Lemma 5.6.

Let $\mathcal{C}$ be a small category with an initial object $v$. Let
$\mathbbm{1}$ be the category with a single morphism $1$. Let
$\iota\colon\mathbbm{1}\to\mathcal{C}$ be the functor such that $\iota(1)=v$.
Let $\rho$ be the unique functor from $\mathcal{C}$ to $\mathbbm{1}$. Then
$\rho\circ\iota=\operatorname{id}_{\mathbbm{1}}$, and
$(\iota\circ\rho)_{\bullet}\colon C_{\bullet}(\mathcal{C})\to
C_{\bullet}(\mathcal{C})$ is chain-homotopic to
$\operatorname{id}_{C_{\bullet}(\mathcal{C})}$. In particular,
$(C_{\bullet}(\mathcal{C}),d_{\bullet})$ is acyclic.

###### Proof.

Clearly, $\rho\circ\iota=\operatorname{id}_{\mathbbm{1}}$. For each
$w\in\mathcal{C}^{0}$ let $\tau_{w}\in\mathcal{C}$ be the unique morphism from
$v$ to $w$. Fix $k\geq 0$. For $0\leq i\leq k$ define $h^{i}\colon
C_{k}(\mathcal{C})\to C_{k+1}(\mathcal{C})$ by

$h^{i}[c_{0},\ldots,c_{k-1}]=\begin{cases*}[c_{0},\ldots,c_{i},\tau_{s(c_{i})},v,\ldots,v]&if
$i>0$\\\ [\tau_{r(c_{0})},v,\ldots,v]&if $i=0$.\end{cases*}$

To see that $h$ is a simplicial homotopy we need to check that
$\partial^{0}h^{0}=(\iota\circ\rho)_{k}$, that
$\partial^{k+1}h^{k}=\operatorname{id}_{C_{k}(\mathcal{C})}$, that
$\partial^{i}h^{j}=h^{j-1}\partial^{i}$ for $i<j$, that
$\partial^{i}h^{j}=h^{j}\partial^{i-1}$ for $i>j+1$, that
$\sigma^{i}h^{j}=h^{j+1}\sigma^{i}$ for $i\leq j$, and that
$\sigma^{i}h^{j}=h^{j}\sigma^{i-1}$ for $i>j$. For the first two identities,
we calculate

$\displaystyle\partial^{0}h^{0}[c_{0},\ldots,c_{k-1}]$
$\displaystyle=\partial^{0}[\tau_{r(c_{0})},v,\ldots,v]=[v,\ldots,v],\text{
and}$ $\displaystyle\partial^{k+1}h^{k}[c_{0},\ldots,c_{k-1}]$
$\displaystyle=\partial^{k+1}[c_{0},\ldots,c_{k-1},\tau_{s(c_{k-1})}]=[c_{0},\ldots,c_{k-1}].$

The remaining four conditions follow from similar calculations. For example,
if $0<i<j$, then

$\displaystyle\partial^{i}h^{j}[c_{0},\ldots,c_{k-1}]$
$\displaystyle=\partial^{i}[c_{0},\ldots,c_{j},\tau_{s(c_{j})},v,\ldots,v]=[c_{0},\ldots,c_{i-1}c_{i},\ldots,c_{j},\tau_{s(c_{j})},v,\ldots,v]$
$\displaystyle=h^{j-1}[c_{0},\ldots,c_{i-1}c_{i},\ldots,c_{j},\ldots,c_{k-1}]=h^{j-1}\partial^{i}[c_{0},\ldots,c_{k-1}].$

Hence, the simplicial maps $(\iota\circ p)_{\bullet}$ and
$\operatorname{id}_{C_{\bullet}(\mathcal{C})}$ are simplicially homotopic. So
$s_{k}\coloneqq\sum_{i=0}^{k}(-1)^{i}h_{k}^{i}$ defines a chain homotopy $s$
between $(\iota\circ p)_{\bullet}$ and
$\operatorname{id}_{C_{\bullet}(\mathcal{C})}$ [Wei94, Lemma 8.3.13].

The final statement follows from acyclicity of
$(C_{\bullet}(\mathbbm{1}),d_{\bullet})$. ∎

######  Lemma 5.7.

For each $n\geq 0$ the chain complex
$(C_{\bullet}^{\bowtie}(\mathcal{E}_{n},\mathcal{F}_{n}),d)$ is acyclic.

###### Proof.

The object $(n,0)$ is an initial object in
$\Gamma_{n}=\mathcal{E}_{n}\bowtie\mathcal{F}_{n}$, so the result follows from
Lemma 5.6. ∎

Chains in $C_{k,l}(\mathcal{E}_{n},\mathcal{F}_{n})$ also admit a tractable
description. The formula

$\displaystyle\mathcal{E}_{n}^{k}*\mathcal{F}_{n}^{l}\ni$
$\displaystyle((p_{0},q_{0}),(p_{1},q_{0}),\ldots,(p_{k},q_{0}),\ldots,(p_{k},q_{l-1}),(p_{k},q_{l}))$
$\displaystyle\quad\mapsto(p_{0},p_{1},\ldots,p_{k};q_{0},\ldots,q_{l-1},q_{l})\in
Y_{n}^{(k,l)}$

is a bijection between $\mathcal{E}_{n}^{k}*\mathcal{F}_{n}^{l}$ and

$Y_{n}^{(k,l)}\coloneqq\Big{\\{}(p_{0},\ldots,p_{k};q_{0},\ldots,q_{l})\in\mathbb{N}^{2k}\mid
p_{i}\leq p_{i+1},\,q_{i}\geq q_{i+1},\text{ and }p_{k}+q_{0}\leq n\Big{\\}},$

and induces an isomorphism
$C_{k,l}(\mathcal{E}_{n},\mathcal{F}_{n})\cong\mathbb{Z}Y_{n}^{(k,l)}.$

We write $\langle p_{0},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle$ for the
generator of $\mathbb{Z}Y_{n}^{(k,l)}$ that corresponds to the tuple
$(p_{0},\ldots,p_{k};q_{0},\ldots,q_{l})\in Y_{n}^{(k,l)}$. The face maps in
the double complex become

$\displaystyle\partial^{h,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle$ $\displaystyle=\langle
p_{0},\ldots,\widehat{p_{i}},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle\quad\text{and}$
$\displaystyle\partial^{v,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle$ $\displaystyle=\langle
p_{0},\ldots,p_{k};q_{0},\ldots,\widehat{q_{i}},\ldots,q_{l}\rangle.$

The degeneracy maps become

$\displaystyle\sigma^{h,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle$ $\displaystyle=\langle
p_{0},\ldots,p_{i-1},p_{i},p_{i},p_{i+1},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle\quad\text{and}$
$\displaystyle\sigma^{v,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{l}\rangle$ $\displaystyle=\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{i-1},q_{i},q_{i},q_{i+1},\ldots,q_{l}\rangle.$

In particular, for the diagonal complex
$C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})$ the face and
degeneracy maps are

$\displaystyle\partial^{\Delta,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{k}\rangle$ $\displaystyle=\langle
p_{0},\ldots,\widehat{p_{i}},\ldots,p_{k};q_{0},\ldots,\widehat{q_{i}},\ldots,q_{k}\rangle\quad\text{and}$
$\displaystyle\sigma^{\Delta,i}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{k}\rangle$ $\displaystyle=\langle
p_{0},\ldots,p_{i-1},p_{i},p_{i},p_{i+1},\ldots,p_{k};q_{0},\ldots,q_{i-1},q_{i},q_{i},q_{i+1},\ldots,q_{k}\rangle.$

######  Lemma 5.8.

The diagonal complex
$(C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n}),d^{\Delta})$ is
acyclic.

###### Proof.

Consider the directed graph
$G_{n}=0\overset{e_{0}}{\leftarrow}1\overset{e_{1}}{\leftarrow}\cdots\overset{e_{n-1}}{\leftarrow}n$.
Since $n$ is an initial object for $G_{n}^{*}$, Lemma 5.6 implies that
$(C_{\bullet}(G_{n}^{*}),d_{\bullet})$ is acyclic. So it suffices to show that
$(C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n}),d^{\Delta})$ is chain-
homotopic to $(C_{\bullet}(G_{n}^{*}),d)$.

The group $C_{k}(G_{n}^{*})$ is freely generated by $k$-tuples $\langle
p_{0},\ldots,p_{k}\rangle$ where $0\leq p_{i}\leq p_{i+1}\leq n$ for each
$0\leq i<k$. The functor $\iota\colon G_{n}^{*}\hookrightarrow\mathcal{E}_{n}$
given by $\iota(e_{p})=e_{p,0}$ induces a chain map $\iota\colon
C_{\bullet}(G_{n}^{*})\to
C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})$ satisfying
$\iota_{k}\langle p_{0},\ldots,p_{k}\rangle=\langle
p_{0},\ldots,p_{k};0,\ldots,0\rangle.$ The functor
$\rho\colon\mathcal{E}_{n}\to G_{n}^{*}$ defined by $\rho(e_{p,q})=e_{p}$,
induces a chain map $\rho\colon
C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})\to
C_{\bullet}(G_{n}^{*})$ satisfying $\rho_{k}\langle
p_{0},\ldots,p_{k};q_{0},\ldots,q_{k}\rangle=\langle
p_{0},\ldots,p_{k}\rangle.$ We have
$\rho_{k}\circ\iota_{k}=\operatorname{id}_{C_{k}(G_{n}^{*})}$. For $0\leq
i\leq k$ define $h^{i}\colon
C_{k}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})\to
C_{k+1}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})$ by

$h^{i}\langle p_{0},\ldots,p_{k};q_{0},\ldots,q_{k}\rangle=\langle
p_{0},\ldots,p_{i-1},p_{i},p_{i},p_{i+1},\ldots,p_{k};0,\ldots,0,q_{i},q_{i+1},\ldots,q_{k}\rangle.$

Direct calculation shows that
$\partial^{0}h^{0}=\operatorname{id}_{C_{k}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})}$
and $\partial^{k+1}h^{k}=(\iota\circ\rho)_{k}$.

It is routine to check that $\partial^{i}h^{j}=h^{j-1}\partial^{i}$ for $i<j$
and $\partial^{i}h^{j}=h^{j}\partial^{i-1}$ for $i>j+1$. Similarly,
$\sigma^{i}h^{j}=h^{j+1}\sigma^{i}$ for $i\leq j$ and
$\sigma^{i}h^{j}=h^{j}\sigma^{i-1}$ for $i>j$. It follows that the simplicial
maps $(\iota\circ p)_{\bullet}$ and
$\operatorname{id}_{C_{\bullet}^{\Delta}(\mathcal{E}_{n},\mathcal{F}_{n})}$
are simplicially homotopic. ∎

We identify some particularly useful chains in the categorical and diagonal
homology of $(\mathcal{E}_{2k},\mathcal{F}_{2k})$. For each $k\geq 0$ define
$x_{k}\in C_{k}^{\bowtie}(\mathcal{E}_{2k},\mathcal{F}_{2k})$ and $y_{k}\in
C_{k}^{\Delta}(\mathcal{E}_{2k},\mathcal{F}_{2k})$ by

$\displaystyle\begin{split}x_{k}&\coloneqq[f_{0,2k}e_{0,2k},f_{1,2k-1}e_{1,2k-1},\ldots,f_{k-1,k+1}e_{k-1,k+1}]=\langle(0,2k),(1,2k-1),\ldots,(k,k)\rangle\end{split}$
(5.8)

and

$\displaystyle\begin{split}y_{k}&\coloneqq[e_{0,k},e_{1,k},\ldots,e_{k-1,k};f_{k,k-1},\ldots,f_{k,1},f_{k,0}]=\langle
0,1,\ldots,k-1,k;k,k-1,\ldots,1,0\rangle.\end{split}$ (5.9)

Pictorially, $x_{k}$ and $y_{k}$ correspond to the following composable tuples
in $\mathcal{E}_{2k}\bowtie\mathcal{F}_{2k}$:

$x_{k}$$(k,0)$$(0,k)$$(k,k)$$(0,2k)$ $y_{k}$$(k,0)$$(0,k)$$(k,k)$$(0,2k)$

By Corollary 3.10, a matched pair morphism
$(\mathcal{E}_{n},\mathcal{F}_{n})\to(\mathcal{C},\mathcal{D})$ corresponds to
a functor $\Gamma_{n}\to\mathcal{C}\bowtie\mathcal{D}$ taking
$\mathcal{E}_{n}$ to $\mathcal{C}$ and $\mathcal{F}_{n}$ to $\mathcal{D}$. For
each $\gamma=(d_{0}c_{0},\ldots,d_{k-1}c_{k-1})$ in
$(\mathcal{C}\bowtie\mathcal{D})^{k}$, Lemma 3.25 gives a morphism
$h_{\gamma}^{\bowtie}\colon\Gamma_{2k}\to\mathcal{C}\bowtie\mathcal{D}$ such
that

$h^{\bowtie}_{\gamma}(f_{p,2k-1-p}e_{p,2k-1-p})=\begin{cases}d_{p}c_{p}&\text{if
}0\leq p<k\\\ s(c_{k-1})&\text{if }k\leq p<2k.\end{cases}$

For
$\lambda=(c_{0},\ldots,c_{k-1},d_{0},\ldots,d_{k-1})\in\mathcal{C}^{k}*\mathcal{D}^{k}$,
with $d^{\prime}_{i}=r(c_{i})$ and $c^{\prime}_{i}=s(d_{i})$, Lemma 3.25
applied to
$(d^{\prime}_{0}c_{0},\cdots,d^{\prime}_{k-1}c_{k-1},d_{0}c^{\prime}_{0},\dots,d_{k-1}c^{\prime}_{k-1})$
yields a morphism
$h_{\lambda}^{\Delta}\colon\Gamma_{2k}\to\mathcal{C}\bowtie\mathcal{D}$ such
that

$h_{\lambda}^{\Delta}(f_{p,2k-1-p}e_{p,2k-1-p})=\begin{cases}c_{p}&\text{if
}0\leq p<k\\\ d_{p-k}&\text{if }k\leq p<2k.\end{cases}$

######  Lemma 5.9.

Let $(\mathcal{C},\mathcal{D})$ be a matched pair. For
$\gamma\in(\mathcal{C}\bowtie\mathcal{D})^{k}$ and
$\lambda\in\mathcal{C}^{k}*\mathcal{D}^{k}$ we have
$[\gamma]=C^{\bowtie}_{k}(h^{\bowtie}_{\gamma})(x_{k})$ and
$[\lambda]=C^{\Delta}_{k}(h^{\Delta}_{\lambda})(y_{k})$. Moreover,

$\\{C^{\bowtie}_{k}(h)(x_{k})\mid
h\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})\\}\quad\text{
and }\quad\\{C_{k}^{\Delta}(h)(y_{k})\mid
h\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})\\}$

generate $C^{\bowtie}_{k}(\mathcal{C},\mathcal{D})$ and
$C^{\Delta}_{k}(\mathcal{C},\mathcal{D})$ respectively.

###### Proof.

That $[\gamma]=C^{\bowtie}_{k}(h^{\bowtie}_{\gamma})(x_{k})$ and
$[\lambda]=C^{\Delta}_{k}(h^{\Delta}_{\lambda})(y_{k})$ follow immediately
from the definitions of $h^{\bowtie}_{\gamma}$ and $h^{\Delta}_{\lambda}$. For
the second statement, let
$h\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})$ be a
matched pair morphism. Then
$C^{\bowtie}_{k}(h)(x_{k})=[h(f_{0,2k}e_{0,2k}),\ldots,h(f_{k-1,k+1}e_{k-1,k+1})]$.
So

$\displaystyle\\{C^{\bowtie}_{k}(h)(x_{k})\mid
h\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})\\}\supseteq\\{C^{\bowtie}_{k}(h^{\bowtie}_{\gamma})(x_{k})\mid\gamma\in(\mathcal{C}\bowtie\mathcal{D})^{k}\\}=\\{[\gamma]\mid\gamma\in(\mathcal{C}\bowtie\mathcal{D})^{k}\\},$

which generates $C_{k}^{\bowtie}(\mathcal{C},\mathcal{D})$. Similarly,

$\\{C_{k}^{\Delta}(h)(y_{k})\mid
h\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})\\}\supseteq\\{[\lambda]\mid\lambda\in\mathcal{C}^{k}*\mathcal{D}^{k}\\}$

generates $C_{k}^{\Delta}(\mathcal{C},\mathcal{D})$. ∎

In the terminology of [Rot88, pp. 239–240], Lemma 5.9 says that the functors
$C_{k}^{\bowtie}$ and $C_{k}^{\Delta}$ from ${\mathsf{MP}}$ to
${\mathsf{Ch}}_{\bullet}$ are _free_ with bases $\\{x_{k}\\}$ and
$\\{y_{k}\\}$, giving the following lemma.

######  Lemma 5.10 ([Rot88, Lemma 9.10]).

If $G\colon{\mathsf{MP}}\to{\mathsf{Ab}}$ is a functor and $g\in
G(\mathcal{E}_{2k},\mathcal{F}_{2k})$, then there is a unique natural
transformation $\alpha\colon C_{k}^{\bowtie}\to G$ such that
$\alpha_{(\mathcal{E}_{2k},\mathcal{F}_{2k})}(x_{k})=g,$ and a unique natural
transformation $\beta\colon C_{k}^{\Delta}\to G$ such that
$\beta_{(\mathcal{E}_{2k},\mathcal{F}_{2k})}(y_{k})=g.$

The proof of [Rot88, Lemma 9.10] describes the natural transformations of
Lemma 5.10: for $[\gamma]\in C_{k}^{\bowtie}(\mathcal{C},\mathcal{D})$, Lemma
5.9 gives
$h_{\gamma}^{\bowtie}\colon(\mathcal{E}_{2k},\mathcal{F}_{2k})\to(\mathcal{C},\mathcal{D})$
such that $h_{\gamma}^{\bowtie}(x_{k})=[\gamma]$, and then
$\alpha_{(\mathcal{C},\mathcal{D})}([\gamma])\coloneqq
G(h_{\gamma}^{\bowtie})(g)$. Similarly,
$\beta_{(\mathcal{C},\mathcal{D})}([\lambda])\coloneqq
G(h_{\lambda}^{\Delta})(g)$ for $[\lambda]\in
C_{k}^{\Delta}(\mathcal{C},\mathcal{D})$.

###  5.4. Proof of the main theorem

To prove Theorem 5.3 we construct a chain equivalence between
$C_{\bullet}^{\bowtie}$ and $C_{\bullet}^{\Delta}$ inductively using [Rot88,
Theorem 9.12].

######  Lemma 5.11.

The identity map
$C_{0}^{\Delta}(\mathcal{C},\mathcal{D})\coloneqq\mathbb{Z}X\overset{\operatorname{id}}{\to}\mathbb{Z}X\eqqcolon
C_{0}^{\bowtie}(\mathcal{C},\mathcal{D})$ induces a natural isomorphism
$\widetilde{\operatorname{id}}:H_{0}^{\bowtie}\cong H_{0}^{\Delta}$.

###### Proof.

Fix a matched pair $(\mathcal{C},\mathcal{D})$ with objects $X$. Identifying
$C_{0}^{\Delta}(\mathcal{C},\mathcal{D})$ with
$C_{0}^{\bowtie}(\mathcal{C},\mathcal{D})$ via the identity map on
$\mathbb{Z}X$, it suffices to show that
$\operatorname{im}(d^{\bowtie})=\operatorname{im}(d^{\Delta})$ in
$\mathbb{Z}X$. If $[d,c]\in C_{1}^{\bowtie}(\mathcal{C},\mathcal{D})$, then
$d^{\bowtie}[d,c]=[s(c)]-[r(d)]=d^{\Delta}[c,s(c)]+d^{\Delta}[r(d),d]\in\operatorname{im}(d^{\Delta}).$
If $[c,d]\in C_{1}^{\Delta}(\mathcal{C},\mathcal{D})$, then
$d^{\Delta}[c,d]=[s(d)]-[r(c)]=d^{\bowtie}[c\bowtie
d]\in\operatorname{im}(d^{\bowtie}).$ ∎

######  Proposition 5.12.

There exist natural chain maps $\alpha\colon C_{\bullet}^{\bowtie}\to
C_{\bullet}^{\Delta}$ and $\beta\colon C_{\bullet}^{\Delta}\to
C_{\bullet}^{\bowtie}$ such that $\alpha\circ\beta$ is naturally chain-
homotopic to $\operatorname{id}_{C_{\bullet}^{\Delta}}$ and $\beta\circ\alpha$
is naturally chain-homotopic to $\operatorname{id}_{C_{\bullet}^{\bowtie}}$
such that $\alpha$ and $\beta$ lift the natural isomorphism
$H_{0}^{\bowtie}\cong H_{0}^{\Delta}$, in the sense that the diagram

${{C_{2}^{\bowtie}}}$${{C_{1}^{\bowtie}}}$${{C^{\bowtie}_{0}}}$${{H^{\bowtie}_{0}}}$${0}$${{C_{2}^{\Delta}}}$${{C_{1}^{\Delta}}}$${{C_{0}^{\Delta}}}$${{H^{\Delta}_{0}}}$${0}$${{C_{2}^{\bowtie}}}$${{C_{1}^{\bowtie}}}$${{C^{\bowtie}_{0}}}$${{H^{\bowtie}_{0}}}$${0}$$\scriptstyle{d_{1}^{\bowtie}}$$\scriptstyle{d_{0}^{\bowtie}}$$\scriptstyle{d_{1}^{\Delta}}$$\scriptstyle{d_{0}^{\Delta}}$$\scriptstyle{d_{1}^{\bowtie}}$$\scriptstyle{d_{0}^{\bowtie}}$$\scriptstyle{\widetilde{\operatorname{id}}}$$\scriptstyle{\widetilde{\operatorname{id}}}$$\scriptstyle{\alpha_{0}}$$\scriptstyle{\beta_{0}}$$\scriptstyle{\alpha_{1}}$$\scriptstyle{\beta_{1}}$$\scriptstyle{\alpha_{2}}$$\scriptstyle{\beta_{2}}$
(5.10)

of natural transformations commutes. If $\alpha^{\prime}\colon
C_{\bullet}^{\bowtie}\to C_{\bullet}^{\Delta}$ and $\beta^{\prime}\colon
C_{\bullet}^{\Delta}\to C_{\bullet}^{\bowtie}$ are chain maps that lift the
natural isomorphism $H_{0}^{\bowtie}\cong H_{0}^{\Delta}$, then they are
naturally chain-homotopic to $\alpha$ and $\beta$.

For $k\geq 0$, let $x_{k},y_{k}$ be as in (5.8) and (5.9). If for each $k\geq
0$, $\alpha_{k}\colon C_{k}^{\Delta}\to C_{k}^{\bowtie}$ is a natural
transformation such that $d^{\Delta}\circ\alpha_{k}(x_{k})=\alpha_{k-1}\circ
d^{\Delta}(x_{k})$, then $\alpha=(\alpha_{k})$ is a natural chain equivalence
from $C_{\bullet}^{\bowtie}$ to $C_{\bullet}^{\Delta}$. Similarly, if for each
$k\geq 0$, $\beta_{k}\colon C_{k}^{\bowtie}\to C_{k}^{\Delta}$ is a natural
transformations such that $d^{\bowtie}\circ\beta_{k}(y_{k})=\beta_{k-1}\circ
d^{\bowtie}(y_{k})$, then $\beta=(\beta_{k})$ is a natural chain equivalence
from $C_{\bullet}^{\Delta}$ to $C_{\bullet}^{\bowtie}$.

The result is standard and follows from [Rot88, Theorem 9.12], but we include
some details to describe the resulting isomorphisms in homology explicitly.

###### Proof.

The morphisms $\alpha_{0}$ and $\beta_{0}$ are induced by the identity maps on
objects. We start by constructing $\alpha$. Suppose that there exists maps
$\alpha_{n}$, for $n<k$ such that the right-most $n+1$ squares of (5.10)
commute. Consider the matched pair $(\mathcal{E}_{2k},\mathcal{F}_{2k})$ and
let $x_{k}\in C_{k}^{\bowtie}(\mathcal{E}_{2k},\mathcal{F}_{2k})$ be as in
(5.8). Commutativity of (5.10) implies that
$d^{\Delta}\alpha_{k-1}d^{\bowtie}=(d^{\Delta})^{2}\alpha_{k-2}=0$. Lemma 5.7
implies that
$(C_{\bullet}^{\bowtie}(\mathcal{E}_{2k},\mathcal{F}_{2k}),d^{\bowtie})$ is
acyclic, so there exists $\overline{x}_{k}\in
C_{k}^{\Delta}(\mathcal{E}_{2k},\mathcal{F}_{2k})$ such that
$d^{\Delta}(\overline{x}_{k})=\alpha_{k-1}d^{\bowtie}(x_{k})$. So Lemma 5.10
yields a unique natural transformation $\alpha_{k}\colon C_{k}^{\bowtie}\to
C_{k}^{\Delta}$ such that
$\alpha_{k}^{(\mathcal{E}_{2k},\mathcal{F}_{2k})}(x_{k})=\overline{x}_{k}$ and
$d^{\Delta}\alpha_{k}=\alpha_{k-1}d^{\bowtie}$.