2.1. Notation

In this work, we will often work with operators between some tensor powers of some vector spaces. Therefore, we adopt the “physics notation” with upper and lower indices for entries of these “tensors.” That is, given $T\;:\; V^{\otimes k}\to V^{\otimes l}$ for some $V={\mathbb{C}}^N$ , we denote

\begin{equation*}T(e_{i_1}\otimes \cdots \otimes e_{i_k})=\sum _{j_1,\ldots,j_l=1}^NT^{j_1\cdots j_l}_{i_1\cdots i_k}(e_{j_1}\otimes \cdots \otimes e_{j_l})\end{equation*}

We will sometimes shorten the notation and write $T_{\textbf{i}}^{\textbf{j}}$ using multi-indices $\textbf{i}=(i_1,\ldots,i_k)$ , $\textbf{j}=(j_1,\ldots,j_l)$ .

2.2. Compact matrix quantum groups

A compact matrix quantum group is a pair $G=(A,u)$ , where $A$ is a $*$ -algebra and $u=(u^i_j)\in M_N(A)$ is a matrix with values in $A$ such that

1. 1. the elements $u^i_j$ , $i,j=1,\ldots, N$ generate $A$ ,

2. 2. the matrices $u$ and $u^t$ ( $u$ transposed) are similar to unitary matrices,

3. 3. the map $\Delta \;:\; A\to A\otimes A$ defined as $\Delta (u^i_j)\;:\!=\;\sum _{k=1}^N u^i_k\otimes u^k_j$ extends to a $*$ -homomorphism.

Compact matrix quantum groups introduced by Woronowicz [Reference Woronowicz32] are generalizations of compact matrix groups in the following sense. For a matrix group $G\subseteq M_N({\mathbb{C}})$ , we define $u^i_j\;:\; G\to{\mathbb{C}}$ to be the coordinate functions $u^i_j(g)\;:\!=\;g^i_j$ . Then we define the coordinate algebra $A\;:\!=\;\mathscr{O}(G)$ to be the algebra generated by $u^i_j$ . The pair $(A,u)$ then forms a compact matrix quantum group. The so-called comultiplication $\Delta \;:\; \mathscr{O}(G)\to \mathscr{O}(G)\otimes \mathscr{O}(G)$ dualizes matrix multiplication on $G$ : $\Delta (f)(g,h)=f(gh)$ for $f\in \mathscr{O}(G)$ and $g,h\in G$ .

Therefore, for a general compact matrix quantum group $G=(A,u)$ , the algebra $A$ should be seen as the algebra of non-commutative functions defined on some non-commutative compact underlying space. For this reason, we often denote $A=\mathscr{O}(G)$ even if $A$ is not commutative. Actually, $A$ also has the structure of a Hopf $*$ -algebra. In addition, we can also define the C^*-algebra $C(G)$ as the universal C^*-completion of $A$ , which can be interpreted as the algebra of continuous functions of $G$ . The matrix $u$ is called the fundamental representation of $G$ .

A compact matrix quantum group $H=(\mathscr{O}(H),v)$ is a quantum subgroup of $G=(\mathscr{O}(G),u)$ , denoted as $H\subseteq G$ , if $u$ and $v$ have the same size and there is a surjective $*$ -homomorphism $\varphi \;:\; \mathscr{O}(G)\to \mathscr{O}(H)$ sending $u^i_j\mapsto v^i_j$ . We say that $G$ and $H$ are equal if there exists such a $*$ -isomorphism (i.e. if $G\subset H$ and $H\subset G$ ). We say that $G$ and $H$ are isomorphic if there exists a $*$ -isomorphism $\varphi \;:\; \mathscr{O}(G)\to \mathscr{O}(H)$ such that $(\varphi \otimes \varphi )\circ \Delta _G=\Delta _H\circ \varphi$ . We will often use the notation $H\subseteq G$ also if $H$ is isomorphic to a quantum subgroup of $G$ .

One of the most important examples is the quantum generalization of the orthogonal group—the free orthogonal quantum group $O_N^+$ defined by Wang in [Reference Wang29] through the universal $*$ -algebra

\begin{equation*}\mathscr {O}(O_N^+)\;:\!=\;\mathop{\ast \textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid u^i_j=u^{i*}_j,uu^t=u^tu=\textrm {id}_{{\mathbb {C}}^N}).\end{equation*}

Note that this example was then further generalized by Banica [Reference Banica2] into the universal free orthogonal quantum group $O^+(F)$ , where $F\in M_N({\mathbb{C}})$ such that $F\bar F=\pm \textrm{id}_{{\mathbb{C}}^N}$ and

\begin{equation*}\mathscr {O}(O^+(F))\;:=\;\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid \text {$u$ is unitary, }u=F\bar uF^{-1}),\end{equation*}

where $[\bar u]^i_j=u^{i*}_j$ .

2.3. Representation categories and Tannaka–Krein reconstruction

For a compact matrix quantum group $G=(\mathscr{O}(G),u)$ , we say that $v\in M_n(\mathscr{O}(G))$ is a representation of $G$ if $\Delta (v^i_j)=\sum _{k}v^i_k\otimes v^k_j$ , where $\Delta$ is the comultiplication. The representation $v$ is called unitary if it is unitary as a matrix, that is $\sum _k v^i_kv^{j*}_k=\sum _k v^{k*}_iv^k_j=\delta _{ij}$ . In particular, an element $a\in \mathscr{O}(G)$ is a one-dimensional representation if $\Delta (a)=a\otimes a$ . Another example of a quantum group representation is the fundamental representation $u$ .

We say that a representation $v$ of $G$ is non-degenerate if $v$ is invertible as a matrix (in the classical group theory, we typically consider only non-degenerate representations). It is faithful if $\mathscr{O}(G)$ is generated by the entries of $v$ . The meaning of this notion is the same as with classical groups: Given a non-degenerate faithful representation $v$ , the pair $G'=(\mathscr{O}(G),v)$ is also a compact matrix quantum group, which is isomorphic to the original $G$ .

A subspace $W\subset{\mathbb{C}}^n$ is called an invariant subspace of $v$ if the projection $P\;:\;{\mathbb{C}}^n\to{\mathbb{C}}^n$ onto $W$ commutes with $v$ , that is, $Pv=vP$ . This then defines the subrepresentation $w:=vP=Pv$ . However, $w$ as a representation is degenerate. If we need to express the subrepresentation as a non-degenerate representation, we had better consider a better consider a coisometry $U\;:\;{\mathbb{C}}^n\to{\mathbb{C}}^m$ with $P=U^*U$ and define $w'\;:\!=\;UvU^*$ . A representation $v$ is called irreducible if it has no non-trivial subrepresentations.

For two representations $v\in M_n(\mathscr{O}(G))$ , $w\in M_m(\mathscr{O}(G))$ of $G$ we define the space of intertwiners

\begin{equation*}\textrm {Mor}(v,w)=\{T\;:\; {\mathbb {C}}^n\to {\mathbb {C}}^m\mid Tv=wT\}.\end{equation*}

The set of all representations of a given quantum group together with those intertwiner spaces forms a rigid monoidal $*$ -category, which will be denoted by $\textrm{Rep}\; G$ .

Nevertheless, since we are working with compact matrix quantum groups, it is more convenient to restrict our attention only to certain representations related to the fundamental representation. If we work with orthogonal quantum groups $G\subset O_n^+$ (or $G\subset O^+(F)$ in general), then it is enough to focus on the tensor powers $u^{\otimes k}$ since the entries of those representations already linearly span the whole $\mathscr{O}(G)$ .

Considering $G=(\mathscr{O}(G),u)\subset O^+(F)$ , $F\in M_N({\mathbb{C}})$ , we define

\begin{equation*}\mathfrak {C}_G(k,l)\;:\!=\;\textrm {Mor}(u^{\otimes k},u^{\otimes l})=\{T\;:\; ({\mathbb {C}}^N)^{\otimes k}\to ({\mathbb {C}}^N)^{\otimes l}\mid Tu^{\otimes k}=u^{\otimes l}T\}.\end{equation*}

The collection of such linear spaces forms a rigid monoidal $*$ -category with the monoid of objects being the natural numbers with zero $\mathbb N_0$ .

Conversely, we can reconstruct any compact matrix quantum group from its representation category [Reference Woronowicz33, Reference Malacarne22].

We can write down the associated quantum group very concretely. The relations satisfied in the algebra $\mathscr{O}(G)$ will be exactly the intertwining relations:

\begin{equation*}\mathscr {O}(G)=\mathop{\ast\textrm{-}\textrm{alg}}(u^i_j,\;i,j=1,\ldots,N\mid u=F\bar uF^{-1},\; Tu^{\otimes k}=u^{\otimes l}T\;\forall T\in \mathfrak {C}(k,l)).\end{equation*}

We say that $S$ is a generating set for a representation category $\mathfrak{C}$ if $\mathfrak{C}$ is the smallest monoidal $*$ -category satisfying the assumptions of Theorem 2.2 that contains $S$ . We use the notation $\mathfrak{C}=\langle S\rangle _N$ (it is important to specify the dimension $N$ of the vector space $V={\mathbb{C}}^N$ associated to the object 1). If we know such a generating set, it is enough to use the generators for our relations:

\begin{equation*}\mathscr {O}(G)=\mathop{\ast\textrm{-}\textrm{alg}}(u^i_j,\;i,j=1,\ldots,N\mid u=F\bar uF^{-1},\; Tu^{\otimes k}=u^{\otimes l}T\;\forall T\in S(k,l)).\end{equation*}

2.4. Partitions

Representation categories of homogeneous orthogonal quantum groups, that is, those $G$ such that $S_N\subset G\subset O_N^+$ are conveniently described using partitions. A partition $p\in \mathscr{P}(k,l)$ is a decomposition of $k$ upper and $l$ lower points into non-empty disjoint subsets called blocks. For instance,

Given any partition $p\in \mathscr{P}(k,l)$ , we define a linear map $T_p^{(N)}\;:\; ({\mathbb{C}}^N)^{\otimes k}\rightarrow ({\mathbb{C}}^N)^{\otimes l}$ whose entries are given as “blockwise Kronecker delta”—we label the $k$ upper points by indices $i_1,\ldots,i_k$ and the $l$ lower points by indices $j_1,\ldots,j_l$ and define $[T_p^{(N)}]^{j_1,\ldots,j_l}_{i_1,\ldots,i_k}$ to be one if and only if for any given block of $p$ all the corresponding indices are equal. For instance, working with the example above, we may write

\begin{equation*}[T_p^{(N)}]^{j_1j_2j_3j_4}_{i_1i_2i_3}=\delta _{i_1i_2i_3j_2j_3},\quad [T_q^{(N)}]^{j_1j_2j_3j_4}_{i_1i_2i_3i_4}=\delta _{i_2j_3j_4}\delta _{i_3j_2}.\end{equation*}

We define $\mathsf{Part}_N(k,l)\;:\!=\;\textrm{span}\mathscr{P}(k,l)$ the space of formal linear combinations of partitions. On this collection of linear spaces, we may define the structure of a monoidal $*$ -category in terms of simple pictorial manipulations (see e.g. [Reference Gromada and Weber16] for details) such that they respect the category structure in $\mathfrak{C}_{S_n}$ . In other words, the mapping $T^{(N)}\;:\; \mathsf{Part}_n\to \mathfrak{C}_{S_n}$ is a monoidal unitary functor. (Note that passing to the linear spaces is often omitted, but in this article, we need them.)

