format: text

text:
# Crossed squares and 2-crossed modules

## 1 Introduction

Simplicial groups were first studied by D. M. Kan in the 1950s . Early work by Kan himself, Moore, Milnor, and Dold showed that
(a) these objects have a well structured homotopy theory,
(b) they modelled all homotopy types of connected spaces,
(c) abelian simplicial groups were an equivalent tool to that of chain complexes and could therefore be applied within homological algebra, and
(d) in low dimensions, calculations were possible, provided, for instance, the simplicial group was free with chosen $`\mathrm{`}CW`$-basis’.

Simplicially enriched groupoids have a more recent birth, but have the same sort of attributes plus being able to model non-connected homotopy types. The shortened form of their name ‘simplicial groupoid’ used by Dwyer and Kan  is more usually used for these objects although not strictly correct as simplicial objects in the category of groupoids form a much larger setting than do simplicially enriched groupoids. None the less we will often use that shortened form here.

Crossed modules model homotopy 2-types. Crossed squares model 3-types. Crossed $`n`$-cubes model $`(n+1)`$types, cf.  and the references therein. Conduché  has an alternative model for 3-types namely 2-crossed modules and Baues  uses a variant of this, the quadratic module, in some of his work. Another model for 3-types was introduced by Brown and Gilbert, , (involving a particular subdivided triangular diagram in its derivation). This model, braided crossed modules and their lax counterpart, the braided categorical groups, have been further studied by members of the Granada Algebra group (cf. Carrasco and Cegarra, , and Garzon and Miranda, , for example). Similar object, Gray groupoids, have been studied by Joyal and Tierney (unpublished) and have recently started to receive some attention in the TQFT literature. The proof of the equivalence between Gray groupoids (that is, 2-groupoid enriched groupoids) and Conduché’s models is discussed in  and more detailed references to other work by LeRoy, Berger, Marty, and, of course, the original proof from the 1980s by Joyal and Tierney, can be found there as well as in the bibliography of this paper.

In a letter to Brown and Loday, dated in the mid 1980s, Conduché pointed out that given a crossed square,

$$=\left(\text{}\right),$$

the mapping cone complex of $``$,

$$LMNP$$

constructed by Loday in , has a 2-crossed module structure. He ended his letter by pointing out that this seemed to give a canonical and direct way to link the categories of crossed squares and 2-crossed modules, and his results suggested that it should yield some sort of equivalence between the two models.

Although much more is known on this area than when Conduché’s letter was written, the background underlying structure still seems obscure. In this paper we aim to shed some light on the 2-crossed module structure given by Conduché and also on the subdivided triangular diagram of Brown and Gilbert. This, in fact, provides the key and suggests ways of generalising Conduché’s construction to higher $`n`$-types.

## 2 Preliminaries

### 2.1 Simplicial Groups and Groupoids

We assume that the reader is conversant with the basic theory of simplicial sets and simplicial groups. The following merely sets up notation and some conventions.

Let $`𝔊𝔯𝔭`$ be the category of groups. A simplicial group $`𝐆`$ consists of a family of groups $`\{G_n\}`$ together with face and degeneracy maps $`d_i=d_i^n:G_nG_{n1},`$ $`0i<n`$ $`(n0)`$ and $`s_i=s_i^n:G_nG_{n+1}`$, $`0in,`$ satisfying the usual simplicial identities given in ,  and . It can be completely described as a functor $`𝐆:\mathrm{\Delta }^{op}𝔊𝔯𝔭`$ where $`\mathrm{\Delta }`$ is the category of finite ordinals, $`[n]=\{0<1<2<\mathrm{}<n\}`$, and increasing maps. We will denote the category of simplicial group by $`𝔖𝔦𝔪𝔭𝔊𝔯𝔭𝔰.`$ We have for each $`k0`$, a subcategory $`\mathrm{\Delta }_k`$ determined by objects $`[j]`$ of $`\mathrm{\Delta }`$ with $`jk.`$ A $`k`$-truncated simplicial group is a functor from $`(\mathrm{\Delta }_k^{op})`$ to $`𝔊𝔯𝔭`$, where $`(\mathrm{\Delta }_k^{op})`$ has the obvious meaning.

Remark:

We will restrict detailed attention in the main to simplicial groups and hence to connected homotopy types. This is traditional but a bit unnatural as all the results and definitions extend with little or no trouble to simplicial groupoids in the sense of Dwyer and Kan  and hence to non-connected homotopy types. It should be noted that such simplicial groupoids have a fixed and constant simplicial set of objects and so are not merely simplicial objects in the category of groupoids. In this context if $`𝐆`$ is a simplicial groupoid with set of objects $`O`$, the natural form of the Moore complex $`\mathrm{𝐍𝐆}`$ (see below) is given by the same formula as in the reduced case, interpreting Ker$`d_i^n`$ as being the subgroupoid of elements in $`G_n`$ whose $`i`$th face is an identity of $`G_{n1}`$. Of course if $`n1`$, the resulting $`NG_n`$ is a disjoint union of groups, so $`\mathrm{𝐍𝐆}`$ is a disjoint union of the Moore complexes of the vertex simplicial groups of $`𝐆`$ together with the groupoid $`G_0`$ providing elements that allow conjugation between (some of) these vertex complexes (cf. Ehlers and Porter ).

Consider the product $`\mathrm{\Delta }\times \mathrm{\Delta }`$ whose objects are pairs $`([p],[q])`$ and whose maps are pairs of weakly increasing maps. A functor $`𝒢:(\mathrm{\Delta }\times \mathrm{\Delta })^{op}𝔊𝔯𝔭`$ is called a bisimplicial group. To give $`𝒢`$ is equivalent to giving for each $`(p,q)`$ a group $`G_{p,q}`$ and homomorphisms

$$\begin{array}{ccccc}d_i^h\hfill & :\hfill & G_{p,q}G_{p1,q}\hfill & & \\ s_i^h\hfill & :\hfill & G_{p,q}G_{p+1,q}\hfill & i:0,1,\mathrm{},p\hfill & \\ d_j^v\hfill & :\hfill & G_{p,q}G_{p,q1}\hfill & & \\ s_j^v\hfill & :\hfill & G_{p,q}G_{p,q+1}\hfill & j:0,1,\mathrm{},p\hfill & \end{array}$$

such that the maps $`d_i^h,s_i^h`$ commute with $`d_j^v,s_j^v`$ and $`d_i^h,s_i^h`$ (resp. $`d_j^v,s_j^v`$) and satisfy the usual simplicial identities. Here $`d_i^h,s_i^h`$ denote the horizontal operators and $`d_j^vs_j^v`$ denote the vertical operators. A bisimplicial group can also be thought of as a simplicial object in the category of simplicial groups.

Multisimplicial groups are similarly defined. Explicitly if $`n`$ is a positive integer, form the $`n`$-fold product $`\mathrm{\Delta }^{\times n}`$ of $`\mathrm{\Delta }`$ with itself, then an $`n`$-simplicial group is merely a functor $`𝒢:(\mathrm{\Delta }^{\times n})^{op}𝔊𝔯𝔭`$. Of course an $`n`$-simplicial group leads to an $`n`$-indexed family of groups $`G_{p_1,\mathrm{},p_n}`$ with face and degeneracy operators in the obvious way, generalising the case $`n=2`$ discussed above.

All of this extends painlessly to simplicial groupoids and with obvious definitions of morphisms of $`n`$-simplicial groups and groupoids, we thus get a whole host of categories $`n𝔖𝔦𝔪𝔭𝔊𝔯𝔭𝔰`$ and $`n𝔖𝔦𝔪𝔭𝔊𝔯𝔡𝔰`$.

Recall from  that a normal chain complex of groups, $`(X,d)`$ means one in which each Im$`d_{i+1}`$ is a normal subgroup of the corresponding $`X_i.`$ Given any normal chain complex $`(X,d)`$ of groups and an integer $`n`$, the truncation, $`t_{n]}X`$ of $`X`$ at level $`n`$ is defined by

$$(t_{n]}X)_i=\{\begin{array}{ccc}X_i\hfill & \text{if }i<n\hfill & \\ X_i/\text{Im}d_{n+1}\hfill & \text{if }i=n\hfill & \\ 0\hfill & \text{if }i>n.\hfill & \end{array}$$

The differential $`d`$ of $`t_{n]}X`$ is that of $`X`$ for $`i<n,`$ whilst $`d_n`$ is induced by the $`n^{\mathrm{th}}`$ differential of $`X`$ and all other differentials are zero.

There are multicomplex and groupoid versions of this. The only points worth noting here are that any non trivial normal subgroupoid is a kernel and hence must be a disjoint union of its vertex groups and that in a normal $`n`$-multicomplex of groups, $`(X,d_1,\mathrm{},d_n)`$, each image in each direction is assumed normal in each dimension.

### 2.2 The Moore complex of simplicial group

The archetypal normal $`n`$-complex of group(oid)s is the Moore complex of an $`n`$-simplicial group(oid). In particular given a simplicial group $`𝐆,`$ the Moore complex $`(\mathrm{𝐍𝐆},)`$ of $`𝐆`$ is the normal chain complex defined by

$$\mathrm{𝐍𝐆}_n=\underset{i=0}{\overset{n1}{}}\text{Ker}d_i$$

and with differential $`_n:NG_nNG_{n1}`$ induced from $`d_n`$ by restriction.

To form the Moore $`n`$-complex of an $`n`$-simplicial group(oid) one just applies the functor $`N`$ repeatedly in each direction in turn.

There is an extensive theory of the Moore complex and its links with homotopy theory. We mention that $`\pi _n(G)`$ can be calculated by calculating the $`n^{\mathrm{th}}`$ homology group of $`(\mathrm{𝐍𝐆},)`$. Explicitly the $`n^{\mathrm{th}}`$ homotopy group $`\pi _n(𝐆)`$ of $`𝐆`$ is defined to be the $`n^{\mathrm{th}}`$ homology of the Moore complex of $`𝐆,`$ i.e.,

$$\pi _n(𝐆)H_n(\mathrm{𝐍𝐆},)=\underset{i=0}{\overset{n}{}}\text{Ker}d_i^n/d_{n+1}^{n+1}(\underset{i=0}{\overset{n}{}}\text{Ker}d_i^{n+1}).$$

We say that the Moore complex $`\mathrm{𝐍𝐆}`$ of a simplicial group is of length $`k`$ if $`NG_n=1`$ for all $`nk+1`$ so that a Moore complex of length $`k`$ also has length $`l`$ for $`lk.`$

A simplicial map $`f:𝐆𝐆^{}`$ is called an $`n`$-equivalence if it induces isomorphisms

$$\pi _k(𝐆)\pi _k(𝐆^{})\text{for}kn.$$

Composites of $`n`$-equivalences are, of course, also $`n`$-equivalences. Two simplicial groups, $`𝐆`$ and $`𝐆^{}`$, are said to have the same $`n`$-type if there is a zig-zag chain of $`n`$-equivalences linking them. A simplicial group $`𝐆`$ *is an $`n`$-type* if $`\pi _i(𝐆)=1`$ for $`i>n.`$

The Moore complex carries a lot of fine structure and this has been studied, e.g. by Carrasco and Cegarra, , Wu , and the present authors in earlier papers in this series, . The specific structure of the $`k`$-truncation of the Moore complex for $`k=1`$ and 2 is now well known. For $`k=1`$ this gives a crossed module, for $`k=2`$, a 2-crossed module, cf. Conduché, . We summarise his theory below. The hypercrossed complex structure of Carrasco and Cegarra, , clearly models all homotopy types and on $`k`$-truncation, all $`(k+1)`$-types, but the structure does get unwealdy for $`k`$ larger than about 3 or 4.

All of this theory works for both simplicial groups and simplicially enriched groupoids with virtually identical presentations. Rather than write ‘simplicial group(oid)’ all the time we have written the exposition in terms of simplicial groups but the other case works in the same way.

## 3 2-crossed modules and simplicial groups

Crossed module techniques give a very efficient way of handling information about a homotopy type. They correspond to 2-types (see  and ). As mentioned above Conduché, , in 1984 introduced the notion of 2-crossed module as a model for 3-types.

Throughout this paper we denote an action of $`pP`$ on $`mM`$ by $`pm={}_{}{}^{p}m.`$

A crossed module is a group homomorphism $`:MP`$ together with an action of $`P`$ on $`M`$ satisfying
(C1) $`({}_{}{}^{p}m)=p(m)p^1`$
and
(C2) $`{}_{}{}^{m}m_{}^{}=mm^{}m^1`$ for all $`m,m^{}M,pP.`$

This second condition is called the Peiffer identity. We will denote such a crossed module by $`(M,P,).`$

A morphism of crossed modules from $`(M,P,)`$ to $`(M^{},P^{},^{})`$ is a pair of group homomorphisms, $`\varphi :MM^{}`$, $`\psi :PP^{}`$ such that $`\varphi ({}_{}{}^{p}m)={}_{}{}^{\psi (p)}\varphi (m)`$ and $`^{}\varphi (m)=\psi (m)`$. We thus get a category $`𝔛𝔐𝔬𝔡`$ of crossed modules.

Examples of crossed modules

(a) Any normal subgroup $`N`$ in $`P`$ gives an inclusion map, inc$`:NP`$ which is a crossed module. Conversely given any arbitrary crossed module $`:MP,`$ one can easily see that the Peiffer identity implies that $`M=P`$ is a normal subgroup in $`P.`$
(b) Given any $`P`$-module, $`L`$, the trivial homomorphism $`\mathrm{𝟏}:LP`$ is a crossed $`P`$-module for the given action of $`P`$ on $`L`$.

The following definition of 2-crossed modules is equivalent to that given by D.Conduché, .

Definition:

A *2-crossed module* consists of a complex of groups

together with an action of $`N`$ on $`L`$ and $`M`$ so that $`_2,_1`$ are morphisms of $`N`$-groups, where the group $`N`$ acts on itself by conjugation, and an $`N`$-equivariant function

$$\{,\}:M\times ML$$

called a  *Peiffer lifting*, which satisfies the following axioms:

$$\begin{array}{ccccc}2CM1:\hfill & & \hfill _2\{m,m^{}\}& =& (^{_1m}m^{})(m(m^{})^1m^1),\hfill \\ 2CM2:\hfill & & \hfill \{_2(l),_2(l^{})\}& =& [l^{},l],\hfill \\ 2CM3:\hfill & (i)\hfill & \hfill \{mm^{},m^{\prime \prime }\}& =& ^{_1m}\{m^{},m^{\prime \prime }\}\{m,m^{}m^{\prime \prime }(m^{})^1\},\hfill \\ & (ii)\hfill & \hfill \{m,m^{}m^{\prime \prime }\}& =& \{m,m^{}\}{}_{}{}^{mm^{}(m)^1}\{m,m^{\prime \prime }\},\hfill \\ 2CM4:\hfill & & \hfill \{m,_2l\}\{_2l,m\}& =& ^{_1m}l(l)^1,\hfill \\ 2CM5\hfill & & \hfill ^n\{m,m^{}\}& =& \{^nm,^nm^{}\},\hfill \end{array}$$

for all $`l,l^{}L,m,m^{},m^{\prime \prime }M`$ and $`nN.`$

Here we have used $`{}_{}{}^{m}l`$ as a shorthand for $`\{_2l,m\}l`$ in condition 2CM3(ii) where $`l`$ is $`\{m,m^{\prime \prime }\}`$ and $`m`$ is $`mm^{}(m)^1`$. This gives a new action of $`M`$ on $`L`$. Using this notation, we can split 2CM4 into two pieces, the first of which is tautologous:

$$\begin{array}{ccccc}2CM4:\hfill & (a)\hfill & \hfill \{_2l,m\}& =& {}_{}{}^{m}(l).l^1,\hfill \\ & (b)\hfill & \hfill \{m,_2l\}& =& ({}_{}{}^{_1m}l)({}_{}{}^{m}l_{}^{1}).\hfill \end{array}$$

The old action of $`M`$ on $`L`$, via $`_1`$ and the $`N`$action on $`L`$, is in general distinct from this second action with $`\{m,_2(l)\}`$ measuring the difference (by 2CM4(b)). An easy argument using 2CM2 and 2CM4(b) shows that with this action, $`{}_{}{}^{m}l`$, of $`M`$ on $`L`$, $`(L,M,_2)`$ becomes a crossed module.

We denote such a 2-crossed module by $`\{L,M,N,_2,_1\}.`$ A morphism of 2-crossed modules is given by a diagram

where $`f_0_1=_1^{}f_1,f_1_2=_2^{}f_2,`$

$$f_1({}_{}{}^{n}m_{1}^{})={}_{}{}^{f_0(n)}f_{1}^{}(m_1),f_2({}_{}{}^{n}l)={}_{}{}^{f_0(n)}f_{2}^{}(l),$$

and

$$\{,\}f_1\times f_1=f_2\{,\},$$

for all $`lL,m_1M,nN.`$ These compose in an obvious way.

The groupoid analogues of these definitions are left to the reader. We will concentrate on the reduced case i.e. with groups rather than groupoids.

We thus can consider the category of 2-crossed modules denoting it as $`𝔛_\mathfrak{2}𝔐𝔬𝔡.`$ Conduché  proved that 2-crossed modules give algebraic models of connected homotopy 3-types.

###### Theorem 3.1

(, ) The category, $`𝔛_\mathfrak{2}𝔐𝔬𝔡`$, of $`2`$-crossed modules is equivalent to the category $`𝔖𝔦𝔪𝔭𝔊𝔯𝔭_2`$ of simplicial groups with Moore complex of length $`2`$. $`\mathrm{}`$

## 4 Cat2-groups and crossed squares

The following definition is due to D. Guin-Walery and J.-L. Loday, see  and also .

Definition:

A crossed square of groups is a commutative square of groups

together with actions of $`P`$ on $`L`$, $`M`$ and $`N.`$ There are thus actions of $`N`$ on $`L`$ and $`M`$ via $`\mu ^{}`$ and $`M`$ acts on $`L`$ and $`N`$ via $`\mu `$ and a function $`h:M\times NL`$ such that, for all $`lL,m_1,mM,n_1,nN`$ and $`pP`$ the following axioms hold:

1. the homomorphisms $`\lambda ,\lambda ^{},\mu \mu ^{}`$ and $`\kappa =\mu \lambda =\mu ^{}\lambda ^{}`$ are crossed modules for the corresponding actions and the morphisms of maps $`(\lambda )(\kappa );(\kappa )(\mu )`$$`(\lambda ^{})(\kappa )`$; and $`(\kappa )(\mu ^{})`$ are morphisms of crossed modules,
2. $`\lambda h(m,n)=m{}_{}{}^{\mu ^{}(n)}m,`$
3. $`\lambda ^{}h(m,n)={}_{}{}^{\mu (m)}n(n)^1,`$
4. $`h(\lambda (l),n)=l{}_{}{}^{n}l_{}^{1},`$
5. $`h(m,\lambda ^{}(l))=({}_{}{}^{m}l)l^1,`$
6. $`h(mm_1,n)={}_{}{}^{m}h(m_1,n)h(m,n),`$
7. $`h(m,nn_1)=h(m,n){}_{}{}^{n}h(m,n_1),`$
8. $`h({}_{}{}^{p}m,{}_{}{}^{p}n)={}_{}{}^{p}h(m,n),`$

The category of crossed squares will be denoted, $`𝔯𝔰^\mathfrak{2}.`$

In the simplest examples of crossed squares (see ), $`\mu `$ and $`\mu ^{}`$ are normal subgroup inclusions and $`L=MN,`$ with $`h`$ being the conjugation map. We also note that if

is a simplicial crossed square constructed from a simplicial group $`𝐆`$ and two simplicial normal subgroups $`𝐌`$ and $`𝐍`$ then applying $`\pi _0`$, the square gives a crossed square and that up to isomorphism all crossed squares arise in this way, again see .

Although when first defined by D. Guin-Walery and J.-L. Loday , the notion of crossed squares was not linked to that of cat2-groups, it was in this form that Loday gave their generalisation to an $`n`$-fold structure, catn-groups (see ).

Recall from  that a cat1-group is a triple $`(G,s,t)`$, where $`G`$ is a group and $`s,t`$ are endomorphisms of $`G`$ satisfying conditions
(i) $`st=t`$ and $`ts=s.`$
(ii) $`[\text{Ker}s,\text{Ker}t]=1.`$

It was shown  that setting $`M=\text{Ker}s,`$ $`N=\text{Im}s`$ and $`=t|M,`$ then the action of $`N`$ on $`M`$ by conjugation within $`G`$ makes $`:MN`$ into a crossed module. Conversely if $`:MN`$ is a crossed module, then setting $`G=MN`$ and letting $`s,t`$ be defined by

$$s(m,n)=(1,n)$$

and

$$t(m,n)=(1,(m)n)$$

for $`mM,nN,`$ we have that $`(G,s,t)`$ is a cat1-group.

For a cat2-group, we again have a group, $`G`$, but this time with two independent cat1-group structures on it. Explicitly:

A cat2-group is a 5-tuple $`(G,s_1,t_1,s_2,t_2),`$ where $`(G,s_i,t_i),`$ $`i=1,2,`$ are cat1-groups and

$$s_is_j=s_js_i,t_it_j=t_jt_i,s_it_j=t_js_i$$

for $`i,j=1,2`$, $`ij.`$

###### Theorem 4.1

 There is an equivalence of categories between the category of cat2-groups and that of crossed squares.

We include a sketch of the proof as it contains ideas that will be needed later.

Proof: The cat1-group $`(G,s_1,t_1)`$ will gives us a crossed module with $`M=\text{Ker}s,N=\text{Im}s`$, and $`=t|M,`$ but as the two cat1-group structures are independent, $`(G,s_2,t_2)`$ restricts to give cat1-group structures on $`M`$ and $`N`$ and makes $``$ a morphism of cat1-groups. We thus get a morphism of crossed modules

where each morphism is a crossed module for the natural action, i.e., conjugation in $`G.`$ It remains to produce an $`h`$-map, but this is given by the commutator within $`G`$ since if $`x\text{Ker}s_2\text{Im}s_1`$ and $`y\text{Im}s_2\text{Ker}s_1`$ then $`[x,y]\text{Ker}s_1\text{Ker}s_2.`$ It is easy to check the axioms for a crossed square.

Conversely, if

is a crossed square, then we can think of it as a morphism of crossed modules

Using the equivalence between crossed modules and cat1-groups this gives a morphism

$$:(LN,s,t)(MP,s^{},t^{})$$

of cat1-groups. There is an action of $`(m,p)MP`$ on $`(l,n)LN`$ given by

$${}_{}{}^{(m,p)}(l,n)={}_{}{}^{m}({}_{}{}^{p}l,{}_{}{}^{p}n)=({}_{}{}^{\mu (m)p}lh(m,{}_{}{}^{p}n),{}_{}{}^{p}n).$$

Using this action, we thus form the associated cat1-group with ‘big’ group $`(LN)(MP)`$ and induced endomorphisms, $`s_1,t_1,s_2,t_2.`$ $`\mathrm{}`$

It is easy to show that cat1-groups are merely a reformulation of an internal groupoid in the category $`𝔊𝔯𝔭𝔰`$ of groups, whilst cat2-groups correspond similarly to double groupoid objects in $`𝔊𝔯𝔭𝔰`$.

## 5 Crossed $`n`$-cubes and simplicial groups

In the form given above, crossed squares were difficult to generalise to higher order structures, although cat2-groups could clearly and easily be generalised to catn-groups. The following generalisation is due to Ellis and Steiner  and includes a reformulation of crossed squares as a special case.. Let $`n`$ denote the set $`\{1,\mathrm{},n\}.`$

A crossed $`n`$-cube of group is a family $`\{𝔐_A:An\}`$ of groups, together with homomorphisms $`\mu _i:𝔐_A𝔐_{A\{i\}}`$ for $`in`$ and functions

$$h:𝔐_A\times 𝔐_B𝔐_{AB}$$

for $`A,Bn,`$ such that if $`{}_{}{}^{a}b`$ denotes $`h(a,b)b`$ for $`a𝔐_A`$ and $`b𝔐_B`$ with $`AB,`$ then for $`a,a^{}𝔐_A`$ and $`b,b^{}𝔐_B,c𝔐_C`$ and $`i,jn,`$ the following axioms hold:

$$\begin{array}{cc}1)\hfill & \mu _ia=a\text{if}iA,\hfill \\ 2)\hfill & \mu _i\mu _ja=\mu _j\mu _ia,\hfill \\ 3)\hfill & \mu _ih(a,b)=h(\mu _ia,\mu _ib),\hfill \\ 4)\hfill & h(a,b)=h(\mu _ia,b)=h(a,\mu _ib),\text{if}iAB,\hfill \\ 5)\hfill & h(a,a^{})=[a,a^{}],\hfill \\ 6)\hfill & h(a,b)=h(b,a)^1,\hfill \\ 7)\hfill & h(a,b)=1,\text{if }a=1\text{ }\text{or}\text{ }b=1,\hfill \\ 8)\hfill & h(aa^{},b)={}_{}{}^{a}h(a^{},b)h(a,b),\hfill \\ 9)\hfill & h(a,bb^{})=h(a,b){}_{}{}^{b}h(a,b^{}),\hfill \\ 10)\hfill & {}_{}{}^{a}h(b,c)=h({}_{}{}^{a}b,{}_{}{}^{a}c),\text{if }ABC,\hfill \\ 11)\hfill & {}_{}{}^{a}h(h(a^1,b),c){}_{}{}^{c}h(h(c^1,a),b){}_{}{}^{b}h(h(b^1,c),a)=1.\hfill \end{array}$$

A morphism of crossed n-cubes is defined in the obvious way: It is a family of group homomorphisms, for $`An,`$ $`f_A:𝔐_A𝔐_A^{}`$ commuting with the $`\mu _i`$’s and $`h`$’s. We thus obtain a category of crossed $`n`$-cubes denoted by $`𝔯𝔰^𝔫,`$ cf. Ellis and Steiner .
We will concentrate most attention on crossed modules and crossed squares, but will recall some of the general theory.

Examples: (1) For $`n=1,`$ a crossed $`1`$-cube is the same as a crossed module.
(2) For $`n=2,`$ one has a crossed square:

Each $`\mu _i`$ is a crossed module, as is $`\mu _1\mu _2`$. The h-functions give actions and a function

$$h:𝔐_{\{1\}}\times 𝔐_{\{2\}}𝔐_2.$$

The maps $`\mu _2`$ (or $`\mu _1)`$ also define a map of crossed modules. In fact a crossed square can be thought of as a crossed module in the category of crossed modules.
(3) Let G be a simplicial group. Then the following diagram, which will be denoted $`𝔐(𝐆,2),`$

is a crossed square. Here $`NG_1=`$Ker$`d_0^1`$ and $`\overline{NG}_1=`$Ker$`d_1^1`$.

Since $`G_1`$ acts on $`NG_2/_3NG_3,\overline{NG}_1`$ and $`NG_1,`$ there are actions of $`\overline{NG}_1`$ on $`NG_2/_3NG_3`$ and $`NG_1`$ via $`\mu ^{},`$ and $`NG_1`$ acts on $`NG_2/_3NG_3`$ and $`\overline{NG}_1`$ via $`\mu .`$ Both $`\mu `$ and $`\mu ^{}`$ are inclusions, and all actions are given by conjugation. The h-map is

$$\begin{array}{ccc}NG_1\times \overline{NG}_1& & NG_2/_3NG_3\hfill \\ (x,\overline{y})& & h(x,y)=[s_1x,s_1ys_0y^1]_3NG_3.\hfill \end{array}$$

Here $`x`$ and $`y`$ are both in $`NG_1`$ as there exists a bijection between $`NG_1`$ and $`\overline{NG}_1`$, the element $`\overline{y}`$ is the image of $`y`$ under this.

This last example effectively presents a functor

(4) Let $`G`$ be a group with normal subgroups $`N_1,\mathrm{},N_n`$. Let

$$\begin{array}{ccc}𝔐_A=\{N_i:iA\}& \text{and}& 𝔐_{\mathrm{}}=\text{G}\end{array}$$

with $`An.`$ For $`in,`$ $`𝔐_A`$ is a normal subgroup of $`𝔐_{A\{i\}.}`$ Define

$$\mu _i:𝔐_A𝔐_{A\{i\}}$$

to be the inclusion. If $`A,Bn`$, then $`𝔐_{AB}=𝔐_A𝔐_B,`$ let

$$\begin{array}{cccc}h:& 𝔐_A\times 𝔐_B& & 𝔐_{AB}\hfill \\ & (a,b)& & [a,b]\hfill \end{array}$$

as $`[𝔐_A,𝔐_B]𝔐_A𝔐_B,`$ where $`a𝔐_A,b𝔐_B.`$ Then

$$\{𝔐_A:An,\mu _i,h\}$$

is a crossed $`n`$-cube, called the inclusion crossed n-cube given by the normal $`n`$-ad of groups $`(G;N_1,\mathrm{},N_n).`$ The following result is then fairly easily proved, see .

###### Proposition 5.1

Let $`(𝐆;N_1,\mathrm{},N_n)`$ be a simplicial normal $`n`$-ad of subgroups of groups and define for $`An`$

$$𝔐_A=\pi _0(\underset{iA}{}N_i)$$

with homomorphisms $`\mu _i:𝔐_A𝔐_{A\{i\}}`$ and h-maps induced by the corresponding maps in the simplicial inclusion crossed $`n`$-cube, constructed by applying the previous example to each level. Then $`\{𝔐_A:An,\mu _i,h\}`$ is a crossed $`n`$-cube. $`\mathrm{}`$

Up to isomorphism, all crossed $`n`$-cubes arise in this way. In fact any crossed $`n`$-cube can be realised (up to isomorphism) as a $`\pi _0`$ of a simplicial inclusion crossed $`n`$-cube coming from a simplicial normal $`n`$-ad of groups.

In 1993, the second author, , described a functor from the category of simplicial groups to that of crossed $`n`$-cubes of groups. We will summarise its construction.

The functor is constructed using the *décalage* functor studied by Duskin  and Illusie  and is a $`\pi _0`$-image of a functor taking values in a category of simplicial normal $`(n+1)`$-ads. The *décalage* functor will be denoted by $`𝔇𝔢𝔠.`$ Given any simplicial group $`𝐆,`$ $`𝔇𝔢𝔠𝐆`$ is the augmented simplicial group obtained from $`𝐆`$ by forgetting the zeroth face and degeneracy operators at each level and then renumbering the levels (cf. Duskin  or Illusie ). (There are two main forms of the *décalage* functor. The alternative forgets the last face instead of the zeroth one. This second form is used in . Reversing the indexed order of the faces used gives an equivalence between the two theories and allows for the easy translation of proofs between them.) In the convention adopted in this paper, we thus have

$$𝔇𝔢𝔠G_n=G_{n+1},$$

with face operators

$$d_i^{n,Dec}=d_{i+1}^{n+1}$$

and degenerate operators

$$s_i^{n,Dec}=s_{i+1}^{n+1}.$$

The remaining degeneracy $`s_0^{n+1}`$ of $`𝐆`$ yields a contraction of $`𝔇𝔢𝔠^1𝐆`$ as an augmented simplicial group and

$$𝔇𝔢𝔠^1𝐆𝐊(G_0,0),$$

by an explicit natural homotopy equivalence (cf. Duskin ). The zeroth face map will be denoted $`\delta _0:𝔇𝔢𝔠^1𝐆𝐆`$. This is a split epimorphism and has kernel the simplicial group, Ker $`d_0`$ used above. We have $`\pi _0(\text{Ker}\delta )\pi _0(𝔇𝔢𝔠𝐆)`$ is a crossed module and using that

$$\pi _0𝐇=NH_0/NH_1$$

for any simplicial group $`𝐇`$, we get:
Case 1: $`𝐇=𝔇𝔢𝔠𝐆.`$
Then $`NH_0=G_1,`$ $`NH_1=`$Ker$`(d_1^2:G_2G_1)`$ so

$$\begin{array}{ccc}\hfill \pi _0(𝔇𝔢𝔠𝐆)& & G_1/d_2^2(\text{Ker}d_1^2),\hfill \\ & & G_0,\hfill \end{array}$$

since $`G_1`$ Ker$`d_1^1s_0(G_0).`$
Case 2: $`𝐇=`$ Ker$`\delta .`$ Then $`NH_0=`$ Ker$`d_0^1=NG_1,`$ $`NH_1=`$ Ker$`d_0^2`$ Ker$`d_1^2=NG_2`$ so

$$\pi _0(\text{ Ker }\delta )=NG_1/_2NG_2.$$

Iterating the $`𝔇𝔢𝔠`$ construction gives an augmented bisimplicial group

which in expanded form is the total *décalage* of G, (see  or  for details). The maps from $`𝔇𝔢𝔠^i𝐆`$ to $`𝔇𝔢𝔠^{i1}𝐆`$ coming from the $`i`$ first face maps will be labelled $`\delta _0,\mathrm{},\delta _{i1}`$ so that $`\delta _0=d_0,\delta _1=d_1`$ and so on.

For a simplicial group G and a given $`n,`$ we write $`𝔐(𝐆,n)`$ for the crossed $`n`$-cube arising as a functor

$$𝔐(,n):𝔖𝔦𝔪𝔭𝔊𝔯𝔭𝔯𝔰^𝔫.$$

which is given by $`\pi _0(𝔇𝔢𝔠𝐆;\text{Ker}\delta _0,\mathrm{},\text{Ker}\delta _{n1}).`$ The following data explicitly gives this crossed $`n`$-cube of groups, for the details see :

###### Theorem 5.2

If G is a simplicial group, then the crossed $`n`$-cube $`𝔐`$(G,$`n`$) is determined by:

(i) for $`An,`$

$$𝔐(𝐆,n)_A=\frac{_{jA}\text{Ker}d_{j1}^n}{d_{n+1}^{n+1}(\text{Ker}d_0^{n+1}\{_{jA}\text{Ker}d_j^{n+1}\})};$$

(ii) the inclusion

$$\underset{jA}{}\text{Ker}d_{j1}^n\underset{jA\{i\}}{}\text{Ker}d_{j1}^n$$

induces the morphism

$$\mu _i:𝔐(𝐆,n)_A𝔐(𝐆,n)_{A\{i\}};$$

(iii) the functions, for $`A,Bn,`$

$$h:𝔐(𝐆,n)_A\times 𝔐(𝐆,n)_B𝔐(𝐆,n)_{AB}$$

are given by

$$h(\overline{x},\overline{y})=\overline{[x,y]},$$

where an element of $`𝔐(𝐆,n)_A`$ is denoted by $`\overline{x}`$ with $`x_{jA}`$Ker$`d_{j1}^n.`$ $`\mathrm{}`$

In general, we use the ($`n1`$)-skeleton of the total *décalage* to form an $`n`$-cube and thus a simplicial inclusion crossed $`n`$-cube of kernels. Continuing this $`n`$-times gives the simplicial inclusion crossed $`n`$-cube corresponding to the simplicial normal $`(n+1)`$-ad,

$$(𝐆,n)=(𝔇𝔢𝔠^n𝐆;\text{Ker}\delta _0,\mathrm{},\text{Ker}\delta _{n1}),$$

and its associated crossed $`n`$-cube is

$$\pi _0((𝐆,n))=𝔐(𝐆,n).$$

The results of  now follow by direct calculation on examining the construction of $`\pi _0`$ as the zeroth homology of the Moore complex of each term in the inclusion crossed $`n`$-cube, $`(𝐆,n).`$

Expanding this out for low values of $`n`$ gives:
1) For $`n=0`$,

$$\begin{array}{ccc}\hfill 𝔐(𝐆,0)& =& G_0/d_1(\text{Ker}d_0,)\hfill \\ & & \pi _0(𝐆),\hfill \\ & =& H_0(𝐆).\hfill \end{array}$$

2) For $`n=1`$, $`𝔐(𝐆,1)`$ is the crossed module

$$\mu _1:\text{Ker}d_0^1/d_2^2(NG_2)G_1/d_2^2(\text{Ker}d_0^2).$$

Since $`d_2^2(NG_2)=`$ \[Ker$`d_1^1,`$ Ker$`d_0^1],`$ this gives

$$\mu :NG_1/[\text{Ker}d_1^1,\text{Ker}d_0^1]G_0.$$

$$𝔐(𝐆,1)\left(\begin{array}{ccc}NG_1/_2NG_2G_0& & \end{array}\right).$$

3) For $`n=2`$, $`𝔐(𝐆,2)`$ is

As shown in , this is isomorphic to

that is

$$𝔐(𝐆,2)\left(\text{}\right).$$

Here the $`h`$-map is

$$h:\text{Ker}d_0^1\times \text{Ker}d_1^1NG_2/d_3^3(NG_3)$$

given by $`h(x,y)=[s_1x,s_1ys_0y^1]_3NG_3.`$ Note if we consider the above crossed square as a vertical morphism of crossed modules we can take its kernel and cokernel within the category of crossed modules. In the above, the morphisms in the top left hand corner are induced from $`d_2`$ so

$$\text{Ker}(\mu _1:\frac{NG_2}{_3NG_3}\text{Ker}d_1)=\frac{NG_2\text{Ker}d_2}{_3NG_3}\pi _2(𝐆)$$

whilst the other map labelled $`\mu _1`$ is an inclusion so has trivial kernel. Hence the kernel of this morphism of crossed modules is

$$\pi _2(𝐆)1.$$

The image of $`\mu _2`$ is normal in both the simplicial groups on the bottom line and as $`\text{Ker}d_0=NG_1`$ with the corresponding $`\text{Im}\mu _1`$ being $`d_2NG_2,`$ the cokernel is $`NG_1/_2NG_2,`$ whilst $`G_1/\text{Ker}d_0G_0,`$ i.e., the cokernel of $`\mu _1`$ is $`𝔐(𝐆,1).`$

In fact of course $`\mu _1`$ is not only a morphism of crossed modules, it is a crossed module. This means that $`\pi _2(𝐆)1`$ is in some sense a $`𝔐(𝐆,1)`$-module and that $`𝔐(𝐆,2)`$ can be thought of as a crossed extension of $`𝔐(𝐆,1)`$ by $`\pi _2(𝐆).`$

## 6 2-crossed modules from crossed squares

D. Conduché’s unpublished work shows that there exists an equivalence (up to homotopy) between the category of crossed squares of groups and that of 2-crossed modules of groups. Loday defined a mapping complex of crossed squares by: if

$$=\text{}$$

is a crossed square, then its mapping complex is

where $`_2l=(\lambda l^1,\lambda ^{}l)`$ and $`_1(m,n)=\mu (m)\nu (n).`$

Conduché showed that this mapping complex is always a 2-crossed complex, representing the same 3-type as the original crossed square. Why?

### 6.1 From crossed squares to bisimplicial groups

Recall that from a crossed module $`=(M\stackrel{\mu }{}P)`$, we can build a simplicial group whose Moore complex is trivial in dimensions 2 and above. This is the nerve of the associated cat1-group. (Because a cat1-group is an internal groupoid in $`𝔊𝔯𝔭𝔰`$, we can form the nerve of its category structure internally within $`𝔊𝔯𝔭𝔰`$ and hence obtain a simplicial group.) We need an explicit description of this, elementwise: The simplicial group $`Ner()`$ has

$$Ner()_0=P$$

$$Ner()_n=M(\mathrm{}(MP)\mathrm{}),$$

with $`n`$ semidirect factors of $`M`$ (see Conduché, , Carrasco and Cegarra, , or our own papers  for more on semidirect decompositions and simplicial groups). If $`(m,p)Ner()_1`$, then

$$d_0^1(m,p)=\mu (m)p$$

$$d_1^1(m,p)=p$$

and

$$s_0^0(p)=(1,p).$$

If $`(m_2,m_1,p)Ner()_2`$, then

$$d_0^2(m_2,m_1,p)=(m_2,\mu (m_1)p)$$

$$d_1^2(m_2,m_1,p)=(m_2m_1,p)$$

$$d_1^2(m_2,m_1,p)=(m_1,p)$$

$$s_0^1(m,p)=(m,1,p)$$

$$s_1^1(m,p)=(1,m,p)$$

and the obvious pattern continues to higher dimensions.

Now going to crossed squares, let

$$=\text{}$$

be a crossed square. The construction we will need is the bisimplicial nerve of $``$ or rather of the associated cat2-group. That will be an internal double groupoid in $`𝔊𝔯𝔭𝔰`$ and so when we take the nerves in the two directions, we will get a bisimplicial group. Although again this is known, we will want explicit descriptions of elements etc. for explicit calculations of actions, pairings, etc. later on, so will give quite a lot of detail, even when it is fairly simple to check.

Considering the crossed square $``$ as a morphism /crossed module from $`(LN)`$ to $`(MP)`$, we apply the above nerve construction to its domain and codomain to get a crossed module of simplicial groups. In low dimensions:

To check, for instance, that $`(\lambda ,\nu )`$ is a crossed module, you need to use the $`h`$-map of $``$, as follows: First the action of $`(m,p)`$ on $`(l,n)`$ is

$${}_{}{}^{(m,p)}(l,n)={}_{}{}^{m}({}_{}{}^{p}l,{}_{}{}^{p}n)=({}_{}{}^{\mu (m)p}lh(m,{}_{}{}^{p}n),{}_{}{}^{p}n).$$

Now writing $`=(\lambda ,\nu )`$,

$$({}_{}{}^{(m,p)}(l,n))=(\lambda ({}_{}{}^{\mu (m)p}l).\lambda (h(m,{}_{}{}^{p}n)),\nu ({}_{}{}^{p}n),$$

but $`\lambda (h(m,{}_{}{}^{p}n))=m.{}_{}{}^{\nu {}_{}{}^{p}n}m_{}^{1}`$ and so a routine calculation shows that this expands to

$$(m,p)(\lambda l,\nu n)({}_{}{}^{p^1}m_{}^{1},p^1),$$

i.e. to $`{}_{}{}^{(m,p)}\lambda (l,n)`$, so $``$ satisfies the first crossed module axiom. We leave the second crossed module axiom (Peiffer identity) to the diligent reader. It uses $`h(\lambda l,n^{})=l{}_{}{}^{n^{}}l_{}^{1}`$. The description of the ‘vertical’ face and degeneracies is as before.

Next we start building the nerve in the second direction. Writing $`𝒳`$ for the resulting simplicial group, we get:

$`𝒳_{0,0}`$ $`=`$ $`P`$
$`𝒳_{0,1}`$ $`=`$ $`MP`$
and in general
$`𝒳_{0,q}`$ $`=`$ $`M\mathrm{}MP=M^{(q)}P\text{ }`$
with $`q`$-factors of $`M`$, (note
the shorthand version).
$`\text{Similarly}\text{ }\text{ }𝒳_{p,0}`$ $`=`$ $`N\mathrm{}NP=N^{(p)}P`$
with $`p`$-factors of $`N`$. In general $`𝒳_{p,q}`$ can be written :

$$𝒳_{p,q}=(L^{(q)}N)^{(p)}(M^{(q)}P).$$

Remark:

This initially looks asymmetric but in fact is not. The result of forming the horizontal nerve first then the vertical one would give an isomorphic bisimplicial group. This is easy to show categorically, but is tedious to show elementwise as it makes repeated use of the interchange /$`h`$-map structure within $``$.

### 6.2 From bisimplicial groups to simplicial groups.

There are two useful ways of passing from bisimplicial groups to simplicial groups. One is the diagonal, the other, due to Artin and Mazur, , is the ‘codiagonal’ and, for us, is more useful. In the bisimplicial group $`𝒳`$, the corresponding Moore bicomplex has relatively few non-zero terms. In fact, $`N(𝒳)_{p,q}`$ will be zero if $`p`$ or $`q`$ is bigger than 1. If you take the diagonal and try to apply the Moore complex functor, the task looks horrendous. Although, in fact, this Moore complex has length 2, the individual terms are quite large with a complicated expression for the differential. The diagonal gets complicated because its $`p`$-simplexes are the $`(p,p)`$-simplices of the original bisimplicial group and so seem to correspond to $`2p`$-dimensional data. (In fact they need a list of $`(p+1)^2`$-elements to describe them.)

In the Artin-Mazur construction, if $`𝒳_,`$ is a bisimplicial group, we first form for each $`n`$, a group

$$𝒳_{(n)}=\underset{p+q=n}{}𝒳_{p,q}.$$

Within this $`𝒳_{(n)}`$, we pick out a subgroup, $`(𝒳)_n`$ as follows: Let $`\underset{¯}{x}=(x_0,\mathrm{},x_n)𝒳_{(n)}`$ with $`x_p𝒳_{p,np}`$. Then $`\underset{¯}{x}(𝒳)_n`$ if and only if for each $`p=0,\mathrm{},n1`$

$$d_0^vx_p=d_{p+1}^hx_{p+1}.$$

This mysterious formula can be best remembered by looking at the case $`n=2`$ and the diagram

$`d_0^vx_0=d_1^hx_1`$
$`d_0^vx_1=d_2^hx_2`$
where we have expanded the notation $`x_p`$ to $`x_{p,np}`$ to make the changes in dimension clearer (we hope). Similar subdivided simplex diagrams can be seen to give the formulae in higher dimensions, although above $`n=3`$, they cannot be so simply drawn. The link between this and the ordinal subdivision of the paper, , by Ehlers and the second author will be explored and exploited later.

The face and degeneracy maps of $`(𝒳)`$ are built up in an obvious way from this formula:

$$d_j=d_j^{}:(𝒳)_n(𝒳)_{n1},$$

for $`\underset{¯}{x}=(x_0,\mathrm{},x_n),`$ with $`d_0^vx_p=d_{p+1}^hx_{p+1},`$ $`p=0,\mathrm{},n1`$, then for $`0<j<n`$,
$`d_j^{}(\underset{¯}{x}):=(d_j^vx_0,d_{j1}^vx_1,\mathrm{},d_1^vx_{j1},d_j^hx_{j+1},\mathrm{},d_j^hx_n)`$;
$`d_0^{}(\underset{¯}{x}):=(d_0^hx_1,d_0^hx_2,\mathrm{},d_0^hx_n)`$;
and
$`d_n^{}(\underset{¯}{x}):=(d_n^vx_0,d_{n1}^vx_1,\mathrm{},d_1^vx_{n1}),`$
whilst $`s_i^{}(\underset{¯}{x}):=(s_i^vx_0,s_{i1}^vx_1,\mathrm{},s_0^vx_i,s_i^hx_i,\mathrm{},s_i^hx_n)`$ for $`0in`$.

Remark:

Of course the formulae for $`d_0`$ and $`d_n`$ can be considered as being special cases of that for $`d_j`$.

Suppose now given a bisimplicial group, $`𝒳`$, such that for any fixed $`p`$, the Moore complex of $`𝒳_{p,}`$ is of length at most 1 (so is a crossed module) and that for any fixed $`q`$, similarly $`N(𝒳_{,q})`$ has length at most 1. Then we claim that $`N((𝒳))`$ has length $`2`$.

We examine an element $`\underset{¯}{x}N((𝒳))_n`$ for $`n3`$. Since $`d_0(\underset{¯}{x})=1`$, we have

$$x_pKerd_0^h\text{ for all }p>0.$$

Now for each $`0<j<n`$, $`d_j(\underset{¯}{x})=1`$, so

$$d_j^vx_0=d_{j1}^vx_1=\mathrm{}d_1^vx_{j1}=1,$$

whilst

$$d_j^hx_{j+1}=\mathrm{}=d_j^hx_n=1.$$

Looking at $`x_n`$, $`d_j^hx_n=1`$ for $`j=0,\mathrm{},n1`$, i.e. $`x_nN(𝒳_{,0})_n`$. If $`n2`$, then this group is trivial, so $`x_n=1`$, but $`d_n^hx_n=d_0^vx_{n1}`$, so $`d_0^vx_{n1}=1`$ as well. Turning to $`x_{n1}𝒳_{n1,1}`$, we have $`d_0^hx_{n1}=1`$. From $`d_j^{}`$, we have $`d_j^hx_{n1}=1`$ for $`j=1,\mathrm{},n2`$, i.e. $`x_{n1}N(𝒳_{,1})_{n1}`$. As $`n3`$, $`n12`$, so $`N(𝒳_{,1})_{n1}=1`$, i.e. $`x_{n1}=1`$ and hence $`d_0^v(x_{n1})=1`$. Continuing like this, we get $`x_k=1`$ for all $`k2`$: for each index, we already know

$$d_j^hx_k=1\text{ for }jk1,$$

i.e. $`x_kN(𝒳_{,nk})_k=1`$ if $`k2`$. This leaves us with just $`x_0`$ and $`x_1`$ to examine:

$$d_0^vx_1=d_2^hx_2=1,$$

whilst $`d_j^vx_1=1`$ (from $`d_{j+1}^{}\underset{¯}{x}=1`$ so again $`x_1N(𝒳_{1,})_{n1}`$ which is trivial as $`n12`$, i.e. $`x_1=1`$, so $`d_0^vx_0=1`$ as well. Finally $`d_j^vx_0=1`$ for all $`0<j<n`$ (from $`d_0^{}\underset{¯}{x}=1`$), so $`x_0N(𝒳_{0,})_n=1`$.

We have thus proved :

###### Proposition 6.1

If $`𝒳_,`$ is a bisimplicial group such that for any $`p`$, $`N(𝒳_{p,})_q=1`$ for $`q2`$ and for any $`q`$, $`N(𝒳_{,q})_p=1`$ for $`p2`$, then $`N((𝒳)_n=1`$ for $`n3`$. $`\mathrm{}`$

We have in fact proved a bit more. If $`𝒳_,`$ satisfies the conditions of the proposition and $`\underset{¯}{x}=(x_0,x_1,x_2)N((𝒳))_2`$, then $`x_2=1`$ since $`x_2N(𝒳_{,0})_2=1`$. Of course $`N((𝒳))_n=1`$ for $`n3`$ implies that $`N((𝒳))`$ is a 2-crossed module. We will examine this in some detail.

Remark:

The above proposition suggests two questions. Firstly if we weaken the condition that each direction gives a crossed module as it Moore complex to that it gives a crossed *complex*, is it true that $`N((𝒳))`$ is a 2-crossed complex? Also, is there a generalisation to higher order multisimplicial groups? We will later on show that the answer to the second one is positive.

For the moment we will look in more detail at the case when $`𝒳`$ is the binerve of a crossed square.

### 6.3 The 2-crossed module structure of $`N((𝒳()))`$.

As before, we let $``$ be a crossed square and will write $`𝒳()`$ for $`Ner^h(Ner^v())`$, i.e. for the binerve of $``$. For convenience we will often write $`G`$ instead of $`(𝒳())`$.

We know $`N(G)_n=1`$ if $`n3`$. It is also clear that $`G_0=P`$, so $`N(G)_0=P`$ as well. We thus only need to work out $`N(G)_k`$ for $`k=1`$ and $`2`$, together with explicit formulae for the boundary maps and the Peiffer pairing from $`N(G)_1\times N(G)_1`$ to $`N(G)_2`$.

Suppose $`xG_1`$, then $`\underset{¯}{x}=(x_0,x_1)`$ with $`x_0_{0,1}`$, $`x_1_{1,0}`$. We have

$$_{0,1}=MP,_{1,0}=NP,$$

so $`x_0=(m,p)`$, $`x_1=(n,p^{})`$ and, since $`\underset{¯}{x}𝒳())_1`$

$$d_0^v(m,p)=\mu (m)p=p^{}=d_1^h(n,p^{}),$$

i.e. $`p^{}`$ is determined by $`(m,p)`$. The assignment

$$\underset{¯}{x}=((m,p),(n,\mu (m)p))(n,m,p)$$

is easily checked to give an isomorphism

$$G_1\stackrel{}{}N(MP),$$

where $`M`$ acts on $`N`$ via $`P`$, $`{}_{}{}^{m}n={}_{}{}^{\mu (m)}n.`$ Identifying $`G_1`$ with $`N(MP)`$, $`d_0`$ and $`d_1`$ have the descriptions:

$`d_0(n,m,p)`$ $`=`$ $`\nu (n)\mu (m)p`$
$`d_1(n,m,p)`$ $`=`$ $`p.`$
Thus $`\underset{¯}{x}N(G_1)`$ if and only if $`p=\mu (m)^1\nu (n)^1`$ and it is again easily verified that

$$NG_1MN,$$

where the isomorphism is given by

$$(n^1,m^1,\mu (m)\nu (n))(n,m).$$

We note that via this isomorphism, we get

$$_1:NG_1NG_0$$

is given by

$$_1(n,m)=\mu (m)\nu (n).$$

This does look strange (inverses do not work well with conditions for homomorphisms), but does work as is easily checked.

Turning to $`NG_2`$, $`\underset{¯}{x}𝒳_2`$ will have the form $`(x_0,x_1,x_2)`$ with

$`x_0`$ $`=`$ $`(m_2,m_1,p)M(MP)`$
$`x_1`$ $`=`$ $`(l,n,m,p^{})(LN)(MP)`$
$`x_2`$ $`=`$ $`(n_2,n_1,p^{\prime \prime })N(NP)`$
The equations $`d_0^vx_0=d_1^hx_1`$ and $`d_0^vx_1=d_2^hx_2`$ give relations between the individual coordinates implying that $`m_2=m`$, $`p^{}=\mu (m_1)p`$, $`\lambda ^{}(l)n=n_1`$ and $`\mu (m)p^{}=p^{\prime \prime }`$. (This is best seen on a diagram as above, but such a diagram is best left to the reader to draw!) Now suppose $`\underset{¯}{x}N(𝒳)_2`$, then in addition one gets $`p=1`$, $`m_2m_1=1`$, etc. and it follows that all the ‘coordinates’ depend only on $`l`$. In fact,

$$\underset{¯}{x}=((\lambda (l)^1,(\lambda (l),1)),((l,\lambda ^{}(l)^1),(\lambda (l)^1,\mu \lambda (l))),(1,(1,1)))$$

with $`d_2(\underset{¯}{x})=((\lambda (l),1),(\lambda ^{}(l),\mu \lambda (l)))`$, which identifies to $`(\lambda (l)^1,\lambda ^{}(l))MN`$. Thus the normal chain complex $`NG`$ is isomorphic to

with

$`_2(l)`$ $`=`$ $`((\lambda ^{}(l)^1,\lambda (l)))`$
$`_1(l)`$ $`=`$ $`\mu (m)^1\nu (n)^1.`$
To complete the description, we should really specify the Peiffer pairing

$$\{,\}:NG_1\times NG_1NG_2.$$

We can use the formula given in our earlier paper, , derived from work of Conduché:

$$\{\underset{¯}{x},\underset{¯}{y}\}=s_0(\underset{¯}{x})s_1(\underset{¯}{y})s_0(\underset{¯}{x})^1s_1(\underset{¯}{x}\underset{¯}{y}^1\underset{¯}{x}^1)$$

Since $`s_0(\underset{¯}{x})=s_0(x_0,x_1)=(s_0^vx_0,s_0^hx_0,s_0^hx_1)`$ and $`s_1(\underset{¯}{x})=s_1(x_0,x_1)=(s_1^vx_0,s_0^vx_1,s_1^hx_1)`$, we can get an explicit desciption of $`\{\underset{¯}{x},\underset{¯}{y}\}`$. In fact, that description is not that useful. Its exact form is dependent on the order of multiplication used. These forms are equivalent via the relations for expanding $`h(m.m^{},n)`$ in terms of $`h(m,n)`$ and $`h(m^{},n)`$, but at the risk of lengthening the expression. These different forms are fairly complicated and so have been omitted here, but can be retrieved from the original formula.

Remarks
(i) In Conduché’s original letter, he gives a much simpler form, namely $`h(m,nbn^1)`$. Our efforts to reduce the above to something as simple as this have so far failed! This is almost certainly due to the change in convention on the Moore complex, but we have not managed fully to understand the reason for the greater complication. Conduché’s elegant form *does* work as is very easily checked. What is not clear is its relationship with the ‘canonical’ form coming from the Peiffer pairings.

(ii) The above shows a subtle difficulty encountered when working with elements in models for homotopy $`n`$-types for $`n>1`$. With (free) groups, we are used to handling normal forms of elements, but even with free crossed modules, the Peiffer identity makes calculating with representatives of elements much more difficult. This emphasises the need for a higher order version of both combinatorial and computational group theory, adapting the methods of the classical case to these higher dimensional situations. Some success has been achieved in this area by Alp and Wensley, , and by Ellis, .

### 6.4 Squared complexes and 2-crossed complexes

In 1993, Ellis defined the notion of a squared complex, . A crossed complex combines a crossed module at its ‘base’ with a continuation by a chain complex of modules further up. They thus have good descriptive power, being able to model 2-types via their crossed module part and also a certain amount of higher homotopy information, typically thought of as generalising chains on the universal cover of a space.

Squared complexes are one of the possible notions that generalise crossed complexes to include the so-called quadratic information available in a 3-type. Other versions include double crossed complexes (cf. Tonks, ), 2-crossed complexes (cf. the authors, ) and quadratic complexes, (cf. Baues, ). We will need to examine 2-crossed complexes in detail later.

A squared complex consists of a diagram of group homomorphisms

together with actions of $`P`$ on $`L,N,M`$ and $`C_i`$ for $`i3,`$ and a function $`h:M\times NL.`$ The following axioms need to be satisfied.
(i) The square $`\left(\text{}\right)`$ is a crossed square;
(ii) The group $`C_n`$ is abelian for $`n3`$
(iii) The boundary homomorphisms satisfy $`_n_{n+1}=1`$ for $`n3,`$ and $`_3(C_3)`$ lies in the intersection $`\text{ker}\lambda \text{ker}\lambda ^{};`$
(iv) The action of $`P`$ on $`C_n`$ for $`n3`$ is such that $`\mu M`$ and $`\mu ^{}N`$ act trivially. Thus each $`C_n`$ is a $`\pi _0`$-module with $`\pi _0=P/\mu M\mu ^{}N.`$
(v) The homomorphisms $`_n`$ are $`\pi _0`$-module homomorphisms for $`n3.`$

This last condition does make sense since the axioms for crossed squares imply that $`\text{ker}\mu ^{}\text{ker}\mu `$ is a $`\pi _0`$-module.

A morphism of squared complexes

$$\mathrm{\Phi }:(C_{},\left(\text{}\right))(C_{}^{},\left(\text{}\right))$$

consists of a morphism of crossed squares $`(\mathrm{\Phi }_L,\mathrm{\Phi }_N,\mathrm{\Phi }_M,\mathrm{\Phi }_P)`$, together with a family of equivariant homomorphisms $`\mathrm{\Phi }_n`$ for $`n3`$ satisfying $`\mathrm{\Phi }_L_3=_{}^{}{}_{3}{}^{}\mathrm{\Phi }_L`$ and $`\mathrm{\Phi }_{n1}_n=_{}^{}{}_{n}{}^{}\mathrm{\Phi }_n`$ for $`n4.`$ There is clearly a category $`𝔖𝔮𝔬𝔪𝔭`$ of squared complexes. This exists in both group and groupoid based versions.

A squared complex is thus a crossed square with a ‘tail’ attached. The same process can be applied to 2-crossed modules and leads to the notion of a 2-crossed complex, .

A 2-crossed complex of group(oid)s is a sequence of group(oid)s

$$C:\mathrm{}C_n\stackrel{_n}{}C_{n1}\mathrm{}C_2\stackrel{_2}{}C_1\stackrel{_1}{}C_0$$

in which
(i) $`C_n`$ is abelian for $`n3`$;
(ii) $`C_0`$ acts on $`C_n`$, $`n1`$, the action of $`C_1`$ being trivial on $`C_n`$ for $`n3`$;
(iii) each $`_n`$ is a $`C_0`$-group(oid) homomorphism and $`_i_{i+1}=1`$ for all $`i1`$;
and
(iv) $`C_2\stackrel{_2}{}C_1\stackrel{_1}{}C_0`$ is a 2-crossed module.

The following is an easy consequence of our earlier work.

###### Theorem 6.2

If

is a squared complex then

$$\mathrm{}C_n\stackrel{_n}{}C_{n1}\mathrm{}C_3LNMP$$

is a 2-crossed complex. $`\mathrm{}`$

## 7 Homotopy groups

It is folklore that any bisimplicial group $`𝒳_,`$, the diagonal, $`diag(𝒳)`$ and the codiagonal $`𝒳`$ have the same homotopy type. The original work of Loday,  and Conduché, , together with the second author’s  all used the diagonal so showing that the homotopy groups of $`diag(𝒳())`$ were those of $`G`$ when $`=𝔐(G,2)`$. The use of the mapping complex construction by Loday, again in , also gave the same homotopy groups. Here we will briefly look at the homotopy groups of $`(𝒳(𝔐(G,2)))`$ directly.

The crossed square $`𝔐(G,2)`$ as we recalled earlier has form

$$𝔐(𝐆,2)\left(\text{}\right).$$

The horizontal kernel is $`\pi _2(G)1`$ and the cokernel “is” $`𝔐(G,1)`$, i.e. isomorphic to

$$\begin{array}{ccc}NG_1/_2NG_2G_0,& & \end{array}$$

which, in turn, has kernel $`\pi _1(G)`$ and cokernel $`\pi _0G)`$ .

The corresponding simplicial group $`(𝒳(𝔐(G,2)))`$ has Moore complex

$$NG_2/_3(NG_3)\stackrel{(\mu _2^1,\mu _1)}{}\text{ Ker }d_0\text{ Ker }d_1\stackrel{\mu _1\mu _2}{}G_1.$$

The homomorphisms $`\mu _2`$ and $`\mu _1`$ from $`NG_2/_3(NG_3)`$ in the crossed square are both induced from $`d_2`$, so it is immediate that $`\text{Ker}(\mu _2^1,\mu _1)`$ is $`\pi _2(G)`$. The other two $`\mu `$s (bottom and right of the square) are inclusions. Since $`G_0G_1/\mu _2(\text{Ker}d_1)`$, we again easily check that $`\pi _0`$ of the complex, i.e. $`G_1/Im(\mu _1\mu _2)`$, is $`\pi _0(G)`$.

Finally

$$(m,n)\text{Ker}(\mu _1\mu _2)$$

if and only if $`\mu _1(m)=\mu _2(n)^1`$, but as $`\mu _1`$ and $`\mu _2`$ are inclusions, this amounts to $`\text{Ker}(\mu _1\mu _2)`$ being

$$\{(m,m^1):m\text{Ker}d_0\text{Ker}d_1\}.$$

Then the image of $`(\mu _2^1,\mu _1)`$ identifies as

$$\{(m,m^1):m_2(NG_2)\}$$

and again a routine calculation shows that

$$\frac{\text{Ker}(\mu _1\mu _2)}{\text{Im}(\mu _2^1,\mu _1)}\pi _1(G),$$

as expected.

These calculations do not involve the Peiffer lifting so are not conclusive about homotopy type, however a neat argument noted by Conduché shows that there is an (obvious) epimorphism

with acyclic kernel. This still does not quite clinch the argument, since it would be better to check that there was an acyclic fibration

$$(𝒳(𝔐(G,2)))t_{2]}G$$

where $`t_{2]}G`$ here denotes the homotopy truncation of $`G`$ (essentially its 2-coskeleton). However we have not attempted to give this here.

## 8 Higher dimensions

Loday’s mapping complex was defined for catn-groups (see ) and results of Bullejos, Cegarra and Duskin,  suggest that a similar multiple codiagonal would give his mapping complex. This raises the question of what would be the result on taking a crossed $`n`$-cube $``$ and forming its $`n`$-fold nerve $`Ner^{(n)}`$, which will be an $`n`$-simplicial group (just generalise the construction of section 6.1). Again Bullejos, Cegarra and Duskin use an inductive argument to derive a result that would suggest the multicodiagonal of $`Ner^{(n)}`$ should have Moore complex of length $`n`$.

We first note that the proof of Proposition 6.1 shows the following:

###### Proposition 8.1

If $`𝒳_,`$ is a bisimplicial group such that for any $`p`$, $`N(𝒳_{p,})_q=1`$ for $`q2`$, whilst for any $`q`$, $`N(𝒳_{,q})_p=1`$ for $`pm`$, then

$$N(𝒳)_n=1\text{ for }nm+1.$$

$`\mathrm{}`$

We next need a categorical description of the multidiagonal:

Let $`or:\mathrm{\Delta }\times \mathrm{\Delta }\mathrm{\Delta }`$ be the ordinal sum functor, then for a bisimplicial group $`𝒳`$, it is well known that $`𝒳`$ has a description as a coend

$$(𝒳)_n=^{[p],[q]}\mathrm{\Delta }([n],[p]or[q])\times 𝒳_{p,q},$$

(cf. for example, Cordier-Porter, ). A corresponding codiagonal for a $`m`$-fold simplicial group $`𝒳_\underset{¯}{}`$, $`\underset{¯}{}`$ an $`m`$-fold index, is

$$(^{(m)}𝒳)_n=^{\underset{¯}{p}}\mathrm{\Delta }([n],or\underset{¯}{p})\times 𝒳_{\underset{¯}{p}},$$

where by abuse of notation, we indicate by

$$or:\mathrm{\Delta }^{\times m}\mathrm{\Delta },$$

the $`m`$-fold ordinal sum, $`\underset{¯}{p}=([p_1],\mathrm{},[p_m])`$ an $`m`$-fold index and have used as a shorthand

$$or\underset{¯}{p}=[p_1]or\mathrm{}or[p_m],$$

which causes no ambiguity as $`or`$ is associative.

As $`or\underset{¯}{p}=([p_1]or\mathrm{}or[p_{m1}])or[p_m]=:(or\underset{¯}{p^{}})or[p_m]`$

$$(^{(m)}𝒳)_n=^{\underset{¯}{p^{}}}^{[p_m]}\mathrm{\Delta }([n],(or\underset{¯}{p^{}})or[p_m])\times 𝒳_{\underset{¯}{p^{},p_m}},$$

but then ‘integrating’ over all $`\underset{¯}{p^{}}`$ for each $`n`$ produces a new description of $`(^{(m)}𝒳)`$ as $`(^{(m1)}𝒳_{\underset{¯}{},\mathrm{?}})`$ i.e. an iterative description. (The proof uses the fact that any mapping from $`[n]`$ to $`(or\underset{¯}{p^{}})or[p_m]`$ effectively partitions $`[n]`$ into an initial segment mapping to $`or\underset{¯}{p^{}}`$ and a second part mapping to $`[p_m]`$. Fixing the latter part, we form the coend with $`[n]`$ replaced by the first segment of the partition.) Now assume that the $`m`$-simplicial group $`𝒳_\underset{¯}{}`$ is obtained as the $`m`$-fold nerve of a crossed $`m`$-cube (or catm-group), then applying the above proposition repeatedly we obtain:

###### Theorem 8.2

If $`𝔐`$ is a crossed $`m`$-cube with $`m`$-fold nerve, the $`m`$-simplicial group, $`𝒳(𝔐)`$, then

$$N(𝒳(𝔐))_n=1\text{for}nm+1$$

$`\mathrm{}`$

There is a ‘complex’ form of this result as well. If one takes the obvious notion of $`m`$-cube complex, generalising the squared complexes considered above, then Theorem 6.2 generalises without bother to give a notion of $`m`$-crossed complex and a construction that generalises $`𝒳`$ above. The Moore complex that one gets is related to complexes considered by Duskin and Nan Tie as well as the hypercrossed complexes of .

The structural maps of such hypercrossed complexes and the related Peiffer pairings considered in earlier papers of the series could be given explicit algebraic formulae in terms of the $`h`$-maps in the $`m`$-cube complex, but the problem of the complexity of these formulae raises doubts as to their usefulness.

A. Mutlu T. Porter
Department of Mathematics School of Informatics
Faculty of Science University of Wales Bangor,
University of Celal Bayar Gwynedd, LL57 1UT, UK.
Manisa, Turkey e-Mail: t.porter@bangor.ac.uk
e-Mail: amutlu@spil.bayar.edu.tr


text:
# The underlying digraphs of a coined quantum random walk

## 1. Introduction

In this paper, we give a characterization of the line digraph of a regular digraph. We make use of the characterization, to show that the underlying digraph of a coined quantum random walk is a line digraph.

The structure of the paper is the following. In Section 2, we recall the definition of line digraph and survey some properties. In Section 3, we give the characterization. In Section 4, we consider coined quantum random walks and remark the connection between these objects and line digraphs. Finally, we remark the connection between line digraphs and in-split graphs as defined in symbolic dynamics. The reader familiar with the general properties of line digraphs can skip Section 2.

## 2. Line digraphs

### 2.1. Definition

The notion of line digraph has been introduced by Harary and Nornam in 1960 \[HN60\]. A classic survey on line graphs and digraphs is \[HB78\]; a recent one is \[P95\]. Line digraphs are used in the design and analysis of interconnection networks (see *e.g.* \[FYA84\]) and as a tool in algorithms for DIRECTED MAX-CUT \[CE90\], certain poset problems \[Sy84\], and special cases of TRAVELLING SALESMAN \[GKWS98\].

A *directed graph*, for short *digraph*, consists of a non-empty finite set of elements called *vertices* and a finite set of ordered pairs of vertices called *arcs*. Let us denote by $`D=(V,A)`$ a digraph with vertex-set $`V\left(D\right)`$ and arc-set $`A\left(D\right)`$. In an arc $`(v_i,v_j)`$, $`v_i`$ and $`v_j`$ are called *end-vertices* of $`(v_i,v_j)`$; $`v_i`$ *tail* and $`v_j`$ *head* of $`(v_i,v_j)`$. A digraph $`D`$ is an *empty-graph* if $`A\left(D\right)`$ is the empty-set.

###### Definition 1 (Line digraph).

The *line digraph* of a digraph $`D`$ is denoted by $`\stackrel{}{L}D`$ and defined as follows: the vertex set of $`\stackrel{}{L}D`$ is $`A\left(D\right)`$ and, for every $`v_h,v_i,v_j,v_kV\left(D\right)`$, $`(v_h,v_i),(v_j,v_k)A\left(\stackrel{}{L}D\right)`$ if and only if $`v_i=v_j`$. The $`k`$*-iterated line digraph* is recursively defined by

$$\stackrel{}{L}^kD=\stackrel{}{L}^{k1}\stackrel{}{L}D.$$

Now we need some standard terminology.

A *dipath* is a non-empty digraph $`D`$, where

| $`V\left(D\right)=\{v_0,v_1,\mathrm{},v_k\},`$ |  | $`A\left(D\right)=\{(v_0,v_1),(v_1,v_2),\mathrm{},(v_{k1},v_k)\},`$ |
| --- | --- | --- |

and, for every $`v_i,v_jV\left(D\right)`$, $`v_iv_j`$. A dipath is called *dicycle* if $`v_0=v_k`$. A $`k`$-*dipath* ($`k`$-*dicycle*), denoted by $`\stackrel{}{P}_n`$ ($`\stackrel{}{C}_n`$), is a dipath (dicycle) on $`n`$ vertices. The undirected analogues of a dipath and a dicycle are called *path* and *cycle*, respectively.

A digraph $`H`$ is a s*ubdigraph* of a digraph $`D`$ if $`V\left(H\right)V\left(D\right)`$, $`A\left(H\right)A\left(D\right)`$ and every arc in $`A\left(H\right)`$ has both end-vertices in $`V\left(H\right)`$. If $`V\left(H\right)=V\left(D\right)`$, $`H`$ is said to be a *spanning subdigraph* of $`D`$. If every arc of $`A\left(D\right)`$ with both end-vertices in $`V\left(H\right)`$ is in $`A\left(H\right)`$, we say that $`H`$ is *induced* by the set $`X=V\left(H\right)`$ and $`H`$ is an *induced* subdigraph of $`D`$.

This is an obvious but important remark: the set of vertices $`V\left(\stackrel{}{L}^kD\right)`$ can be seen as the set of the $`k`$-dipaths in $`D`$.

### 2.2. General properties

The theorems stated here are well-known; the proofs can be found in \[HB78\].

For every $`SV\left(D\right)`$, let

$$N_D^{}\left(S\right)=\{v_i:(v_i,v_j)A\left(D\right),v_jS\}$$

and

$$N_D^+\left(S\right)=\{v_j:(v_i,v_j)A\left(D\right),v_iS\}$$

be the *in-neighbourhood* and the *out-neighbourhood* of $`S`$, respectively. If the context is not equivoque we then write $`N^{}\left(S\right)`$ ($`N^+\left(S\right)`$). The *in-degree* of $`S`$ is $`d^{}\left(S\right)=\left|N^{}\left(S\right)\right|`$; the *out-degree* $`d^+\left(S\right)=\left|N^+\left(S\right)\right|`$.

A vertex $`v_i`$ in a digraph $`D`$ is *isolated* if it is not in a dipath with another vertex of $`D`$.

A digraph $`D`$ is *connected* if, for every $`v_i,v_jV\left(D\right)`$, there is a dipath containing $`v_i`$ to $`v_j`$, or *viceversa*; $`D`$ is *strongly-connected* if, for every $`v_i,v_jV\left(D\right)`$, there is a dipath from $`v_i`$ to $`v_j`$ and from $`v_j`$ to $`v_i`$.

###### Theorem 1.

Let $`D`$ be a digraph on $`n`$ vertices (none of which isolated) and $`m`$ arcs. Then:

* | $`\left|V\left(\stackrel{}{L}D\right)\right|=m`$ | and | $`\left|A\left(\stackrel{}{L}D\right)\right|=_{v_iV\left(D\right)}d^+\left(v_i\right)d^{}\left(v_i\right);`$ |
| --- | --- | --- |
* | $`N^{}\left((v_i,v_j)\right)=d^{}\left(v_i\right)`$ | and | $`N^+\left((v_i,v_j)\right)=d^+\left(v_j\right);`$ |
| --- | --- | --- |
* $`\stackrel{}{L}D\stackrel{}{P}_{n1}`$ if and only if $`D\stackrel{}{P}_n`$;
* $`\stackrel{}{L}D\stackrel{}{C}_n`$ if and only if $`D\stackrel{}{C}_n`$.

###### Theorem 2.

Let $`D`$ be a digraph. Then

* $`\stackrel{}{L}^nD`$ is an emty-graph, for some $`n`$, if and only if $`D`$ has no dipaths;
* if $`D`$ has two dicycles joined by a $`k`$-dipath (possibly $`k=1`$), then

$$\underset{n\mathrm{}}{lim}p_n=\mathrm{},$$

where $`p_n`$ is the number of vertices of $`\stackrel{}{L}^nD`$;
* if $`D`$ is strongly connected, and if $`\stackrel{}{L}^nDD`$ for some $`n`$, then $`\stackrel{}{L}DD`$, and $`D`$ is a dicycle.

A digraph $`D`$ is *hamiltonian* when $`V\left(D\right)=V\left(H\right)`$, where $`H`$ is a dicycle. A digraph $`D`$ is *eulerian* if it is connected and, for every $`v_iV\left(D\right)`$, $`d^{}\left(v_i\right)=d^+\left(v_i\right)`$. A digraph $`D`$ is regular if, for every $`v_i,v_jV\left(D\right)`$, $`d^{}\left(v_i\right)=d^+\left(v_i\right)=d^{}\left(v_j\right)=d^+\left(v_j\right)`$.

###### Theorem 3.

Let $`D`$ be a digraph. Then

* $`\stackrel{}{L}D`$ is strongly connected if and only if $`D`$ is strongly connected;
* $`\stackrel{}{L}D`$ is eulerian if and only if, for every arc $`(v_i,v_j)A\left(D\right)`$, $`d^{}\left(v_i\right)=d^+\left(v_j\right)`$;
* $`\stackrel{}{L}D`$ is hamiltonian if and only if $`D`$ is eulerian.

A *general partition* of a set $`S`$ is a collection $`\left\{S_i\right\}_{iI}`$ of (possibly empty) subsets of $`S`$, such that

| $`S=_{iI}S_i,`$ | and | $`S_iS_j=\mathrm{}`$ if $`ij.`$ |
| --- | --- | --- |

A digraph $`D`$ is said to be $`F`$*-free* if it does not contain any subdigraph isomorphic to $`F`$.

The *adjacency matrix* of a digraph $`D`$ on $`n`$ vertices, denoted by $`M\left(D\right)`$ is the $`n\times n`$ $`(0,1)`$-matrix with $`ij`$-th entry equal to $`1`$ if $`(i,j)A\left(D\right)`$, and equal to $`0`$, otherwise. Let $`r_i\left(M\right)`$ and $`c_j\left(M\right)`$ be respectively the $`i`$-th row and the $`j`$-th column of a matrix $`M`$. Let $`a,b`$ the inner product of vectors $`a`$ and $`b`$.

###### Theorem 4.

Let $`D`$ be a digraph. Then the following statements are equivalent:

* $`D`$ is a line digraph;
* there exist two general partitions $`\left\{A_i\right\}_{iI}`$ and $`\left\{B_i\right\}_{iI}`$ of $`V\left(D\right)`$ such that, for each $`i`$ and $`j`$,

| $`\left|A_jB_i\right|1\delta _{i,j},`$ | and such that | $`A\left(D\right)=_{iI}A_i\times B_i;`$ |
| --- | --- | --- |
* any two rows of $`M\left(D\right)`$ are identical or orthogonal, $`M_{i,i}=0`$ for all $`i`$, and if $`r_i\left(M\right)=r_j\left(M\right)0`$ then $`c_i\left(M\right),c_j\left(M\right)=0`$;
* any two columns of $`M\left(D\right)`$ are identical or orthogonal, $`M_{i,i}=0`$ for all $`i`$, and if $`c_i\left(M\right)=c_j\left(M\right)0`$ then $`r_i\left(M\right),r_j\left(M\right)=0`$;
* $`D`$ is $`D_3`$\- and $`D_4`$-free, where

$$D_3=(\{1,2,3,4\},\{(1,2),(1,3),(4,2)\}),$$

and

$$D_4=(\{1,2,3\},\{(1,2),(3,1),(3,2)\}).$$

Any digraph obtained from $`D_3`$ or $`D_4`$ by adding arcs is not an induced subdigraph of $`D`$, with the exception of

$$D_3^{}=\left(\{1,2,3,4\}\{(1,2),(1,3),(4,2),(4,3)\}\right)$$

and

$$D_4^{}=(\{1,2,3\},\{(1,2),(3,1),(3,2),(1,1)\}).$$

###### Theorem 5 (\[P01\]).

Let $`D`$ be a strongly connected digraph. If $`D`$ is regular then all its iterated line digraphs are regular, thus eulerian, and hamiltonian.

### 2.3. Algebraic properties

#### 2.3.1. Spectrum

Let $`D`$ be a digraph on $`n`$ vertices. The set of eigenvalues of the adjacency matrix $`M\left(D\right)`$ is denoted by $`sp\left(D\right)`$, and called *spectrum* of $`D`$ \[CDH95\]. Let $`I_n`$ be the $`n\times n`$ identity matrix.

###### Theorem 6 (see \[LZ83\] or \[R01\]).

Let $`D`$ be a digraph. The characterisitc polynomial of $`\stackrel{}{L}D`$ is

(2.1)
$$P(\stackrel{}{L}D,x)=x^{\left|A\left(D\right)\right|\left|V\left(D\right)\right|}P(D,x),$$

where

$$P(D,x)=det\left(xI_nM\left(D\right)\right)$$

is the characteristic polynomial of $`D`$.

Let $`\left\{0\right\}_n`$ be a set of $`n`$ zeros. By Theorem 6, since

$$sp\left(K_d^+\right)=\left\{d\right\}\left\{0\right\}_{d1},$$

we have the following corollary.

###### Corollary 1.

$`sp\left(B(d,k)\right)=\left\{d\right\}\left\{0\right\}_{d^k1}`$.

#### 2.3.2. Moore-Penrose inverse

A matrix $`M^+`$ is a *Moore-Penrose inverse* of a matrix $`M`$ if

* $`MM^+M=M`$,
* $`M^+MM^+=M^+`$,
* $`\left(MM^+\right)^{}=MM^+`$,
* $`\left(M^+M\right)^{}=M^+M`$.

###### Theorem 7 (\[Sm81\]).

A square $`(0,1)`$-matrix has a Moore-Penrose inverse if and only if it is the adjacency matrix of a line digraph.

#### 2.3.3. Permanent

The *permanent* of a $`(0,1)`$-matrix $`M`$ is

$$per\left(M\right)=\underset{\pi S_n}{}\underset{i=1}{\overset{n}{}}A_{i,\pi \left(i\right)},$$

where $`S_n`$ is the symmetric group on an $`n`$-set.

###### Theorem 8 (\[KSW97\]).

Let $`D`$ be a digraph. Then

$$per\left(M\left(\stackrel{}{L}D\right)\right)>0$$

if and only if each connected component of $`D`$ is eulerian.

### 2.4. Line digraphs and unitary matrices

Let $`M`$ be a matrix over any field. The *support of* $`M`$ is the $`(0,1)`$-matrix with $`ij`$-th element equal to $`1`$ if $`M_{i,j}0`$, and equal to $`0`$, otherwise. The *digraph of* $`M`$ is the digraph whose adjacency matrix is the support of $`M`$. If a digraph $`D`$ is the digraph of a matrix $`M`$ then we say that $`D`$, or indistinctly $`M\left(D\right)`$, *supports* $`M`$.

###### Theorem 9 (\[Se03\]).

Let $`D`$ be a digraph. Then $`\stackrel{}{L}D`$ is the digraph of a unitary matrix if and only if every connected component of $`D`$ is eulerian.

## 3. A characterization of the line digraph of a regular digraph

In this section, we characterize the adjacency matrix of the line digraph of a regular digraph.

### 3.1. The characterization

Let $`D`$ be a digraph. A $`1`$*-cycle factor* of $`D`$ is the disjoint union of directed cycles spanning $`D`$. The adjacency matrix of a $`1`$-cycle factor is a permutation matrix.

A $`k`$-*factor* $`F`$ of $`D`$ is a $`k`$-regular spanning subdigraph of $`D`$. A $`k`$-*factorization of* $`D`$ is a set $`\{F_1,F_2,\mathrm{},F_m\}`$ of pairwise arc-disjoint $`k`$-factors of $`D`$ *covering* $`A\left(D\right)`$, that is $`A\left(D\right)=F_1F_2\mathrm{}F_m`$. More generally, a *factorization of* $`D`$ is a set of pairwise arc-disjoint factors of $`D`$, possibly of different degrees, covering $`A\left(D\right)`$.

The *growth* $`\mathrm{{\rm Y}}_D\left(F\right)`$ of $`D`$, introduced in \[HS96\], is a digraph derived from a spanning subdigraph $`F`$ of $`D`$, by adding, for each vertex $`v_iF`$,

| $`l=\left|N_D^+\left(v_i\right)\right|\left|N_F^+\left(v_i\right)\right|`$ | vertices | $`\{v_1,\mathrm{},v_l\}`$ |
| --- | --- | --- |

and

| $`l`$ | arcs | $`(v_i,v_1),(v_i,v_2),\mathrm{},(v_i,v_l).`$ |
| --- | --- | --- |

###### Proposition 1.

Let $`D`$ be a $`k`$-regular digraph. Let $`\{F_1,F_2,\mathrm{},F_k\}`$ be a $`1`$-factorization of $`D`$. Then there is a labeling of $`\stackrel{}{L}D`$, such that

$$M\left(\stackrel{}{L}D\right)=\left[\begin{array}{cccc}M\left(F_1\right)& M\left(F_2\right)& \mathrm{}& M\left(F_k\right)\\ M\left(F_1\right)& M\left(F_2\right)& \mathrm{}& M\left(F_k\right)\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ M\left(F_1\right)& M\left(F_2\right)& \mathrm{}& M\left(F_k\right)\end{array}\right].$$

###### Proof.

Since $`D`$ is $`k`$-regular, the adjacency matrix of $`D`$ is

$$M\left(D\right)=\underset{j=1}{\overset{k}{}}M\left(F_j\right).$$

Label by the pair $`(F_j,v_l)`$ the arc $`(v_i,v_l)`$ of $`F_j`$. Construct $`\mathrm{{\rm Y}}_D\left(F_j\right)`$. Note that $`F_j`$ is a subdigraph of $`\mathrm{{\rm Y}}_D\left(F_j\right)`$. So, in $`\mathrm{{\rm Y}}_D\left(F_j\right)`$, we can keep the same labelling of $`F_j`$. In addition, we label by $`v_m`$, with $`ml`$, the $`m`$-th of the $`k1`$ vertices which are heads of the arcs incident to $`v_i`$ and that are not in $`F_j`$. Then label the arc $`(v_i,v_m)`$ with the pair $`(F_m,v_m)`$. Since each $`F_j`$ is the disjoint union of dicycles, and since the line digraph of a dicycle is a dicycle (see, *e.g.*, \[HB78\], Theorem 7.1), it follows that

$$\mathrm{{\rm Y}}_D\left(F_j\right)\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_j\right).$$

Given the chosen labelling and an ordering of the vertices,

$$M\left(\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_j\right)\right)=\left[\begin{array}{cccccc}\mathrm{𝟎}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{𝟎}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}\\ M\left(F_1\right)& M\left(F_2\right)& \mathrm{}& M\left(F_j\right)& \mathrm{}& M\left(F_k\right)\\ \mathrm{𝟎}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{𝟎}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}& \mathrm{}& \mathrm{𝟎}\end{array}\right],$$

where $`M\left(F_j\right)`$ is the $`(j,j)`$-th block of $`M\left(\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_j\right)\right)`$. Since, the set

$$\{F_1,F_2,\mathrm{},F_k\}$$

is a $`1`$-factorization of $`D`$ if and only if

$$\{\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_1\right),\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_2\right),\mathrm{},\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_k\right)\}$$

is a $`1`$-factorization of $`\stackrel{}{L}D`$ \[HS96\], it follows that

$$M\left(\stackrel{}{L}D\right)=\underset{j=1}{\overset{k}{}}M\left(\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_j\right)\right).$$

### 3.2. Example

Consider the digraph $`D`$ with adjacency matrix matrix

$$M\left(D\right)=\left[\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 0& 1& 1& 0\end{array}\right].$$

Note that $`D`$ is a $`2`$-cube. Chose a $`1`$-factorization of $`D`$, $`\{F_1,F_2\}`$. For example, we chose $`\{F_1,F_2\}`$ such that

| $`M\left(F_1\right)=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]`$ | and | $`M\left(F_2\right)=\left[\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right]`$ |
| --- | --- | --- |

We obtain

$$M\left(\mathrm{{\rm Y}}_D\left(F_1\right)\right)=\begin{array}{ccccccccc}& F_1,1& F_1,2& F_1,3& F_1,4& F_2,1& F_2,2& F_2,3& F_2,4\\ F_1,1& 0& 1& 0& 0& 0& 0& 1& 0\\ F_1,2& 1& 0& 0& 0& 0& 0& 0& 1\\ F_1,3& 0& 0& 0& 1& 1& 0& 0& 0\\ F_1,4& 0& 0& 1& 0& 0& 1& 0& 0\\ F_2,1& 0& 0& \mathrm{}& & & & \mathrm{}& 0\\ F_2,2& 0& 0& \mathrm{}& & & & \mathrm{}& 0\\ F_2,3& \mathrm{}& \mathrm{}& & & & & & \mathrm{}\\ F_2,4& 0& \mathrm{}& & & & & \mathrm{}& 0\end{array}$$

and

$$M\left(\mathrm{{\rm Y}}_D\left(F_2\right)\right)=\begin{array}{ccccccccc}& F_1,1& F_1,2& F_1,3& F_1,4& F_2,1& F_2,2& F_2,3& F_2,4\\ F_1,1& 0& 0& \mathrm{}& & & & \mathrm{}& 0\\ F_1,2& 0& 0& \mathrm{}& & & & \mathrm{}& 0\\ F_1,3& 0& \mathrm{}& & & & & & \mathrm{}\\ F_1,4& 0& \mathrm{}& & & & & \mathrm{}& 0\\ F_2,1& 0& 1& 0& 0& 0& 0& 1& 0\\ F_2,2& 1& 0& 0& 0& 0& 0& 0& 1\\ F_2,3& 0& 0& 0& 1& 1& 0& 0& 0\\ F_2,4& 0& 0& 1& 0& 0& 1& 0& 0\end{array}.$$

Now,

| $`\mathrm{{\rm Y}}_D\left(F_1\right)\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_1\right)`$ | and | $`\mathrm{{\rm Y}}_D\left(F_2\right)\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_2\right)`$ |
| --- | --- | --- |

Since $`\{\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_1\right),\mathrm{{\rm Y}}_{\stackrel{}{L}D}\left(F_2\right)\}`$ is a factorization of $`\stackrel{}{L}D`$,

$`M\left(\stackrel{}{L}D\right)`$ $`=`$ $`M\left(\mathrm{{\rm Y}}_D\left(F_1\right)\right)+M\left(\mathrm{{\rm Y}}_D\left(F_2\right)\right)=`$
$`=`$ $`\left[\begin{array}{cc}M\left(F_1\right)& M\left(F_2\right)\\ M\left(F_1\right)& M\left(F_2\right)\end{array}\right].`$
## 4. Line digraphs and coined quantum random walks

In this section, we first recall the definition of coined quantum random walk, then, we show that the underlying digraph of a coined quantum random walk is a line digraph. Coined quantum random walks, and continuous-time quantum random walks, are surveyed in \[K03\].

### 4.1. Definition

Let $`D`$ be a $`k`$-regular digraph on $`n`$ vertices. Consider two quantum systems, to which are respectively assigned the Hilbert spaces $`^k`$ and $`^n`$, of respective dimensions $`k`$ and $`n`$. Label each ray of the standard basis of $`^k`$ by a $`1`$-factor of $`D`$. Label each ray of the standard basis of $`^n`$ by the vertices of $`D`$. Let

$$\left\{\right|F_j,v_i:0jk,0in\}$$

be the standard basis of $`^{kn}=^k^n`$. Let $`|\psi _t^{kn}`$ be the state of the system at time $`t`$. Let

| $`\widehat{C}:^k^k`$ | and | $`\widehat{T}:^{kn}^{kn}`$ |
| --- | --- | --- |

be unitary operators, such that

| $`\widehat{C}:|F_j_{j=1}^k\alpha _j|F_j`$ | and | $`\widehat{T}:|F_j,v_i|F_j,v_l`$, where $`(v_i,v_l)F_j`$. |
| --- | --- | --- |

The matrices $`C`$ and $`T`$, arising from these operators, are respectively called *coin* and *shift*. Define the unitary operator

$$\widehat{U}:|F_j,v_i\underset{j=1,l:(v_i,v_l)F_j}{\overset{k}{}}\alpha _j|F_j,v_l.$$

A *coined quantum random walk* on $`D`$ *with coin* $`C`$, induced by the *transition matrix*

$$U=T\left(CI_n\right),$$

is a sequence $`\left\{X_t\right\}`$ of random variables. The sequence starts at $`X_0=v_i`$, fixed, or drawn from some initial distribution. At time $`t`$, the probability that $`X_t=v_j`$, conditioned on a initial state $`|\psi _0`$, is

| $`\mathrm{Pr}_t\left(v_j|\psi _0\right)=_i\psi _t\left|P^{(i,j)}\right|\psi _t,`$ | where | $`|\psi _t=U^t|\psi _0`$ |
| --- | --- | --- |

and $`P^{(i,j)}`$ is the projector onto the $`k`$-dimensional subspace spanned $`|F_j,v_i`$.

### 4.2. The underlying digraph of a coined quantum random walk

The *underlying digraph* of a random walk induced by a transition matrix $`M`$ is the digraph of $`M`$. In this sense, the underlying digraph of a coined quantum random walk induced by a unitary matrix $`U`$ is the digraph of $`U`$.

###### Proposition 2.

The underlying digraph of a coined quantum random walk is a line digraph.

###### Proof.

Let $`D`$ be a $`k`$-regular digraph on $`n`$ vertices. Let $`\{F_1,F_2,\mathrm{},F_k\}`$ be a factorization of $`D`$. By Proposition 1,

$$M\left(\stackrel{}{L}D\right)=\left(M\left(K_k^+\right)I_n\right)T,$$

where

$$T=\underset{j=1}{\overset{k}{}}M\left(F_j\right),$$

Observe that

$$M\left(\stackrel{}{L}D\right)^{}=T\left(M\left(K_k^+\right)I_n\right).$$

If in this equation we replace $`M\left(K_k^+\right)`$ with a unitary matrix $`C`$ of size $`k`$, we obtain

$$T\left(CI_n\right),$$

which is the transition matrix of a coined quantum random walk on $`D`$.

### 4.3. Example: the cycle

The following construction is described in \[FFY92\].

Let $`D=Cay(G,S)`$ be a Cayley digraph and let $`S=\{s_1,s_2,\mathrm{},s_d\}`$. Let

$$H=\{\pi _{s_i}:s_iS\}$$

be a set of permutations of $`S`$. Let $`H`$ act on $`S`$ as a regular group: we take $`\pi _{s_1}`$ as identity element and, for every $`s_i,s_jS`$, we assume that there exists a unique $`s_k`$, such that $`\pi _{s_k}\left(s_i\right)=s_j`$. The set $`H`$ can be used to define the following operation on $`S`$:

$$s_is_j=\pi _{s_i}\left(s_j\right).$$

Let $`S^{}S`$. The elements $`s_kS^{}`$, such that, for all $`s_i,s_jS`$,

$$s_k\left(s_is_j\right)=\left(s_ks_i\right)s_j,$$

form a group $`(S^{},)`$, whose identity element is $`s_1`$.

Let $`\times _{sd}`$ be the symbol of the (external) semidirect product. If $`HAut\left(G\right)`$ then $`(S,)H`$. In such a case, the digraph $`\stackrel{}{L}D`$ is a Cayley digraph of

$$\mathrm{\Omega }G\times _{sd}(S,),$$

with respect to the set of generators

$$\{(s_1,s_i):s_iS\}.$$

Let $`C_n`$ be the cyclic group of order $`n`$. Take $`n`$ odd. Assume that $`_nC_n`$ is generated by the set $`S=\{1,n1\}`$. The Cayley digraph $`D=Cay(_n,S)`$ is a cycle of lenght $`n`$. Let $`H=\{\pi _1,\pi _{n1}\}`$. Let $`\pi _1`$ be the identity and,

| $`\pi _{n1}\left(n1\right)=1`$ | and | $`\pi _{n1}\left(1\right)=n1.`$ |
| --- | --- | --- |

Then $`H_2`$. The element $`\pi _{n1}Aut\left(_n\right)`$. Then $`\stackrel{}{L}D`$ is the Cayley digraph of the group

$$\mathrm{\Omega }_n\times _{sd}_2D_n,$$

where

$$D_n=a,b:a^n=b^2=e,a^{n1}=bab$$

is the dihedral group of order $`2n`$, generated by its standard presentation.

By denoting a permutation in the standard cycle notation, we write

| $`g=\left(1\text{ }2\text{ }3\text{ … }n\right)`$ | and | $`g^{n1}=\left(1\text{ }n\text{ }n1\text{ … }2\text{ }1\right)`$, |
| --- | --- | --- |

where $`g=1`$ and $`g^{n1}=n1`$. Then

| $`\pi _{n1}\left(1\right)=\sigma \left(1\right)\sigma =n1,`$ | and | $`\pi _1\left(n1\right)=\sigma \left(n1\right)\sigma =1,`$ |
| --- | --- | --- |

where

$$\sigma =\left(2\text{ }n\right)\left(3\text{ }n1\right)\mathrm{}\left(\frac{n+1}{2}\text{ }\frac{n+1}{2}+1\right).$$

The fixed-point of $`\sigma `$ is $`1`$. Under the isomorphism $`\iota :_n\times _{sd}_2D_n`$, the generators of $`D_n`$ are

| $`\iota \left[(g,g)\right]=g=a`$ | and | $`\iota \left[(g,g^{n1})\right]=g\sigma =b,`$ |
| --- | --- | --- |

where

$$g\sigma =\left(1\text{ }n\right)\left(2\text{ }n1\right)\mathrm{}\left(\frac{n1}{2}\text{ }\frac{n+1}{2}+1\right).$$

The fixed-point of $`g\sigma `$ is $`\frac{n+1}{2}`$. The Cayley digraph $`Cay(D_n,\left\{a=g,b=g\sigma \right\})`$ is the $`1`$-skeleton of an $`n`$-gon prism. Let $`\rho _{reg}`$ be the (right) regular permutation representation of $`_n`$. By Proposition 1,

$$M\left(Cay(D_n,\{a,b\})\right)=\left[\begin{array}{cc}\rho _{reg}\left(g\right)& \rho _{reg}\left(g^{n1}\right)\\ \rho _{reg}\left(g\right)& \rho _{reg}\left(g^{n1}\right)\end{array}\right].$$

### 4.4. Line digraphs and in-split graphs

The notion of split graph is fundamental in symbolic dynamics (see, *e.g.*, \[LM95\]). Let $`D`$ be a digraph. Then $`\stackrel{}{L}D`$ is is a special case of *split graph* of $`D`$, namely a *in-split graphs*. Here is the definition. For every $`v_iV\left(D\right)`$, let

$$N^{}\left(v_i\right)=I(1,v_i)I(2,v_i)\mathrm{}I(m\left(v_i\right),v_i),$$

where $`m\left(v_i\right)`$ is the number of classes in the partition of $`N^{}\left(v_i\right)`$. Let $`𝒫`$ be a partition of $`A\left(D\right)`$ as above. The *in-split graph* *formed* from $`D`$ *using* $`𝒫`$ is denoted by $`D_{\left[𝒫\right]}`$ and defined as follows:

$$V\left(D_{\left[𝒫\right]}\right)=\{I(j,v_i):v_iV\left(S\right),1jm\left(v_i\right)\};$$

the number of arcs from the vertex $`I(k,v_l)`$ to the vertex $`I(j,v_i)`$ is the number of arcs in $`D`$ which belong to $`I(j,v_i)`$ and have $`v_l`$ as tail. If $`𝒫`$ is the maximal partition (all its classes have cardinality 1) then

$$D_{\left[𝒫\right]}=\stackrel{}{L}D.$$

Acknowledgements. I wish to thank Yaokun Wu for referring me to \[LM95\]. I wish to thank Richard Jozsa and Andreas Winter for reading earlier versions of the paper.