As a consequence, any homogeneous quantum group $O_N^+\supset G\supset S_N$ can be described using some diagrammatic category of partitions. Thanks to the Tannaka–Krein duality, we also have the converse—any category of partitions defines a some homogeneous compact matrix quantum group [Reference Banica and Speicher12]. For more information, see the survey [Reference Weber31] or the author’s PhD thesis [Reference Gromada14].

Finally, let us mention that when working with anticommutative deformations of groups (see the next section), then it might (although sometimes might not) be convenient to use a deformed functor. Let $p\in \mathscr{P}(k,l)$ be a partition that does not contain any block of odd size. Then we define a linear operator $\breve{T}_p^{(N)}$ by

\begin{equation*}[\breve T_p^{(N)}]^{\textbf {j}}_{\textbf {i}}=\sigma _{\textbf {i}}\sigma _{\textbf {j}}[T_p^{(N)}]^{\textbf {j}}_{\textbf {i}},\end{equation*}

where $\sigma _{\textbf{i}}$ is a certain sign function: Given a multi-index $\textbf{i}=(i_1,\ldots,i_k)$ , we count the number of pairs $(k,l)$ such that $k<l$ , but $i_k>i_l$ . If this number is odd, then $\sigma _{\textbf{i}}=-1$ ; otherwise $\sigma _{\textbf{i}}=1$ . See [Reference Gromada and Weber17, Section 7].

2.5. Anticommutative deformations

In this work, we will often work with certain anticommutative deformations of classical groups. We say that a matrix $u$ has anticommutative entries if the following relations hold

\begin{equation*}u^i_ku^j_k=-u^j_ku^i_k,\quad u^k_iu^k_j=-u^k_ju^k_i,\quad u^i_ku^j_l=u^j_lu^i_k\end{equation*}

assuming $i\neq j$ and $k\neq l$ .

As an example, let us mention the anticommutative orthogonal quantum group

\begin{equation*}\mathscr {O}(O_N^{-1})=\mathop{\ast\textrm{-alg}}(u^i_j\mid \text {$u=\bar u$, $u$ orthogonal, $u$ anticommutative}).\end{equation*}

There is a whole theory about $q$ -deformations of classical groups, where taking $q=1$ gives the classical case and $q=-1$ gives usually the anticommutative one, see [Reference Klimyk and Schmüdgen19] for more details.

2.6. Exterior products: classical case

In this section, we would like to recall the definition of exterior products in connection with the representation theory of classical groups.

Let $V$ be a vector space. We define the exterior product $V\wedge V$ and, more generally, the exterior powers $\Lambda _k(V)=V^{\wedge k}$ as follows. $V^{\wedge k}$ is the vector subspace of $V^{\otimes k}$ generated by the elements

\begin{equation*}v_1\wedge \cdots \wedge v_k={1\over k!}\sum _{\sigma \in S_k}\textrm {sgn}(\sigma )v_{\sigma (1)}\otimes \cdots \otimes v_{\sigma (k)}\end{equation*}

We denote by ${\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\wedge k}$ the coisometry mapping $v_1\otimes \cdots \otimes v_k\mapsto v_1\wedge \cdots \wedge v_k$ and call it the antisymmetrizer. (That is, ${\mathcal{A}}_k^*{\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\otimes k}$ is the projection onto $V^{\wedge k}$ taken as a subspace of $V^{\otimes k}$ .)

The motivation for such a definition is the following.

In particular, we can consider $G=O_n$ acting on $V={\mathbb{C}}^n$ by standard matrix multiplication. Let us prove this statement from a quantum group point of view.

Proof. Let $u\in C(G)\otimes GL(V)$ be the representation of $G$ on $V$ . We need to prove that $u^{\otimes k}{\mathcal{A}}_k^*{\mathcal{A}}_k={\mathcal{A}}_k^*{\mathcal{A}}_k u^{\otimes k}$ . Let us express both sides in coordinates.

\begin{align*} [u^{\otimes k}{\mathcal{A}}_k^*{\mathcal{A}}_k]^{\textbf{i}}_{\textbf{j}}&={1\over k!}\sum _{\sigma \in S_k}\textrm{sgn}(\sigma )u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}\\[5pt] [{\mathcal{A}}_k^*{\mathcal{A}}_k u^{\otimes k}]^{\textbf{i}}_{\textbf{j}}&={1\over k!}\sum _{\sigma \in S_k}\textrm{sgn}(\sigma )u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k} \end{align*}

The terms $u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}$ and $u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ differ just by reordering of the factors. Since we assume that $G$ is a classical group, the entries of $u$ are commutative, so the terms must be equal.

We denote by

\begin{equation*}u^{\wedge k}\;:\!=\;{\mathcal {A}}_k u^{\otimes k}{\mathcal {A}}_k^*\end{equation*}

the corresponding subrepresentation.

The dimension of the $k$ th exterior power $V^{\wedge k}$ equals $\binom{n}{k}$ , where $n=\dim V$ . The highest non-zero power is therefore the $n$ th, which is one-dimensional. Given a representation $u$ of some group $G$ , the $n$ th exterior power of $u$ equals to the determinant $u^{\wedge n}=\mathop{\textrm{det}}\nolimits u$ .

2.7. Exterior products: anticommutative case

The concept of exterior product does not work in general for quantum groups. Let us revise it here for the case of anticommutative deformations.

For this purpose, we need to introduce some sort of “anticommutative antisymmetrization.” This should be basically the same thing as the usual symmetrization, but, in addition, we have to “throw out the diagonal” again. (Recall that classically we have $v_1\wedge \cdots \wedge v_k=0$ whenever $v_a=v_b$ for some $a,b$ .)

We define $V^{\mathop{\breve \wedge } k}$ to be the vector subspace of $V^{\otimes k}$ generated by the elements

\begin{equation*}v_1\mathop {\breve \wedge }\cdots \mathop {\breve \wedge } v_k= \begin {cases} 0&\text {if $v_a=v_b$ for some $a\neq b$}\\[5pt] \frac {1}{k!}\sum _{\sigma \in S_k}v_{\sigma (1)}\otimes \cdots \otimes v_{\sigma (k)}&\text {otherwise} \end {cases}\end{equation*}

We denote by $\breve{\mathcal{A}}_k\;:\; V^{\otimes k}\to V^{\mathop{\breve \wedge } k}$ the coisometry mapping $v_1\otimes \cdots \otimes v_k\mapsto v_1\mathop{\breve \wedge }\cdots \mathop{\breve \wedge } v_k$ .

In other words, this means that $({\mathbb{C}}^n)^{\mathop{\breve \wedge } k}$ is an invariant space of the representation $u^{\otimes k}$ . We denote the corresponding subrepresentation by

\begin{equation*}u^{\mathop {\breve \wedge } k}\;:\!=\;\breve {\mathcal {A}}_k u^{\otimes k}\breve {\mathcal {A}}_k^*.\end{equation*}

Proof. Let us write both sides of the equation entrywise.

(2.1) \begin{align} [u^{\otimes k}\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k]^{\textbf{i}}_{\textbf{j}}&= \begin{cases} 0&\textrm{if $j_a=j_b$ for some $a\neq b$}\\[5pt] \frac{1}{k!}\sum _{\sigma \in S_k}u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}&\textrm{otherwise} \end{cases} \end{align}

(2.2) \begin{align} [\breve{\mathcal{A}}_k^*\breve{\mathcal{A}}_k u^{\otimes k}]^{\textbf{i}}_{\textbf{j}}&= \begin{cases} 0&\textrm{if $i_a=i_b$ for some $a\neq b$}\\[5pt] \frac{1}{k!}\sum _{\sigma \in S_k}u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}&\textrm{otherwise} \end{cases} \end{align}

Notice again that $u^{i_1}_{\sigma ^{-1}(j_1)}\cdots u^{i_k}_{\sigma ^{-1}(j_k)}$ and $u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ coincide up to ordering of the factors. If both $\textbf{i}$ and $\textbf{j}$ consist of mutually distinct indices, then the factors commute, and hence, the terms are equal. If $j_a=j_b$ for some $a\neq b$ , then the factors $u^{\sigma (i_a)}_{j_a}$ and $u^{\sigma (i_b)}_{j_b}$ mutually anticommute. Consequently, the symmetrization $\sum _{\sigma }u^{\sigma (i_1)}_{j_1}\cdots u^{\sigma (i_k)}_{j_k}$ equals to zero. The same applies in the case when $i_a=i_b$ for some $a\neq b$ .

The dimension of the anticommutative exterior powers is again given by the binomial coefficients. So, taking the $n$ th power, we can define the anticommutative determinant as follows

Since we assume the anticommutativity, all the factors of the terms always mutually commute. From this, the different ways to write down the determinant follow. The definition is very similar to the one of classical determinant—we are only missing the sign of the permutation in the sum. Such an object is sometimes considered also in the classical theory of matrices, where it is called the permanent. Since $u$ is a one-dimensional representation of $O_n^{-1}$ , it defines a quantum subgroup $SO_n^{-1}$ called the anticommutative special orthogonal quantum group

Note that the relation $u=1$ can be seen also as an intertwiner relation $\breve{\mathcal{A}}_nu^{\otimes n}=\breve{\mathcal{A}}_n$ . In other words $SO_n^{-1}$ is a quantum subgroup of $O_n^{-1}$ that was created by adding the intertwiner $\breve{\mathcal{A}}_n\in \textrm{Mor}(u^{\otimes n},1)$ to its representation category. Similarly, $SO_n$ can be created from $O_n$ by imposing the intertwiner ${\mathcal{A}}_n\in \textrm{Mor}(u^{\otimes n},1)$ .

2.8. Projective versions

Let $G\subset O_N^+$ be an orthogonal compact matrix quantum group and denote by $u$ its fundamental representation. Then $u\otimes u$ is surely its representation, but its matrix entries may not generate the whole algebra $\mathscr{O}(G)$ . Denote by $\mathscr{O}(PG)$ the $*$ -subalgebra of $\mathscr{O}(G)$ generated by entries of $u\otimes u$ , that is elements of the form $u^i_ju^k_l$ . Then $PG\;:\!=\;(\mathscr{O}(PG),u\otimes u)$ is a compact matrix quantum group called the projective version of $G$ .

For our work, we need only $q=+1$ (classical case) and $q=-1$ (anticommutative case). Nevertheless, the statement and its proof actually does not depend on $q$ and we could take any deformation of the orthogonal group here.

Proof. Denote by $u$ the fundamental representation of $O_N^q$ , so that $u\otimes u$ is the fundamental representation of $PO_N^q$ . Denote by $v$ the fundamental representation of $SO_N^q$ .

We claim that there is a $*$ -homomorphism $\alpha \;:\; \mathscr{O}(SO_N^q)\to \mathscr{O}(PO_N^q)$ mapping

\begin{equation*}v^i_j\mapsto u^i_j\mathop {\textrm {det}}\nolimits _q u\end{equation*}

First, note that $u^i_j\mathop{\textrm{det}}\nolimits _q u$ is a polynomial of even degree in the entries of $u$ (since $N$ is odd, so the determinant is of odd degree), and hence, $u^i_j\mathop{\textrm{det}}\nolimits _q u$ is indeed an element of $\mathscr{O}(PO_N^q)$ . Secondly, it is easy to check that all relations of $SO_N^q$ are satisfied by the image. In particular the determinant equals to one since $\mathop{\textrm{det}}\nolimits _q\!(u^i_j\mathop{\textrm{det}}\nolimits _q u)_{i,j}=(\!\mathop{\textrm{det}}\nolimits _q u)^2=1$ .

On the other hand, there is surely a $*$ -homomorphism $\beta \;:\; \mathscr{O}(PO_N^q)\to \mathscr{O}(SO_N^q)$ mapping $u^i_ju^k_l\mapsto v^i_jv^k_l$ since this is nothing but the restriction of the quotient map $\mathscr{O}(O_N^q)\to \mathscr{O}(SO_N^q)$ . Finally, it is easy to check that both $\beta \circ \alpha$ and $\alpha \circ \beta$ equal to the identity, so the maps must actually be isomorphisms.

3.1. Quantum automorphism group of a graph

We define the free symmetric quantum group [Reference Wang30] $S_N^+=(C(S_N^+),u)$ , where

\begin{equation*}\mathscr {O}(S_N^+)=\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid (u^i_j)^2=u^i_j=u^{i*}_j,\;\sum _k u^i_k=1).\end{equation*}

It holds that $S_N^+$ describes all quantum symmetries of the space of $N$ discrete points. What we mean by this is that $S_N^+$ is the largest quantum group that faithfully acts on the space of $N$ points. Let us look on this property in even more detail.

Denote by $X_N=\{1,\ldots,N\}$ the set of $N$ points. We can associate to $X_N$ the algebra of all functions $C(X_N)$ , which has a basis $\delta _1,\ldots,\delta _N$ of the canonical projections, that is, functions $\delta _i(j)=\delta _{ij}$ . An action of a quantum group $G$ on $X_N$ is described by a coaction of the associated Hopf $*$ -algebra, that is, a $*$ -homomorphism $C(X_N)\to C(X_N)\otimes \mathscr{O}(G)$ satisfying some axioms.

Now, note that since $(\delta _i)$ is a linear basis of $C(X_N)$ , the action of any compact quantum group on $X_N$ must be of the form $\delta _j\mapsto \sum _{i=1}^N \delta _i\otimes v^i_j$ . The axioms of a coaction are now equivalent to the fact that $v$ is a representation of the acting quantum group $G$ . The algebra $C(X_N)$ can be defined as the universal C^*-algebra generated by $\delta _i$ satisfying the relations $\delta _i^2=\delta _i=\delta _i^*$ and $\sum _i\delta _i=1$ . Now, it is easy to check that the requirement of the coaction being a $*$ -homomorphism exactly corresponds to the defining relations of $C(S_N^+)$ .

Alternatively, one can see the homomorphism condition also as some kind of an intertwiner relation. $S_N^+$ can be seen as a quantum subgroup of $O_N^+$ with respect to the relation , that is, requiring . Here is a tensor $C^N\to{\mathbb{C}}^N\otimes{\mathbb{C}}^N$ defined by . See also [Reference Banica3, Reference Banica4].

Actually, it is easy to check that the partition $\sqcap$ defining $O_N^+$ together with defining $S_N^+\subset O_N^+$ generate all non-crossing partitions, that is, partitions where the strings do not cross. Let us denote by $NC(k,l)$ the set of all partitions $p\in \mathscr{P}(k,l)$ , which are non-crossing. This provides a “free quantum analogue” to Theorem 2.3 of Jones.

Now let $X$ be a finite graph, so it has a finite set of vertices $V\;:\!=\;V(X)$ . Let us number those vertices, so we can write $V=\{1,\ldots,N\}$ . The adjacency matrix of $X$ is then an $N\times N$ matrix $A_X$ with entries consisting of zeros and ones such that $[A_X]^j_i=1$ if and only if $(i,j)$ is an edge in $X$ . If $X$ is undirected, then $A_X$ should be symmetric, otherwise it need not. If we have $[A_X]^i_i=1$ , we say that $X$ has a loop at the vertex $i$ . All concrete examples of graphs mentioned in this paper will be simple, that is undirected and without loops, but the general considerations will hold also for the directed case with loops.

We say that a quantum group $G$ acts on the graph $X$ through the coaction $\alpha \;:\; \delta _i\mapsto \sum _j\delta _j\otimes u^j_i$ if the coaction $\alpha$ commutes with the adjacency matrix, that is, $\alpha \circ A=(A\otimes \textrm{id})\circ \alpha$ . Equivalently, this means the $uA=Au$ . The quantum automorphism group of $X$ is defined to be the universal quantum group acting on $X$ .

Definition 3.2 ([Reference Banica5]). Let $X$ be a graph on $N$ vertices. We define the quantum automorphism group of $X$ to be the compact matrix quantum group ${\textrm{Aut}}^+X=(\mathscr{O}({\textrm{Aut}}^+X),u)$ with

\begin{equation*}\mathscr {O}(\mathop{\textrm{Aut}}\nolimits^+X)=\mathop{\ast\textrm{-alg}}(u^i_j,\;i,j=1,\ldots,N\mid (u^i_j)^2=u^i_j=u^{i*}_j,\;\sum _k u^i_k=1,\;Au=uA).\end{equation*}

Equivalently, it is determined by its representation category

where $\uparrow \in \mathscr{P}(0,1)$ is the singleton partition. The equivalence of the two generating sets can be easily seen by noticing that on one hand and on the other hand. See also [Reference Chassaniol13].

3.2. The $n$ -dimensional hypercube

Consider a natural number $n\in \mathbb N$ . The $n$ -dimensional hypercube graph $Q_n$ is determined by the vertices and edges of an $n$ -dimensional hypercube. It can be parametrized as follows.

The set of $N\;:\!=\;2^n$ vertices can be identified with the elements of the group $\mathbb Z_2^n$ . We are going to denote these group elements by Greek letters $\alpha =(\alpha _1,\ldots,\alpha _n)\in \mathbb Z_2^n$ with $\alpha _i\in \{0,1\}\simeq \mathbb Z_2$ . We will denote the group operation as addition. We also denote the canonical generators by $\varepsilon _i=(0,\ldots,0,1,0,\ldots,0)$ .

Two vertices $\alpha,\beta \in V(Q_n)$ are connected by an edge if and only if they differ in exactly one of the $n$ indices, that is, if $\beta =\alpha +\varepsilon _i$ for some $i\in \{1,\ldots,n\}$ . Equivalently, we can say that $Q_n$ is the Cayley graph of $\mathbb Z_2^n$ with respect to the generating set $\varepsilon _1,\ldots,\varepsilon _n$ . We can also express the edges via the adjacency matrix

\begin{equation*}[A_{Q_n}]^\alpha _\beta = \begin {cases} 1&\text {if $\beta =\alpha +\varepsilon _i$ for some $i$,}\\[5pt] 0&\text {otherwise.} \end {cases}\end{equation*}

Example 3.3 ( $n=3$ ). We mention the example of the ordinary three-dimensional cube and its parametrization using triples of zero/one indices. Note that shifting the vertex by $\varepsilon _i$ , that is, flipping the $i$ th index, we move in the direction of the $i$ th dimension.

Below, we show the corresponding adjacency matrix. Since it is not clear, how the elements of $\mathbb Z_2^n$ should be ordered, we also labeled the rows with the corresponding tuples (the columns are ordered the same way). We also indicated the division of the matrix into blocks with respect to the number of ones in the tuple (essentially the distance from the $(0,0,0)$ -vertex).

3.3. Functions on the hypercube and Fourier transform

We denote by $C(Q_n)$ the algebra of functions on the vertex set $V(Q_n)=\mathbb Z_2^n$ . It has the canonical basis of $\delta$ -functions $\delta _\alpha$ defined by $\delta _\alpha (\beta )=\delta _{\alpha \beta }$ .

We can also define the structure of a Hilbert space $l^2(Q_n)$ on the vector space of functions simply by putting $\langle f,g\rangle =\sum _\alpha \overline{f(\alpha )}g(\alpha )$ . The basis $(\delta _\alpha )$ is then orthonormal with respect to this inner product.

There is another important basis on $l^2(Q_n)$ given by functions of the form

\begin{equation*}\tau _\mu =\tau _1^{\mu _1}\cdots \tau _n^{\mu _n},\qquad \hbox {where}\quad \mu =(\mu _1,\ldots,\mu _n)\in \mathbb Z_2^n\end{equation*}

and

\begin{equation*}\tau _i(\alpha )=(\!-\!1)^{\alpha _i},\end{equation*}

so

\begin{equation*}\tau _\mu (\alpha )=(\!-\!1)^{\alpha _1\mu _1+\cdots +\alpha _n\mu _n}=(\!-\!1)^{\alpha \cdot \mu }.\end{equation*}

First, note that the elements $\tau _\mu$ form a presentation of the group $\mathbb Z_2^n$ itself or, alternatively, of the group algebra ${\mathbb{C}}\mathbb Z_2^n$ . That is, we have $\tau _\mu \tau _\nu =\tau _{\mu +\nu }$ ; indeed,

\begin{equation*}(\tau _\mu \tau _\nu )(\alpha )=(\!-\!1)^{\alpha \cdot \mu }(\!-\!1)^{\alpha \cdot \nu }=(\!-\!1)^{\alpha \cdot (\mu +\nu )}=\tau _{\mu +\nu }.\end{equation*}

Secondly, note that the basis $(\tau _\mu )$ is orthogonal:

\begin{equation*}\langle \tau _\mu,\tau _\nu \rangle =\sum _\alpha (\!-\!1)^{\alpha \cdot (\mu +\nu )}= \begin {cases} 2^n&\text {if $\mu +\nu =0$, i.e. $\mu =\nu $,}\\[5pt] 0&\text {otherwise.} \end {cases}\end{equation*}

Let us explain more in detail the last equality, which will actually be useful also in subsequent computations.

Lemma 3.4. For $\beta \in \mathbb Z_2^n$ , it holds that

\begin{equation*}\sum _{\alpha \in \mathbb Z_2^n} (\!-\!1)^{\alpha \cdot \beta }= \begin {cases} 2^n&\textit {if $\beta =0$,}\\[5pt] 0&\textit{otherwise.} \end {cases}\end{equation*}

Proof. If $\beta =0$ , then $(\!-\!1)^{\alpha \cdot \beta }=(\!-\!1)^0=1$ , so in the sum we are summing over $2^n$ ones. Hence the result. If $\beta$ has some non-zero entry, say $\beta _i=1$ , then for every $\alpha$ , we can flip the $i$ th entry of $\alpha$ in order to flip the sign of $(\!-\!1)^{\alpha \cdot \beta }$ . Thus, there is an equal amount of $+1$ as $-1$ in the sum, so they cancel out.

We define the transformation matrix $\mathcal{F}\;:\; l^2(Q_n)\to l^2(Q_n)$ by $\mathcal{F}^\alpha _\mu =(\!-\!1)^{\alpha \cdot \mu }$ called the Fourier transform. It provides a transformation between the two bases: $\tau _\mu =\sum _\alpha \delta _\alpha \mathcal{F}^\alpha _\mu$ . Thanks to the orthogonality property above, we have that $\mathcal{F}$ is, up to scaling, orthogonal. More precisely $\mathcal{F}^{-1}={1\over 2^n}\mathcal{F}^*$ .

Example 3.5 ( $n=3$ ). Let us again look on the case $n=3$ . The matrix $\mathcal{F}$ consists only of $\pm 1$ elements. For easier reading, we write only $+$ or $-$ in the matrix instead of $+1$ and $-1$ . The order for the bases $(\delta _\alpha )$ and $(\tau _\mu )$ or, better to say, the order of the tuples $\alpha \in \mathbb Z_2^3$ are again indicated behind the matrix.

3.4. Applying Fourier transform to the intertwiners

Recall that the quantum automorphism group of the hypercube ${\textrm{Aut}}^+ Q_n$ should be the quantum subgroup of $S_N^+$ with respect to the intertwiner relation $uA=Au$ , where we denote for short $A\;:\!=\;A_{Q_n}$ . Equivalently, it is the quantum subgroup of $O_N^+$ with respect to relations and $uA=Au$ .

On the first sight, it is not clear, which quantum group these relations define. In order to see this, we first apply the Fourier transform to the intertwiners. (Recall that $\mathcal{F}$ is up to scaling orthogonal, so $O_N^+$ is invariant under $\mathcal{F}$ .) Let us look on an example first.

Example 3.6 ( $n=3$ ). The most important intertwiner seems to be the adjacency matrix of the graph as only this carries the data of the graph itself. A straightforward computation gives us a diagonal matrix

Writing some explicit matrices for would be slightly complicated, so we will get back to this tensor later. So, let us now do the computations for general $n$ . For the adjacency matrix, we have

\begin{align*} [\mathcal{F}^{-1}A\mathcal{F}]^\mu _\nu &={1\over 2^n}\sum _{\alpha,\beta }(\!-\!1)^{\alpha \cdot \mu }A^\alpha _\beta (\!-\!1)^{\beta \cdot \nu }={1\over 2^n}\sum _\alpha \sum _{i=1}^n(\!-\!1)^{\alpha \cdot \mu }(\!-\!1)^{(\alpha +\varepsilon _i)\cdot \nu }\\[5pt] &={1\over 2^n}\left (\sum _\alpha (\!-\!1)^{\alpha \cdot (\mu +\nu )}\right )\left (\sum _{i=1}^n(\!-\!1)^{\nu _i}\right )=\delta _{\mu \nu }(n-2\deg \nu ), \end{align*}

where $\deg \nu$ is the number of ones in $\nu$ , which we will subsequently call the degree of $\nu$ . So, we can say that the Fourier image of the adjacency matrix is a direct sum of identities with some scalar factors

(3.1) \begin{equation} \hat A\;:\!=\;\mathcal{F}^{-1}A\mathcal{F}=\bigoplus _{k=0}^n(n-2k)I_{\left(\substack{n\\[2pt] k}\right)} \end{equation}

Imposing $\hat A$ to be an intertwiner is equivalent to saying that every subspace of $l^2(Q_n)$ consisting of elements with a given degree $d$ (w.r.t. the basis $(\tau _\mu )$ ) is invariant. So, let us denote the invariant subspaces by

\begin{equation*}V_k\;:\!=\;\{f\in l^2(Q_n)\mid \deg f=k\}.\end{equation*}

Note that $\dim V_k={\left(\substack{n\\[2pt] k}\right)}$ . Note also that those spaces do not define a grading, but only a filtration on the algebra $C(Q_n)$ .

So, denote by $\hat u\;:\!=\;\mathcal{F}^{-1}u\mathcal{F}$ the Fourier transform of the fundamental representation of the quantum automorphism group of the hypercube and by $\hat u=\hat u^{(0)}\oplus \hat u^{(1)}\oplus \cdots \oplus \hat u^{(n)}$ the decomposition according to the invariant subspaces $V_k$ .

This was only how the adjacency matrix $A$ transforms under $\mathcal{F}$ . But we also need to transform the intertwiners defining the free symmetric quantum group $S_N^+$ . Let us consider the tensor defined by (This is indeed an intertwiner of $S_N^+$ since .)

Thanks to the fact that $u$ must be block diagonal (as we just derived), we can study such intertwiners restricted to such blocks. So, denote by $P_k$ the (Fourier transform composed with the) orthogonal projection $l^2(Q_n)\to V_k$ and define the tensor , which must be an intertwiner of $\hat u^{(1)}$ . We can compute its entries:

One can write down this result also using the partition notation as

This is well known to be the intertwiner defining the quantum group $O_n^{-1}$ . (See e.g. [Reference Gromada and Weber17, Section 7]). Now, we may already see, where is this heading toward.

As a side remark, note that one might also want to directly compute the projection of to the subspace $V_1$ . This is of course possible by doing a very similar computation. However, this intertwiner turns out to be equal to zero (since one can never “pair” a triple of indices).

3.5. Quantum automorphism group of the hypercube

In this section, we prove that the quantum automorphism group of the hypercube graph is the $O_n^{-1}$ —a result originally obtained in [Reference Banica, Bichon and Collins7, Theorem 4.2].

Theorem 3.7. The quantum automorphism group of the $n$ -dimensional hypercube graph is the anticommutative orthogonal quantum group $O_n^{-1}$ with the representation

\begin{equation*}\mathcal {F}\big (1\oplus v\oplus (v\mathop {\breve \wedge } v)\oplus \cdots \oplus v^{\mathop {\breve \wedge } n}\big )\mathcal {F}^{-1},\end{equation*}

where $v$ is the standard fundamental representation of $O_n^{-1}$ .

Proof. Denote by $u$ the fundamental representation of the quantum automorphism group of the hypercube ${\textrm{Aut}}^+Q_n$ . Denote by $\hat u\;:\!=\;\mathcal{F}^{-1}u\mathcal{F}$ the Fourier transform of $u$ . We prove the theorem by a series of lemmata. We start with results derived in the previous section.

Proof. Follows from the form of the Fourier transform of the adjacency matrix (3.1).

Proof. Follows from being an intertwiner of $\hat u^{(1)}$ .

Proof. The representation $\hat u$ acts on $Q_n$ through the coaction $\tau _\mu \mapsto \sum _\nu \tau _\nu \otimes u^\nu _\mu$ . Since the algebra $C(Q_n)$ is generated by the invariant subspace $V_1=\textrm{span}\{\tau _i\}_{i=1}^n$ , this coaction is uniquely determined by the coaction of $\hat u^{(1)}$ on this invariant subspace. In particular, the entries of $\hat u$ must be generated by the entries of $\hat u^{(1)}$ .

Consequently, ${\textrm{Aut}}^+Q_n$ is a quantum subgroup of $O_n^{-1}$ . Now it remains to prove the opposite inclusion.

Proof. We have to check that the images of the generators $\tau _i$ satisfy the generating relations. That is:

\begin{equation*}\alpha (\tau _i)^*=\alpha (\tau _i),\qquad \alpha (\tau _i)^2=1,\qquad \alpha (\tau _i)\alpha (\tau _j)=\alpha (\tau _j)\alpha (\tau _i).\end{equation*}

The first one is obvious as both $\tau _i$ and $v^j_i$ are self-adjoint. For the second, we have $\alpha (\tau _i)^2=\sum _{j,k}\tau _j\tau _k\otimes u^j_iu^k_i$ . While $\tau _j$ commutes with $\tau _k$ , we have that $u^j_i$ anticommutes with $u^k_i$ unless $j=k$ . So, the entries for $j\neq k$ subtract to zero and we are left with $\sum _j \tau _j\tau _j\otimes u^j_iu^j_i=1$ . Finally, the last one (assuming $i\neq j$ ) is again easy as we have $\alpha (\tau _i)\alpha (\tau _j)=\sum _{k,l}\tau _k\tau _l\otimes u^k_iu^l_j$ , where everything commutes (unless $k=l$ , but for those summands we have $\sum _k \tau _k\tau _k\otimes u^k_iu^k_j=0$ ).

It remains to show that $V_l$ are invariant subspaces. Take arbitrary element $\tau _{i_1}\cdots \tau _{i_l}\in V_l$ (assuming $i_{1} < \cdots < i_{l}$ ) and write explicitly

(3.2) \begin{equation} \alpha (\tau _{i_1}\cdots \tau _{i_l})=\sum _{j_1,\ldots,j_l=1}^n\tau _{j_1}\cdots \tau _{j_l}\otimes u^{i_1}_{j_1}\cdots u^{i_l}_{j_l}. \end{equation}

In the cases, where $j_a=j_b$ for some $a,b$ , the contribution of the sum must equal to zero since the corresponding $\tau _{j_a}$ and $\tau _{j_b}$ commute, while $u^{i_a}_{j_a}$ and $u^{i_b}_{j_b}$ anticommute. So, we are actually summing over elements $\tau _{j_1}\cdots \tau _{j_l}\in V_l$ only, which is what we wanted to prove.

This means that $O_n^{-1}$ is a quantum subgroup of ${\textrm{Aut}}^+Q_n$ , which finishes the proof that ${\textrm{Aut}}^+Q_n\simeq O_n^{-1}$ . Finally, from the explicit expression (3.2), it is clear that $O_n^{-1}$ acts on the invariant subspaces $V_l$ indeed through the representations $\hat u^{(l)}=v^{\mathop{\breve \wedge } l}$ .

5.1. Determining ${\textbf{Aut}}^+\frac{1}{2}\boldsymbol{Q}_{\boldsymbol{n}+1}$

We follow Algorithm 1. We start by computing the spectrum using equation (4.1):

\begin{equation*}\lambda _\mu =\sum _{i=1}^n\tau _\mu (\varepsilon _i)+\sum _{i < j}\tau _\mu (\varepsilon _i+\varepsilon _j)=\sum _i(\!-\!1)^{\mu _i}+\sum _{i < j}(\!-\!1)^{\mu _i+\mu _j}=l_\mu +\frac {1}{2}l_\mu ^2-\frac {n}{2},\end{equation*}

where $l_\mu =\sum _i(\!-\!1)^{\mu _i}=n-2\deg \mu$ . Note that the eigenvalue depends again only on the degree of $\mu$ (the number of non-zero entries). So, denote $\lambda _d\;:\!=\;\lambda _\mu$ for $d=\deg \mu$ . So, $\lambda _d=\frac{1}{2}(l_d^2+2l_d-n)$ with $l_d=n-2d$ . After some computation, one can find out that

\begin{equation*}\lambda _d=\frac {1}{2}\left ((2d-n-1)^2-n-1\right )\end{equation*}

In contrast with the computation for the hypercube $Q_n$ , the eigenvalues $\lambda _0,\ldots,\lambda _n$ are not distinct. Instead, $\lambda _d=\lambda _{n+1-d}$ . Consequently, the matrix $\hat A$ as an intertwiner does not imply that the subspaces $V_i\;:\!=\;\textrm{span}\{\tau _\mu \mid \deg \mu =i\}$ are invariant. Instead, we have the following invariant subspaces: $\tilde V_0\;:\!=\;V_0$ , $\tilde V_1\;:\!=\;V_1+ V_n$ , $\tilde V_2\;:\!=\;V_2+ V_{n+1}$ and so on. In general, $\tilde V_i=V_i+ V_{n+1-i}$ is an invariant subspace for every $i=0,\ldots,\lfloor \frac{n+1}{2}\rfloor$ (using the convention $V_{n+1}=\{0\}$ ).

In order to describe the invariant spaces, define $\tau _{n+1}\;:\!=\;\tau _1\cdots \tau _n$ . Then $\tau _1,\ldots,\tau _n$ , $\tau _{n+1}$ is the basis of $\tilde V_1$ . The basis of each $\tilde V_i$ is exactly the set $\{\tau _\alpha \}$ with $\alpha \in \mathbb Z_2^{n+1}$ , $\deg \alpha =i$ . Denote by $u$ the fundamental representation of ${\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ and by $\hat u^{(i)}$ the block of $\hat u=\mathcal{F}^{-1}u\mathcal{F}$ corresponding to the invariant subspace $\tilde V_i$ .

Obviously, $\tau _1,\ldots,\tau _{n+1}$ are also generators of $C(\frac{1}{2}Q_{n+1})=C(\mathbb Z_2^{n})$ (since already $\tau _1,\ldots,\tau _n$ are generators) and we can write the algebra by generators and relations as

\begin{equation*}C\!\left({ \dfrac {1}{2}}Q_{n+1}\right)=C^*(\tau _1,\ldots,\tau _{n+1}\mid \tau _i^2=1,\;\tau _i\tau _j=\tau _j\tau _i,\;\tau _i^*=\tau _i,\;\tau _1\cdots \tau _{n+1}=1).\end{equation*}

Proof. We follow the proof of Theorem 3.7. Let us first prove that $SO_{n+1}^{-1}\subset{\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ , that is, $SO_{n+1}^{-1}$ really acts on the halved hypercube. To do this, we are going to show that the mapping

\begin{equation*}\tau _j\mapsto \sum _{i=1}^{n+1}\tau _i\otimes u^i_j\end{equation*}

extends to a $*$ -homomorphism. Most of the work was already done in Lemma 3.11. It only remains to prove that the extra relation we have here $\tau _1\cdots \tau _{n+1}=1$ is also preserved under this action. That is, we need to show that

\begin{equation*}1=\sum _{i_1,\ldots,i_{n+1}=1}^{n+1}\tau _{i_1}\cdots \tau _{i_{n+1}}\otimes u_{i_11}\cdots u_{i_{n+1},n+1}\end{equation*}

This is indeed true thanks to the anticommutative determinant relation $u= 1$ .

Now for the converse direction, consider again the intertwiner and compute its restriction to $\tilde V_1$ . It is easy to check that we obtain the same formula

even on the “extended” space $\tilde V_1=V_1\oplus V_n$ (this is the point, where the assumption $n\neq 1,3$ is needed). Consequently, we have proven that $O_{n+1}^{-1}\supset{\textrm{Aut}}^+\frac{1}{2}Q_{n+1}$ .

Finally, it remains to find some intertwiner that would push us to the $SO_{n+1}^{-1}$ . Consider the block partition . The corresponding intertwiner is then of the form . We are interested in restriction of its Fourier transform on $\tilde V_1$ (more precisely, $\tilde V_1^{\otimes (n+1)}$ ):

This is exactly the antisymmetrizer $\breve{\mathcal{A}}_n\in \textrm{Mor}((\hat u^{(1)})^{\otimes n},1)$ , which exactly corresponds to the relation $\hat u^{(1)}=1$ .

5.2. Open problem

Let us finish this section with links to some open questions and related research. Note that there are free quantum analogues of the Coxeter groups of series $A$ (i.e. the symmetric groups $S_n$ ) and series $B$ or $C$ (i.e. the hyperoctahedral groups $H_n$ ), but so far we do not have any really free analogue of the Coxeter series $D$ (recall that series $D$ consists exactly of the symmetry groups of halved hypercubes $\frac{1}{2}Q_n$ ). The series of the anticommutative special orthogonal groups $SO_n^{-1}$ is a liberation of the Coxeter groups of type $D$ , but we should not call them free as they obey some sort of commutativity laws (namely the anticommutativity).

One particular candidate was recently discovered in [Reference Gromada15] for $n=4$ . For general $n$ , the question is still open. If some candidates appear, then the natural follow-up question would be: Is there some graph, whose quantum symmetry is this?

6.1. Determining ${\textbf{Aut}}^+\boldsymbol{FQ}_{\boldsymbol{n}+1}$

Let us now compute the eigenvalues of the adjacency matrix:

\begin{align*} \lambda _\mu &=\sum _{i=1}^n\tau _\mu (\varepsilon _i)+\tau _\mu (\iota )=\sum _{i=1}^n(\!-\!1)^{\mu _i}+(\!-\!1)^{\mu _1+\cdots +\mu _n}\\[5pt] &=n-2\deg \mu +(\!-\!1)^{\deg \mu }=n+1-4\lceil 1/2\,\deg \mu \rceil \end{align*}

Again, the eigenvalue depends only on the degree of $\mu$ , but again the values of $\lambda _d\;:\!=\;\lambda _\mu$ with $\deg \mu =d$ are not mutually distinct. In this case, we have $\lambda _{2d-1}=\lambda _{2d}$ . So, we have invariant subspaces $\tilde V_0\;:\!=\;V_0$ , $\tilde V_2\;:\!=\;V_1\oplus V_2$ and so on. That is, $\tilde V_{2i}=V_{2i-1}\oplus V_{2i}$ , $i=0,1,\ldots,\lceil n/2\rceil$ (with $\tilde V_{n+1}=V_n$ if $n$ is odd). Denoting by $u$ the fundamental representation of ${\textrm{Aut}}^+FQ_{n+1}$ , we denote by

\begin{equation*}\hat u=\hat u^{(0)}\oplus \hat u^{(2)}\oplus u^{(4)}\oplus \cdots \end{equation*}

the decomposition of its Fourier transform according to the invariant subspaces.

Denote $\tau _{n+1}\;:\!=\;1$ , so the elements $\tau _{ij}\;:\!=\;\tau _{ji}\;:\!=\;\tau _i\tau _j$ with $1\le i<j\le n+1$ form a basis of $\tilde V_2$ . In general, the basis of $\tilde V_{2i}$ is $(\tau _\alpha )$ with $\alpha \in \mathbb Z_2^{n+1}, \deg \alpha =2i$ . We can use the basis of $\tilde V_2$ as a generating set of $C(\mathbb Z_2^n)=C(FQ_{n+1})$ :

\begin{equation*}C(FQ_{n+1})=C^*\left (\tau _{ij},\;1\le i < j\le n+1\middle |\begin {matrix} \tau _{ij}^2=1,\;\tau _{ij}^*=\tau _{ij},\\[5pt] \tau _{ij}\tau _{kl}=\tau _{kl}\tau _{ij},\;\tau _{ij}\tau _{ik}=\tau _{jk}\end {matrix}\right ).\end{equation*}

Alternatively, one can view $C(FQ_{n+1})$ as the subalgebra of $C(\mathbb Z_2^{n+1})=C(Q_{n+1})$

\begin{equation*}C(Q_{n+1})=C^*(\tau _1,\ldots,\tau _{n+1}\mid \tau _i^2=1,\;\tau _i^*=\tau _i,\;\tau _i\tau _j=\tau _j\tau _i)\end{equation*}

generated by the elements $\tau _{ij}=\tau _{ji}=\tau _i\tau _j$ . This exactly corresponds to the fact that $FQ_{n+1}$ is a quotient graph of $Q_{n+1}$ .

Before proving this theorem, we need to do some preparatory work first. At this point, it is not even clear whether the prescribed representation $\bigoplus v^{\mathop{\breve \wedge } 2i}$ is a faithful representation of $PO_{n+1}^{-1}$ . We are actually going to prove that $v\mathop{\breve \wedge } v$ is a faithful representation. As a second step, we need to characterize $\mathscr{O}(PO_{n+1}^{-1})$ by generators and relations in terms of this representation $v\mathop{\breve \wedge } v$ . Equivalently, we need to find suitable generators of the representation category $\mathfrak{C}$ associated to $v\mathop{\breve \wedge } v$ . Only this allows us to use our standard machinery and prove Theorem 6.1.

This preparatory work is done in Section 6.2. The proof of Theorem 6.1 itself is then formulated in Section 6.3.

6.2. Projective version represented by exterior product

In Section 2.8, we defined the projective version of a compact matrix quantum group again as a compact matrix quantum group with the fundamental representation of the form $u\otimes u$ . In the classical case, we have also another faithful representation at our disposal.

Before formulating the proof, let us clarify the definition of projective groups. Our definition from Section 2.8 works for orthogonal groups only. For a general matrix group $G\subset GL_n$ , one typically defines its projective version to be the quotient $PG=G/\lambda I$ , $\lambda \in{\mathbb{C}}\setminus \{0\}$ (thus, in particular, $PGL_n=GL_n/Z(GL_n)$ ). Note that if $G$ is orthogonal, then $\lambda I\in G$ only for $\lambda =\pm 1$ . Therefore, assuming $G\subset O_n$ , our definition $PG=\{A\otimes A\mid A\in G\}$ is compatible with the general one (since we can reconstruct $A$ from $A\otimes A$ up to a global sign).

Finally, let us mention that over $\mathbb{C}$ , we obviously have $PGL_n=PSL_n$ , which is known to be a simple group, that is, it has no non-trivial normal subgroups.

Proof. Footnote ¹ Denote $V\;:\!=\;{\mathbb{C}}^n$ , so that $GL_n=GL(V)$ . Consider the homomorphism $\varphi \;:\; GL(V)\to GL(V\wedge V)$ mapping $A\mapsto A\wedge A$ . Since it maps multiples of identity to multiples of identity, it induces a homomorphism $\tilde \varphi \;:\; PGL(V)\to PGL(V\wedge V)$ . Since the $PGL(V)$ is simple (and the mapping $\tilde \varphi$ is obviously non-trivial), we must have that $\tilde \varphi$ is injective. Consequently, the kernel of $\varphi$ is contained in scalar matrices.

Now, we can restrict $\varphi$ to any subgroup $G\subset GL_n$ . Note that we can factor $\varphi$ as $\varphi \;:\; G\overset{\varphi _1}{\to } G'\overset{\varphi _2}{\to } G''$ , where $G'=\{A\otimes A\mid A\in G\}$ and $G''=\{A\wedge A\mid A\in G\}$ . We need to prove that $\varphi _2\;:\; G'\to G''$ is an isomorphism for $G\subset O_n$ as we have $G'\simeq PG$ in this case. Recall that we have the property $\ker \varphi \subset \{\lambda I\}$ . If $G\subset O_n$ , we must actually have $\ker \varphi \subset \{\pm I\}$ . But we know that $\ker \varphi _1=\{\pm I\}$ , and hence, $\varphi _2$ must indeed be an isomorphism.

It is known that the anticommutative orthogonal group can be obtained from the ordinary one by a 2-cocycle twist. Consequently, the two quantum groups are monoidally equivalent. More precisely, there exists a monoidal isomorphism of the corresponding representation categories $\textrm{Rep}\; O_n\to \textrm{Rep}\; O_n^{-1}$ mapping the fundamental representations one to another (i.e. there is also a monoidal isomorphism $\mathfrak{C}_{O_n}\to \mathfrak{C}_{O_n^{-1}}$ ). See for example [Reference Banica, Bichon and Collins7, Reference Gromada and Weber17]. This implies the following corollary.

Proof. Denote by $u$ the fundamental representation of $O_n$ . As mentioned above, there is a monoidal equivalence $\textrm{Rep}\; O_n\to \textrm{Rep}\; O_n^{-1}$ mapping $u\mapsto \breve u$ . It is easy to check that this monoidal equivalence also maps ${\mathcal{A}}_2^*{\mathcal{A}}_2\in \textrm{Mor}(u\otimes u,u\otimes u)$ to $\breve{\mathcal{A}}_2^*\breve{\mathcal{A}}_2\in \textrm{Mor}(\breve u\otimes \breve u,\breve u\otimes \breve u)$ . Consequently, it must map $u\wedge u$ to $\breve u\mathop{\breve \wedge }\breve u$ . Since the former is a faithful representation of $PO_n$ , the latter must be a faithful representation of $PO_n^{-1}$ .

In the following text, we will denote the projective orthogonal group represented by the matrix $u\wedge u$ by $\hat PO_n=(\mathscr{O}(PO_n),u\wedge u)$ . (The hat should remind us about the wedge product $\wedge$ .) Expressing the representation category $\mathfrak{C}_{\hat PO_n}$ in terms of the representation category $\mathfrak{C}_{O_n}$ is easy: We only have to compose all the intertwiners with the antisymmetrizer ${\mathcal{A}}_{2}\;:\; x\otimes y\mapsto x\wedge y$ . That is,

\begin{align*} \mathfrak{C}_{\hat PO_n}(k,l)&=\{{\mathcal{A}}_{(2)}^{\otimes l}T{\mathcal{A}}_{(2)}^{*\otimes k}\mid T\in \mathfrak{C}_{O_n}(2k,2l)\}\\[5pt] &=\{{\mathcal{A}}_{(2)}^{\otimes l}T_p{\mathcal{A}}_{(2)}^{*\otimes k}\mid p\in \mathsf{Pair}_n(2k,2l)\}, \end{align*}

where . (Pairing is a partition, where all blocks have size two. By an old result of Brauer [Reference Brauer11], this is exactly the category corresponding to the orthogonal group. See also e.g. [Reference Banica and Speicher12, Reference Weber31, Reference Gromada14].) However, the question is, what is the generating set of this category. Finding some small set of generators is actually not so easy as it may seem on the first sight.

In order to understand the following text, one needs to familiarize the category operations on linear categories of partitions (or at least the linear category of all pairings $\mathsf{Pair}_n$ ). The rough idea is that in order to perform the composition of two pairings, one should simply follow the lines and, if needed, replace all loops by the factor $n$ . We refer to [Reference Gromada and Weber16, Section 3] for more details.

In the following computations, we are going to treat the antisymmetrizer as a projection rather than a coisometry, so ${\mathcal{A}}_2^*={\mathcal{A}}_2$ . In this sense, it can be expressed in terms of partitions as . However, we are going to use a more convenient notation: In the diagrams, we will denote the antisymmetrizer by . So, for example, the antisymmetrization of will be denoted by , the antisymmetrization of the identity is . For any partition $p\in \mathscr{P}(2k,2l)$ , we are going to denote its antisymmetrization by . Consequently, we can write

(6.1) \begin{equation} \mathfrak{C}_{\hat PO_n}(k,l)=\{T_{{p}^{^{\!\!\!\circ}}}\mid p\in \mathsf{Pair}_n(2k,2l)\}, \end{equation}

so $\mathfrak{C}_{\hat PO_n}$ is modeled by a diagrammatic category $\mathsf{Pair}_n^\circ \;:\!=\;\{{p}^{^{\!\!\!\circ}}\mid p\in \mathsf{Pair}_n\}$ .

Before proving the theorem, let us mention two important Corollaries:

Proof. Follows directly from Theorem 6.4 and equation (6.1).

Proof. As we mentioned earlier, $O_n$ is monoidally equivalent with $O_n^{-1}$ , the monoidal equivalence maps the fundamental representation $u$ of $O_n$ to the fundamental representation $\breve u$ of $O_n^{-1}$ . As for the intertwiners, it maps $T_p\in \textrm{Mor}(u^{\otimes k},u^{\otimes l})$ for $p\in \mathsf{Pair}_n$ to $\breve T_p\in \textrm{Mor}(\breve u^{\otimes k},\breve u^{\otimes l})$ defined at the end of Section 2.4. The Corollary then follows by restricting the monoidal equivalence to the full subcategory $\mathfrak{C}_{PO_n}\subset \mathfrak{C}_{O_n}$ and applying to Corollary 6.5.

Now, we focus on the proof of Theorem 6.4. To make it easier to follow, we split it into several lemmata.

First, let us do a small remark on rotations in the category $\mathsf{Pair}_n^\circ$ . This category (as well as the category $\mathfrak{C}_{PO_n}$ ) is rigid and the duality morphism looks like this: . This again allows to do rotations in the category, but those rotations look a bit different than in the original category $\mathsf{Pair}_n$ . Consider some $p\in \mathscr{P}(2k,2l)$ . Let us call each pair of some $(2i+1)$ -st and $(2i+2)$ -nd point on either lower or upper row in $p$ a two-point. When drawing ${p}^{^{\!\!\!\circ}}$ , those two points are highlighted by the ellipse The element then allows to rotate those two points in ${p}^{^{\!\!\!\circ}}$ as a whole, not separately. For instance, rotating , we may obtain , but we cannot obtain . (The latter would actually equal to zero due to the antisymmetrization:

Proof. Denote by $\mathscr{C}$ the category generated by the given generators. Notice that we have the duality morphism among the generators, so $\mathscr{C}$ is a rigid category and we can consider everything up to rotation now. For instance, we could equivalently consider instead of or instead of in the generating set.

As the first step, we prove that ${p}^{^{\!\!\!\circ}}_k\in{\mathscr{C}}$ for every $k\in \mathbb N\setminus \{1\}$ , where . That is, $p_k$ is the rotation of $\sqcap ^{\otimes k}$ . We do this by induction. The ${p}^{^{\!\!\!\circ}}_k$ for $k=2,3,4,5$ are among the generators, so we have the initial step and a couple of others already by assumption. We construct any ${p}^{^{\!\!\!\circ}}_k$ by precomposing ${p}^{^{\!\!\!\circ}}_{k-1}$ with :

As the second step, we prove that ${p}^{^{\!\!\!\circ}}\in{\mathscr{C}}$ for every pairing $p\in \mathscr{P}_2(0,2k)$ . We use the element , which allows to permute the two points in ${p}^{^{\!\!\!\circ}}$ . We claim that any $p\in \mathscr{P}_2(0,2k)$ can be obtained by such two-point permutations from some ${p}^{^{\!\!\!\circ}}_{i_1}\otimes \cdots \otimes {p}^{^{\!\!\!\circ}}_{i_l}$ . Since we already proved that ${p}^{^{\!\!\!\circ}}_i\in{\mathscr{C}}$ for every $i>1$ and , this will finish the proof of the theorem. Note that thanks to the antisymmetrization, the order of the two points in a two-point is irrelevant (only affecting the $\pm$ sign).

So consider any $p\in \mathscr{P}_2(0,2k)$ . Take the first two-point and denote the corresponding points by $\textrm{pt}_1$ and $\textrm{pt}_2$ . Take the point which is paired with $\textrm{pt}_2$ and denote it by $\textrm{pt}_3$ . We denote by $\textrm{pt}_4$ its neighbor that form a two-point with $\textrm{pt}_3$ . Perform a two-point permutation of $p$ such that $(\textrm{pt}_3,\textrm{pt}_4)$ is the second two-point. Call $\textrm{pt}_5$ the point, which is paired with $\textrm{pt}_4$ and continue in this manner until we find some $\textrm{pt}_{2i_1}$ , which is paired with $\textrm{pt}_1$ . At this point, we have that ${p}^{^{\!\!\!\circ}}$ is a two-point permutation of ${p}^{^{\!\!\!\circ}}_{i_1}\otimes {q}^{^{\!\!\!\circ}}$ , where $q\in \mathscr{P}_2(0,2k-2i_1)$ . If we use mathematical induction, we may assume that $q$ is already a two-point permutation of $p_{i_2}\otimes \cdots \otimes p_{i_l}$ .

Proof. Denote by $\mathscr{C}$ the category generated by . Recall that is a rotation of . So, we can do the following computation in $\mathscr{C}$ :

By rotation, this means that $\mathscr{C}$ contains the linear combinations and . Now, we can do the following (we leave out the detailed computation now):

Subtracting , , , —those all being elements of $\mathscr{C}$ —we get that $\mathscr{C}$ must contain . Finally, squaring this element, we get

Doing all the possible subtractions and multiplying by 4, we get that $\mathscr{C}$ contains , where

\begin{equation*}\alpha =(n-8)^2(n-2)+8(n-8)=(n-4)(n-6)(n-8)\end{equation*}

Consequently, unless $n=4,6,8$ . Since we also proved that , we now have that .

Proof. First, we generate the following two elements of $\mathscr{C}$ :

(6.2)

(6.3)

Now, take the second element and permute the third and fourth two-point to obtain . Adding the element (6.2), we get

(6.4)

Now we go another way: Start with the element (6.2) and precompose it with . We obtain . Multiplying by four and adding (6.4), we finally get

Proof of Theorem 6.4 . Follows directly from the lemmata above. Lemma 6.8 tells us that and generate and . Lemma 6.9 shows that those together generate . Finally, Lemma 6.7 shows that all those together already generate the whole category $\mathsf{Pair}_n^\circ$ .

In the formulation of Theorem 6.4, we needed to make the assumption $n\neq 2,4,6,8$ . We can easily repair the formulation to include the cases $n=6,8$ as well. Notice that the only place, where we needed the assumption $n\neq 6,8$ was Lemma 6.8. So, we can modify the formulation of the theorem as follows:

We will actually need a slightly more technical result in the sequel.

Proposition 6.11. Consider $n\neq 2,4$ . Then the category $\mathsf{Pair}_n^\circ$ is generated by the set , where

(6.5)

Proof. We only need to show that the given intertwiners generate and . We do this by modifying the proof of Lemma 6.8.

In Lemma 6.8, we showed that actually generate the following elements (for which we did not yet need the assumption $n\neq 6,8$ ): The element A rotation of this one is the element . We also construct the element , which can be rotated into .

Subtracting those together with , from the element (6.5), we get that $\mathscr{C}$ contains . Consequently, it must contain both and (For $n=7$ , we can use Lemma 6.8 directly.)

Finally, let us reveal the meaning of the mysterious linear combination $p$ from equation (6.5). One can easily check that given a tuple of indices $i_1$ , $j_1$ , $i_2$ , $j_2$ , $i_3$ , $j_3$ , $i_4$ , $j_4$ such that $i_k\neq j_k$ , we have

(6.6) \begin{equation} [\breve T_p^{(n)}]^{(i_1,j_1),(i_2,j_2),(i_3,j_3),(i_4,j_4)}=\begin{cases}1&\textrm{if the indices can be paired}\\[5pt] 0&\textrm{otherwise}\end{cases} \end{equation}

Indeed, the individual partitions just depict the ways of how the indices can be paired. (The minus signs are there because of the crossings to compensate the minus sign given by the deformed functor $\breve T^{(n)}$ .)

Thus, we have the following Corollary.

6.3. Proof of Theorem 6.1

Denote by $v$ the fundamental representation of $O_{n+1}^{-1}$ . Theorem 6.1 says that ${\textrm{Aut}}^+FQ_n$ is isomorphic with $PO_{n+1}^{-1}$ acting through $u$ with $\hat u=\bigoplus v^{\mathop{\breve \wedge } 2i}$ . First step of the proof was provided by Corollary 6.3, where we showed that $v\mathop{\breve \wedge } v$ is a faithful representation of $PO_{n+1}^{-1}$ , and hence, the whole $\bigoplus v^{\mathop{\breve \wedge } 2i}$ must be a faithful representation.

Secondly, we show that $PO_{n+1}^{-1}$ acts on $FQ_{n+1}$ , which then implies that $PO_{n+1}^{-1}\subset{\textrm{Aut}}^+ FQ_{n+1}$ . But there is no work to be done here as this is just a restriction of the action of $O_{n+1}^{-1}$ on $Q_{n+1}$ . Indeed, recall that we have the coaction $\alpha \;:\; C(Q_{n+1})\to C(Q_{n+1})\otimes \mathscr{O}(O_{n+1}^{-1})$ by $\tau _j\mapsto \sum _{i=1}^n \tau _i v^i_j$ and that $C(FQ_{n+1})$ is the subalgebra of $C(Q_{n+1})$ generated by even polynomials in $\tau _j$ . Restricting to this subalgebra, we get exactly the desired coaction $C(FQ_{n+1})\to C(FQ_{n+1})\otimes \mathscr{O}(PO_{n+1}^{-1})$ .

Finally, we need to prove the converse inclusion ${\textrm{Aut}}^+ FQ_{n+1}\subset PO_{n+1}^{-1}$ . So, we need to show that $\hat u^{(2)}$ is a representation of $PO_{n+1}^{-1}$ . Assume for a moment that $n+1\neq 2,4,6,8$ . Thanks to Corollary 6.6, we only need to show that and are intertwiners of $\hat u^{(1)}$ . The first one is just the orthogonality, which is automatic as Fourier transform preserves orthogonality. The second one is easy to obtain by looking at the Fourier transform of projected to $\tilde V_2$ . Its entries are then

Note that due to the antisymetrization, we need to also assume $i_1\neq j_1$ , $i_2\neq j_2$ , and $i_3\neq j_3$ . We claim that this exactly matches the intertwiner . Indeed, the latter is just a symmetrization of . It is clear that the only way how to pair a tuple of indices $i_1\neq j_1$ , $i_2\neq j_2$ , $i_3\neq j_3$ is according to the partition (up to symmetrization, i.e. permuting neighboring pairs of points). This finishes the proof for the case $n\neq 6,8$ .

For the cases $n=6,8$ , consider the intertwiner of $\hat u^{(1)}$ induced by Again, the entries of are zeros and ones depending on whether the indices can be paired or not. That is, , where $\breve T^{(n+1)}_p$ is given by equation (6.6). Thus, the result follows from Corollary 6.12.

6.4. Open problem

Let us again finish with some open problem. The hyperoctahedral group $H_n$ can be seen not only as the symmetry group of the hypercube $Q_n$ but also as the symmetry group of $n$ copies of a segment $K_2\sqcup \cdots \sqcup K_2$ . While the quantum symmetry of the former is $O_n^{-1}$ , the quantum symmetry of the latter is $H_n^+$ , which are two distinct quantum groups. We have just proven that $PO_n^{-1}$ is the quantum symmetry of the folded hypercube $FQ_n$ . This result suggests the following question:

This is related to a big question on whether there is a quantum analogue of the Frucht theorem, which was discussed recently in [Reference Banica and McCarthy10].

7.1. Full graph

As we just mentioned, a special case for $n=1$ is the full graph $K_m$ . Of course, we know that the quantum symmetry group of the full graph is the free symmetric quantum group $S_m^+$ . Nevertheless, we would like to use this simple example to point out a certain subtlety that one needs to keep in mind when working with cyclic groups $\mathbb Z_m$ for $m\neq 2$ .

So, the full graph $K_m$ is the Cayley graph corresponding to the group $\mathbb Z_m$ and the generating set consisting of all elements of the group except for identity, so $K_m=\textrm{Cay}(\mathbb Z_m,\mathbb Z_m\setminus \{0\})$ . We denote simply by $a=0,\ldots,m-1$ the elements of $\mathbb Z_m$ and by $\tau _a\in \textrm{Irr}\;\mathbb Z_m$ the characters $\tau _a(b)=\gamma ^{ab}$ , where $\gamma$ is some primitive $m$ th root of unity. The spectrum of $K_m$ is hence computed as

\begin{equation*}\lambda _a=\sum _{b=1}^{m-1}\tau _a(b)=\sum _{b=1}^{m-1}\gamma ^{ab}= \begin {cases} m-1&a=0,\\[5pt] -1&\text {otherwise.} \end {cases}\end{equation*}

Now comes the important point we wanted to make in this subsection: The Fourier transform $\mathcal{F}$ on $\mathbb Z_m$ , that is, the transformation of the bases $(\delta _a) \to (\tau _a)$ is unitary, but not orthogonal! Its entries are $[\mathcal{F}]^a_b=\gamma ^{ab}$ , so they are obviously not real (unless $m=2$ ). To be more concrete, the basis elements $\tau _a$ , which are the columns of $\mathcal{F}$ are not self-adjoint, but satisfy $\tau _a^*=\tau _{m-a}$ .

Consequently, if we denote $\hat S_m\;:\!=\;\mathcal{F}^{-1}S_m\mathcal{F}$ and $\hat S_m^+\;:\!=\;\mathcal{F}^{-1}S_m^+\mathcal{F}$ the symmetric group and the free symmetric quantum group represented by the Fourier transform of the standard permutation matrices, then those matrix (quantum) groups are not orthogonal. Instead, they satisfy $\hat S_m\subset \hat S_m^+\subset O^+(F)\subset U_m^+$ with $F\in M_m({\mathbb{C}})$ defined by $F^a_b=\delta _{a+b,m}$ (indices modulo $m$ ). That is, $u^{a\,*}_b=u^{m-a}_{m-b}$ . (Here, $U_n^+$ denotes the free unitary quantum group [Reference Wang29].)

Therefore, if we study the intertwiners of $\hat S_m\simeq{\textrm{Aut}}^+ K_m$ in this basis, then instead of the familiar maps such as $T^{(m)}_{\sqcap }$ , , , we discover their Fourier transforms, which may look rather exotic.

Observation 7.2. The category $\mathfrak{C}_{\hat S_m}$ is generated by $\hat T^{(m)}_{\sqcap }$ and , where

7.2. Wreath product of quantum groups

We should also explain, what does the $\wr$ sign in the formulation of Theorem 7.1 means. It is not the free wreath product of quantum groups, but the classical one. Before specifying, what we mean by a classical wreath product of quantum groups, let us recall the free definition by Bichon [Reference Bichon9].

Definition 7.3. Let $G\subset U_m^+$ be a quantum group with fundamental representation $v=(v^a_b)$ and let $H\subset S_n^+$ be a quantum permutation group with fundamental representation $w=(w^i_j)$ . Then we define the free wreath product of $G$ and $H$ to be the quantum group

\begin{equation*}G\wr _* H\;:\!=\;(\mathscr {O}(G)^{* n}* \mathscr {O}(H),u),\quad \text {where}\quad u^{ai}_{bj}=v^{ai}_bw^i_j,\end{equation*}

where we denote by $v^i=(v^{ai}_b)_{a,b}$ the fundamental representations of the $n$ copies of $G$ occurring in the definition of $G\wr _* H$ .

Now the classical wreath product is supposed to be given by passing from the free product to the tensor product. So, define $\mathscr{O}(G\wr H)\;:\!=\;\mathscr{O}(G)^{\otimes n}\otimes \mathscr{O}(H)$ .

Proof. Denote $\Delta '\;:\!=\;(q\otimes q)\circ \Delta$ , where $q$ is the projection $\mathscr{O}(G\wr _*H)\to \mathscr{O}(G\wr H)$ . We only need to prove that $\Delta '(v^{ai}_b)\Delta '(v^{cj}_d)=\Delta '(v^{cj}_d)\Delta '(v^{ai}_b)$ whenever $i\neq j$ and $\Delta '(v^{ai}_b)\Delta '(w^k_l)=\Delta '(w^k_l)\Delta '(v^{ai}_b)$ . Both are quite straightforward. Let’s have a look on the first one:

\begin{equation*}\Delta '(v^{ai}_b)\Delta '(v^{cj}_d)=\sum _{x,k,y,l}v^{ai}_xw^i_kv^{cj}_yw^j_l\otimes v^{xk}_bv^{yl}_d\end{equation*}

Now, notice that the factors in the left $\otimes$ -factor can be arbitrarily permuted. Assuming $k\neq l$ , the same holds for the right $\otimes$ -factor. For $k=l$ , we have $w^i_kw^j_l=0$ , so the left $\otimes$ -factor equals to zero. Consequently, we see that the coproducts indeed commute as we needed. The second condition is proven the same way using the fact that $\Delta (w^i_j)=\sum _k w^i_k\otimes w^k_j$ .

7.3. Cartesian product of graphs

Given two graphs $X_1$ and $X_2$ , we define their Cartesian product to be the graph $X_1\mathrel{\square } X_2$ with the vertex set $V(X_1\mathrel{\square } X_2)=V(X_1)\times V(X_2)$ and with an edge $((v_1,v_2),(w_1,w_2))\in E(X_1\mathrel{\square } X_2)$ if and only if $(v_1,w_1)\in E(X_1)$ and $v_2=w_2$ or if $(v_2,w_2)\in E(X_2)$ and $v_1=w_1$ . Alternatively, we can describe the Cartesian product by its adjacency matrix $A_{X_1\mathrel{\square } X_2}=A_{X_1}\otimes I_{X_2}+I_{X_1}\otimes A_{X_2}$ , where $I_{X_i}$ denotes the identity matrix.

The Cartesian product of graphs is associative and we can conveniently describe the product of $n$ given graphs by the adjacency matrix

\begin{equation*}A_{X_1\mathrel {\square }\cdots \mathrel {\square } X_n}=A_{X_1}\otimes I_{X_2}\otimes I_{X_3}\otimes \cdots \otimes I_{X_n}+I_{X_1}\otimes A_{X_2}\otimes I_{X_3}\otimes \cdots \otimes I_{X_n}+\cdots \end{equation*}

It is well known that if $G$ acts on a finite space or a graph $X$ by $\delta _a\mapsto \sum _b\delta _b\otimes v^b_a$ , then $G\wr S_n$ acts on the $n$ -fold disjoint union $X\sqcup \cdots \sqcup X$ by $\delta _{ai}\mapsto \sum _{b,j}\delta _{bj}\otimes u^{bj}_{ai}$ . (Notice that $C(X\sqcup \cdots \sqcup X)=C(X)\oplus \cdots \oplus C(X)$ ; the indices $i,j$ are indexing the $n$ copies of $X$ or $C(X)$ here.)

Now, consider the Cartesian product $X\mathrel{\square }\cdots \mathrel{\square } X$ . In this case, we have $C(X\mathrel{\square }\cdots \mathrel{\square } X)=C(X)\otimes \cdots \otimes C(X)$ . Consider a basis $(x_i)_{i=0}^{m-1}$ of $C(X)$ such that $x_0=1_{C(X)}$ (if $X$ is a regular graph, then we can consider the basis of eigenvectors of $A_X$ ). Denote by $\hat v^a_b$ the entries of the action of $G$ on $X$ in this basis, so $x_a\mapsto \sum _bx_b\otimes \hat v^b_a$ . Denote $x_{ai}\;:\!=\;1_{C(X)}\otimes \cdots \otimes 1_{C(X)}\otimes x_a\otimes 1_{C(X)}\otimes \cdots \otimes 1_{C(X)}$ , where the $x_a$ is on the $i$ th place. In the following we are going to prove that $x_{ai}\mapsto \sum _{b,j}x_{bj}\otimes \hat u^{bj}_{ai}$ extends to an action of $G\wr S_n$ on $X\mathrel{\square }\cdots \mathrel{\square } X$ , where $\hat u^{bj}_{ai}=\hat v^{bj}_aw^j_i$ .

First, assume for a moment that this action really exists. Then it is easy to determine, how it must act on the basis $x_{a_1,\ldots,a_n}\;:\!=\;x_{a_1}\otimes \cdots \otimes x_{a_n}$ of $C(X\mathrel{\square }\cdots \mathrel{\square } X)$ :

\begin{align*} x_{a_1,\ldots,a_n} &\mapsto \sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{k_1,\ldots,k_n=1}^n x_{b_1k_1}\cdots x_{b_nk_n}\otimes \hat u^{b_1k_1}_{a_11}\cdots \hat u^{b_nk_n}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_1\sigma (1)}\cdots x_{b_n\sigma (n)}\otimes \hat u^{b_1\sigma (1)}_{a_11}\cdots \hat u^{b_n\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_{\sigma ^{-1}(1)}1}\cdots x_{b_{\sigma ^{-1}(n)}n}\otimes \hat u^{b_1\sigma (1)}_{a_11}\cdots \hat u^{b_n\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}\sum _{\sigma \in S_n} x_{b_11}\cdots x_{b_nn}\otimes \hat u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots \hat u^{b_{\sigma (n)}\sigma (n)}_{a_nn}\\[5pt] &=\sum _{b_1,\ldots,b_n=0}^{m-1}x_{b_1,\ldots,b_n}\otimes \hat{\tilde u}^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}, \end{align*}

where $\hat{\tilde u}^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}=\sum _{\sigma \in S_n}\hat u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots \hat u^{b_{\sigma (n)}\sigma (n)}_{a_nn}$ . We can also change the basis to the standard one and obtain $\delta _{a_1,\ldots,a_n}\mapsto \sum _{b_1,\ldots,b_n}\delta _{b_1,\ldots,b_n}\otimes \tilde u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}$ , where $\tilde u$ is given by a formula analogous to the one for $\hat{\tilde u}$ .

Lemma 7.7. Let $G$ be a compact matrix quantum group with fundamental representation $v$ . Then

\begin{equation*}\tilde u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n} \;:\!=\;\sum _{\sigma \in S_n}u^{b_{\sigma (1)}\sigma (1)}_{a_11}\cdots u^{b_{\sigma (n)}\sigma (n)}_{a_nn} =\sum _{k_1,\ldots,k_n=1}^nu^{b_{k_1}k_1}_{a_11}\cdots u^{b_{k_n}k_n}_{a_nn}\end{equation*}

is a representation of $G\wr S_n$ . If $G\subset S_m^+$ , then $\tilde u$ is faithful.

Proof. First, we should prove the second equality in the formula. To see this, it is enough to notice that the product $u^{b_{k_1}k_1}_{a_11}\cdots u^{b_{k_n}k_n}_{a_nn}$ equals to zero whenever $k_i=k_j$ for some $i\neq j$ (since $w^{k_i}_iw^{k_j}_j=0$ ).

Proving that $\tilde u$ is a representation of $G\wr S_n$ is a straightforward computation:

\begin{align*} \Delta (u^{b_1,\ldots,b_n}_{a_1,\ldots,a_n}) &=\sum _{\sigma \in S_n}\Delta (u^{b_{\sigma (1)}\sigma (1)}_{a_11})\cdots \Delta (u^{b_{\sigma (n)}n}_{a_nn})\\[5pt] &=\sum _{\sigma \in S_n}\sum _{\substack{c_1,\ldots,c_n\\ k_1,\ldots,k_n}}u^{b_{\sigma (1)}\sigma (1)}_{c_1k_1}\cdots u^{b_{\sigma (n)}\sigma (n)}_{c_nk_n}\otimes u^{c_1k_1}_{a_11}\cdots u^{c_nk_n}_{a_nn}\\[5pt] &=\sum _{d_1,\ldots,d_n}\sum _{\pi,\rho \in S_n}u^{b_{\rho (1)}\rho (1)}_{d_11}\cdots u^{b_{\rho (n)}\rho (n)}_{d_nk_n}\otimes u^{d_1\pi (1)}_{a_11}\cdots u^{d_n\pi (n)}_{a_nn}\\[5pt] &=\sum _{d_1,\ldots,d_n}u^{b_1,\ldots,b_n}_{d_1,\ldots,d_n}\otimes u^{d_1,\ldots,d_n}_{a_1,\ldots,a_n} \end{align*}

To get from the second to the third line, we need to notice several things: First, as we already mentioned, the product $u^{c_1k_1}_{a_11}\cdots u^{c_nk_n}_{a_nn}$ equals to zero unless $k_1,\ldots,k_n$ is a permutation of $1,\ldots,n$ . Hence, we can denote this permutation by $\pi$ , so $k_i=\pi (i)$ . Secondly, the terms of the product mutually commute, so we can reorder the first product as $u^{b_{\sigma (1)}\sigma (1)}_{c_1k_1}\cdots u^{b_{\sigma (n)}\sigma (n)}_{c_nk_n}=u^{b_{\sigma (\pi ^{-1}(1))}\sigma (\pi ^{-1}(1))}_{c_{\pi ^{-1}(1)}1}\cdots u^{b_{\sigma (\pi ^{-1}(n))}\sigma (\pi ^{-1}(n))}_{c_{\pi ^{-1}(n)}n}$ . Finally, we denote $\rho \;:\!=\;\sigma \circ \pi ^{-1}$ and $d_i\;:\!=\;c_{\pi ^{-1}(i)}$ .

Assume now that $G\subset S_m$ for some $m$ . The proof of the last statement—that $\tilde u$ is faithful—gets a bit easier if we work in the basis $(x_a)_{a=0}^{m-1}$ of $C(X)$ such that $x_0=1_{C(X)}$ since $x_0$ is an invariant vector of $v$ . So denote by $\hat v^a_b$ the entries of $v$ in the basis $(x_a)$ and similarly $\hat u^{ai}_{bj}\;:\!=\;\hat v^{ai}_bw^i_j$ . We have then $\hat v^0_0=1$ and $\hat v^0_b=0=\hat v^a_0$ for every $a$ , $b$ . We need to show that the entries of $\hat{\tilde u}$ already generate the whole algebra $\mathscr{O}(G\wr S_n)$ . Of course, it is enough to show that it generates the generators $\hat v^{ai}_b$ and $w^i_j$ . We claim that $\hat{\tilde u}^{0,\ldots,0,a,0,\ldots,0}_{0,\ldots,0,b,0,\ldots,0}=\hat u^{ai}_{bj}$ , where the $a$ is on the $i$ th position and the $b$ is on the $j$ th position on the left-hand side. Indeed, we get

(7.1) \begin{equation} \hat{\tilde u}^{0,\ldots,0,a,0,\ldots,0}_{0,\ldots,0,b,0,\ldots,0}=\sum _{\substack{k_1,\ldots,k_n=1\\ \textrm{except for $k_j\;:\!=\;i$}}}^n \hat v^{ai}_b\,w^{k_1}_1\cdots w^{k_n}_n=\hat v^{ai}_bw^i_j=\hat u^{ai}_{bj}. \end{equation}

Proof. Notice that we can express $\tilde u$ in a more “matricial way”

\begin{equation*}\tilde u=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}\otimes \cdots \otimes v^{\sigma (n)})\delta _\sigma,\end{equation*}

where $T_\sigma \;:\; ({\mathbb{C}}^m)^{\otimes n}\to ({\mathbb{C}}^m)^{\otimes n}$ is the linear operator permuting the tensor factors according to $\sigma$ and $\delta _{\sigma }\;:\!=\;w_1^{\sigma (1)}\cdots w_n^{\sigma (n)}$ (it is actually indeed the delta the delta function $S_n\to{\mathbb{C}}$ mapping $\delta _\sigma (\pi )=\delta _{\sigma \pi }$ ). We will use this matrix approach throughout the proof, but one could of course also rewrite the computation in terms of the matrix entries.

We want to show that $({\textrm{Aut}}^+\Gamma )\wr S_n$ represented by the faithful representation $\tilde u$ is a quantum subgroup of ${\textrm{Aut}}^+(\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma )$ . To do this, we need to show that the representation category associated to $\tilde u$ contains the generators of the category $\mathfrak{C}_{{\textrm{Aut}}^+(\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma )}$ , which are $T_{\uparrow }^{(m^n)}$ , , and $\tilde A$ , where $\tilde A$ is the adjacency matrix of $\Gamma \mathrel{\square }\cdots \mathrel{\square }\Gamma$ .

We start with the singleton $T^{(m^n)}_{\uparrow }$ , which is the easiest one. Notice first that $T_{\uparrow }^{(m^n)}=T_{\uparrow }^{(m)}\otimes \cdots \otimes T_{\uparrow }^{(m)}$ . Consequently,

\begin{align*} \tilde{u}T_{\uparrow }^{(m^n)} &=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}\otimes \cdots \otimes v^{\sigma (n)})T_{\uparrow }^{(m^n)}\delta _\sigma \\[5pt] &=\sum _{\sigma \in S_n}T_\sigma (v^{\sigma (1)}T_{\uparrow }^{(m)}\otimes \cdots \otimes v^{\sigma (n)}T_{\uparrow }^{(m)})\delta _\sigma \\[5pt] &=\sum _{\sigma \in S_n}T_\sigma (T_{\uparrow }^{(m)}\otimes \cdots \otimes T_{\uparrow }^{(m)})\delta _\sigma =T_{\uparrow }^{(m^n)}, \end{align*}

where we used the fact that $\sum _{\sigma \in S_n}\delta _\sigma =1_{C(S_n)}$ .

To show the second intertwiner relation, denote by $R$ the natural “disentangling operator” $({\mathbb{C}}^m\otimes{\mathbb{C}}^m)^{\otimes n}\to ({\mathbb{C}}^m)^{\otimes n}\otimes ({\mathbb{C}}^m)^{\otimes n}$ mapping $(x_1\otimes y_1)\otimes \cdots \otimes (x_n\otimes y_n)\mapsto (x_1\otimes \cdots \otimes x_n)\otimes (y_1\otimes \cdots \otimes y_n)$ . Then we can write So,

Finally, we prove that $\tilde u$ commutes with $\tilde A\;:\!=\;\sum _{i=1}^n \textrm{id}\otimes \cdots \otimes \textrm{id}\otimes A\otimes \textrm{id}\otimes \cdots \otimes \textrm{id}$ , where $A$ is the adjacency matrix of $\Gamma$ and in each summand it appears at the $i$ th factor of the tensor product.