15a. Orbits, orbitals

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

We have seen in chapter 14 how to develop the basic theory of quantum symmetry groups of graphs [math]G^+(X)[/math], with this corresponding more or less to the knowledge of the subject from the mid to the end 00s. Many things have happened since, and in the remainder of this book we will attempt to navigate the subject, with some basics.

In the present chapter we would like to discuss a number of more advanced techniques for the computation of [math]G^+(X)[/math]. More specifically, we would like to talk about:

(1) The orbits and orbitals of subgroups [math]G\subset S_N^+[/math], the point here being that an action [math]G\curvearrowright X[/math] is possible when the adjacency matrix of [math]X[/math] is constant on the orbitals of [math]G[/math]. This is a key observation of Lupini, Man\v cinska and Roberson , heavily used ever since.

(2) The study of dual quantum groups [math]\widehat{\Gamma}\subset S_N^+[/math], and their actions on graphs [math]\widehat{\Gamma}\curvearrowright X[/math], when [math]\Gamma[/math] is finite, or classical, or arbitrary. Here the main ideas, which are actually related to the orbit and orbital problematics, are due to Bichon and McCarthy .

(3) The quantum group actions [math]G\curvearrowright X[/math] on graphs which are circulant, [math]\mathbb Z_N\curvearrowright X[/math], or more generally which admit an action of a finite abelian group, [math]A\curvearrowright X[/math]. There is a lot of Fourier magic here, first discussed in my paper with Bichon and Chenevier .

(4) The construction and main properties of the quantum semigroup of quantum partial isometries [math]\widetilde{G}^+(X)\subset\widetilde{S}_N^+[/math], in analogy with what we know about [math]\widetilde{G}(X)\subset\widetilde{S}_N[/math]. This is something more recent, not yet truly developed, and believed to be of interest.

So, this will be the plan for the present chapter, obviously many interesting things to be discussed, and I can only imagine that you are quite excited about this. Unfortunately, there is no easy way of compacting 20 years of math into one chapter, and we have: \begin{disclaimer} Contrary to the previous chapters, where new theory was accompanied by decent theorems using it, here we will be rather theoretical, explaining what is needed to know, in order to read the recent papers on the subject, and their theorems. \end{disclaimer} And as a second disclaimer, this will be just half of the story, because we will still have to talk afterwards about planar algebra methods, which are actually things known since the early and mid 00s. We will do this in chapter 16 below.

But probably too much talking, leaving aside all this arithmetics of knowledge, let us get to work, according to our (1,2,3,4) plan above, for the present chapter.

To start with, a useful tool for the study of the permutation groups [math]G\subset S_N[/math] are the orbits of the action [math]G\curvearrowright\{1,\ldots,N\}[/math]. In the quantum permutation group case, [math]G\subset S_N^+[/math], following Bichon , the orbits can be introduced as follows:

Theorem

Given a closed subgroup [math]G\subset S_N^+[/math], with standard coordinates denoted [math]u_{ij}\in C(G)[/math], the following defines an equivalence relation on [math]\{1,\ldots,N\}[/math],

[[math]] i\sim j\iff u_{ij}\neq0 [[/math]]

that we call orbit decomposition associated to the action [math]G\curvearrowright\{1,\ldots,N\}[/math]. In the classical case, [math]G\subset S_N[/math], this is the usual orbit equivalence.

Show Proof

We first check the fact that we have indeed an equivalence relation. The reflexivity axiom [math]i\sim i[/math] follows by using the counit, as follows:

[[math]] \varepsilon(u_{ii})=1 \implies u_{ii}\neq0 [[/math]]

The symmetry axiom [math]i\sim j\implies j\sim i[/math] follows by using the antipode:

[[math]] S(u_{ji})=u_{ij}\implies[u_{ij}\neq0\implies u_{ji}\neq0] [[/math]]

As for the transitivity axiom [math]i\sim k,k\sim j\implies i\sim j[/math], this follows by using the comultiplication, and positivity. Consider indeed the following formula:

[[math]] \Delta(u_{ij})=\sum_ku_{ik}\otimes u_{kj} [[/math]]

On the right we have a sum of projections, and we obtain from this, as desired:

[[math]] \begin{eqnarray*} u_{ik}\neq0,u_{kj}\neq0 &\implies&u_{ik}\otimes u_{kj} \gt 0\\ &\implies&\Delta(u_{ij}) \gt 0\\ &\implies&u_{ij}\neq0 \end{eqnarray*} [[/math]]

Finally, in the classical case, where [math]G\subset S_N[/math], the standard coordinates are:

[[math]] u_{ij}=\chi\left(\sigma\in G\Big|\sigma(j)=i\right) [[/math]]

Thus [math]u_{ij}\neq0[/math] means that [math]i,j[/math] must be in the same orbit, as claimed.

■

Generally speaking, the theory from the classical case extends well to the quantum group setting, and we have in particular the following result, also from :

Theorem

Given a closed subgroup [math]G\subset S_N^+[/math], with magic matrix [math]u=(u_{ij})[/math], consider the associated coaction map, on the space [math]X=\{1,\ldots,N\}[/math]:

[[math]] \Phi:C(X)\to C(X)\otimes C(G)\quad,\quad e_i\to\sum_je_j\otimes u_{ji} [[/math]]

The following three subalgebras of [math]C(X)[/math] are then equal,

[[math]] Fix(u)=\left\{\xi\in C(X)\Big|u\xi=\xi\right\} [[/math]]

[[math]] Fix(\Phi)=\left\{\xi\in C(X)\Big|\Phi(\xi)=\xi\otimes1\right\} [[/math]]

[[math]] Fix(\sim)=\left\{\xi\in C(X)\Big|i\sim j\implies \xi_i=\xi_j\right\} [[/math]]

where [math]\sim[/math] is the orbit equivalence relation constructed in Theorem 15.2.

Show Proof

The fact that we have [math]Fix(u)=Fix(\Phi)[/math] is standard, with this being valid for any corepresentation [math]u=(u_{ij})[/math]. Indeed, we first have the following computation:

[[math]] \begin{eqnarray*} \item[a]i\in Fix(u) &\iff&u\xi=\xi\\ &\iff&(u\xi)_j=\xi_j,\forall j\\ &\iff&\sum_iu_{ji}\xi_i=\xi_j,\forall j \end{eqnarray*} [[/math]]

On the other hand, we have as well the following computation:

[[math]] \begin{eqnarray*} \item[a]i\in Fix(\Phi) &\iff&\Phi(\xi)=\xi\otimes1\\ &\iff&\sum_i\Phi(e_i)\xi_i=\xi\otimes1\\ &\iff&\sum_{ij}e_j\otimes u_{ji}\xi_i=\sum_je_j\otimes\xi_j\\ &\iff&\sum_iu_{ji}\xi_i=\xi_j,\forall j \end{eqnarray*} [[/math]]

Thus we have [math]Fix(u)=Fix(\Phi)[/math], as claimed. Regarding now the equality of this algebra with [math]Fix(\sim)[/math], observe first that given a vector [math]\xi\in Fix(\sim)[/math], we have:

[[math]] \begin{eqnarray*} \sum_iu_{ji}\xi_i &=&\sum_{i\sim j}u_{ji}\xi_i\\ &=&\sum_{i\sim j}u_{ji}\xi_j\\ &=&\sum_iu_{ji}\xi_j\\ &=&\xi_j \end{eqnarray*} [[/math]]

Thus [math]\xi\in Fix(u)=Fix(\Phi)[/math]. Finally, for the reverse inclusion, we know from Theorem 15.2 that the magic unitary [math]u=(u_{ij})[/math] is block-diagonal, with respect to the orbit decomposition there. But this shows that the algebra [math]Fix(u)=Fix(\Phi)[/math] decomposes as well with respect to the orbit decomposition, so in order to prove the result, we are left with a study in the transitive case. More specifically we must prove that if the action is transitive, then [math]u[/math] is irreducible, and this being clear, we obtain the result. See .

■

We have as well a useful analytic result, as follows:

Theorem

Given a closed subgroup [math]G\subset S_N^+[/math], the matrix

[[math]] P_{ij}=\int_Gu_{ij} [[/math]]

is the orthogonal projection onto [math]Fix(\sim)[/math], and determines the orbits of [math]G\curvearrowright\{1,\ldots,N\}[/math].

Show Proof

This follows from Theorem 15.3, and from the standard fact, coming from Peter-Weyl theory, that [math]P[/math] is the orthogonal projection onto [math]Fix(u)[/math].

■

As an application of the above, let us discuss now the notion of transitivity. We have here the following result, once again coming from :

Theorem

For a closed subgroup [math]G\subset S_N^+[/math], the following are equivalent:

• [math]G[/math] is transitive, in the sense that [math]i\sim j[/math], for any [math]i,j[/math].
• [math]Fix(u)=\mathbb C\xi[/math], where [math]\xi[/math] is the all-one vector.
• [math]\int_Gu_{ij}=\frac{1}{N}[/math], for any [math]i,j[/math].

In the classical case, [math]G\subset S_N[/math], this is the usual notion of transitivity.

Show Proof

This is well-known in the classical case. In general, the proof is as follows:

[math](1)\iff(2)[/math] We use the standard fact that the fixed point space of a corepresentation coincides with the fixed point space of the associated coaction:

[[math]] Fix(u)=Fix(\Phi) [[/math]]

As explained in the beginning of this chapter, the fixed point space of the magic corepresentation [math]u=(u_{ij})[/math] has the following interpretation, in terms of orbits:

[[math]] Fix(u)=\left\{\xi\in C(X)\Big|i\sim j\implies \xi(i)=\xi(j)\right\} [[/math]]

In particular, the transitivity condition corresponds to [math]Fix(u)=\mathbb C\xi[/math], as stated.

[math](2)\iff(3)[/math] This is clear from the general properties of the Haar integration, and more precisely from the fact that [math](\int_Gu_{ij})_{ij}[/math] is the projection onto [math]Fix(u)[/math].

■

Following Lupini, Man\v cinska and Roberson , let us discuss now the higher orbitals. Things are quite tricky here, and we have the following result, to start with:

Theorem

For a closed aubgroup [math]G\subset S_N^+[/math], with magic unitary [math]u=(u_{ij})[/math], and [math]k\in\mathbb N[/math], the relation

[[math]] (i_1,\ldots,i_k)\sim(j_1,\ldots,j_k)\iff u_{i_1j_1}\ldots u_{i_kj_k}\neq0 [[/math]]

is reflexive and symmetric, and is transitive at [math]k=1,2[/math]. In the classical case, [math]G\subset S_N[/math], this relation is transitive at any [math]k\in\mathbb N[/math], and is the usual [math]k[/math]-orbital equivalence.

Show Proof

This is known from , the proof being as follows:

(1) The reflexivity of [math]\sim[/math] follows by using the counit, as follows:

[[math]] \begin{eqnarray*} \varepsilon(u_{i_ri_r})=1,\forall r &\implies&\varepsilon(u_{i_1i_1}\ldots u_{i_ki_k})=1\\ &\implies&u_{i_1i_1}\ldots u_{i_ki_k}\neq0\\ &\implies&(i_1,\ldots,i_k)\sim(i_1,\ldots,i_k) \end{eqnarray*} [[/math]]

(2) The symmetry follows by applying the antipode, and then the involution:

[[math]] \begin{eqnarray*} (i_1,\ldots,i_k)\sim(j_1,\ldots,j_k) &\implies&u_{i_1j_1}\ldots u_{i_kj_k}\neq0\\ &\implies&u_{j_ki_k}\ldots u_{j_1i_1}\neq0\\ &\implies&u_{j_1i_1}\ldots u_{j_ki_k}\neq0\\ &\implies&(j_1,\ldots,j_k)\sim(i_1,\ldots,i_k) \end{eqnarray*} [[/math]]

(3) The transitivity at [math]k=1,2[/math] is more tricky. Here we need to prove that:

[[math]] u_{i_1j_1}\ldots u_{i_kj_k}\neq0\ ,\ u_{j_1l_1}\ldots u_{j_kl_k}\neq0\implies u_{i_1l_1}\ldots u_{i_kl_k}\neq0 [[/math]]

In order to do so, we use the following formula:

[[math]] \Delta(u_{i_1l_1}\ldots u_{i_kl_k})=\sum_{s_1\ldots s_k}u_{i_1s_1}\ldots u_{i_ks_k}\otimes u_{s_1l_1}\ldots u_{s_kl_k} [[/math]]

At [math]k=1[/math], we already know this. At [math]k=2[/math] now, we can use the following trick:

[[math]] \begin{eqnarray*} (u_{i_1j_1}\otimes u_{j_1l_1})\Delta(u_{i_1l_1}u_{i_2l_2})(u_{i_2j_2}\otimes u_{j_2l_2}) &=&\sum_{s_1s_2}u_{i_1j_1}u_{i_1s_1}u_{i_2s_2}u_{i_2j_2}\otimes u_{j_1l_1}u_{s_1l_1}u_{s_2l_2}u_{j_2l_2}\\ &=&u_{i_1j_1}u_{i_2j_2}\otimes u_{j_1l_1}u_{j_2l_2} \end{eqnarray*} [[/math]]

Indeed, we obtain from this the following implication, as desired:

[[math]] u_{i_1j_1}u_{i_2j_2}\neq0,u_{j_1l_1}u_{j_2l_2}\neq0\implies u_{i_1l_1}u_{i_2l_2}\neq0 [[/math]]

(4) Finally, assume that we are in the classical case, [math]G\subset S_N[/math]. We have:

[[math]] u_{ij}=\chi\left(\sigma\in G\Big|\sigma(j)=i\right) [[/math]]

But this formula shows that we have the following equivalence:

[[math]] u_{i_1j_1}\ldots u_{i_kj_k}\neq0\iff\exists \sigma\in G,\ \sigma(i_1)=j_1,\ldots,\sigma(i_k)=j_k [[/math]]

In other words, [math](i_1,\ldots,i_k)\sim(j_1,\ldots,j_k)[/math] happens precisely when [math](i_1,\ldots,i_k)[/math] and [math](j_1,\ldots,j_k)[/math] are in the same [math]k[/math]-orbital of [math]G[/math], and this gives the last assertion.

■

The above result raises the question about what exactly happens at [math]k=3[/math], in relation with transitivity, and the answer here is negative in general. To be more precise, as explained by McCarthy in , there are closed subgroups [math]G\subset S_N^+[/math], as for instance the Kac-Paljutkin quantum group [math]G\subset S_4^+[/math], for which [math]\sim[/math] is not transitive at [math]k=3[/math].

In view of all this, we can only formulate a modest definition, as follows:

Definition

Given a closed subgroup [math]G\subset S_N^+[/math], consider the relation defined by:

[[math]] (i_1,\ldots,i_k)\sim(j_1,\ldots,j_k)\iff u_{i_1j_1}\ldots u_{i_kj_k}\neq0 [[/math]]

• At [math]k=1[/math], the equivalence classes of [math]\sim[/math] are called orbits of [math]G[/math].
• At [math]k=2[/math], the equivalence classes of [math]\sim[/math] are called orbitals of [math]G[/math].
• At [math]k\geq3[/math], if [math]\sim[/math] is transitive, we call its equivalence classes [math]k[/math]-orbitals of [math]G[/math].

It is possible to say more things here, but generally speaking, the good theory remains at [math]k=1,2[/math]. In what follows we will focus on the case [math]k=2[/math], where [math]\sim[/math] is given by:

[[math]] (i,k)\sim (j,l)\iff u_{ij}u_{kl}\neq0 [[/math]]

As a key theoretical result on the subject, again from , we have the following key analogue of Theorem 15.3, which makes a connection with the graph problematics:

Theorem

Given a closed subgroup [math]G\subset S_N^+[/math], with magic matrix [math]u=(u_{ij})[/math], consider the following vector space coaction map, where [math]X=\{1,\ldots,N\}[/math]:

[[math]] \Phi:C(X\times X)\to C(X\times X)\otimes C(G)\quad,\quad e_{ik}\to\sum_{jl}e_{jl}\otimes u_{ji}u_{lk} [[/math]]

The following three algebras are then isomorphic,

[[math]] End(u)=\left\{d\in M_N(\mathbb C)\Big|du=ud\right\} [[/math]]

[[math]] Fix(\Phi)=\left\{\xi\in C(X\times X)\Big|\Phi(\xi)=\xi\otimes1\right\} [[/math]]

[[math]] Fix(\sim)=\left\{\xi\in C(X\times X)\Big|(i,k)\sim(j,l)\implies \xi_{ik}=\xi_{jl}\right\} [[/math]]

where [math]\sim[/math] is the orbital equivalence relation from Definition 15.7 (2).

Show Proof

This follows by doing some computations which are quite similar to those from the proof of Theorem 15.3, and we refer here to , for the details.

■

As already mentioned, the above result makes a quite obvious connection with the graph problematics, the precise statement here being as follows:

Theorem

In order for a quantum permutation group [math]G\subset S_N^+[/math] to act on a graph [math]X[/math], having [math]N[/math] vertices, the adjacency matrix [math]d\in M_N(0,1)[/math] of the graph must be, when regarded as function on the set [math]\{1,\ldots,N\}^2[/math], constant on the orbitals of [math]G[/math].

Show Proof

This follows indeed from the following isomorphism, from Theorem 15.8:

[[math]] End(u)\simeq Fix(\sim) [[/math]]

For more on all this, details, examples, and applications too, we refer to .

■

Finally, as a theoretical application of the theory of orbitals, as developed above, let us discuss now the notion of double transitivity. Following , we have:

Definition

Let [math]G\subset S_N^+[/math] be a closed subgroup, with magic unitary [math]u=(u_{ij})[/math], and consider as before the equivalence relation on [math]\{1,\ldots,N\}^2[/math] given by:

[[math]] (i,k)\sim (j,l)\iff u_{ij}u_{kl}\neq0 [[/math]]

• The equivalence classes under [math]\sim[/math] are called orbitals of [math]G[/math].
• [math]G[/math] is called doubly transitive when the action has two orbitals.

In other words, we call [math]G\subset S_N^+[/math] doubly transitive when [math]u_{ij}u_{kl}\neq0[/math], for any [math]i\neq k,j\neq l[/math].

To be more precise, it is clear from definitions that the diagonal [math]D\subset\{1,\ldots,N\}^2[/math] is an orbital, and that its complement [math]D^c[/math] must be a union of orbitals. With this remark in hand, the meaning of (2) is that the orbitals must be [math]D,D^c[/math].

In more analytic terms, we have the following result, also from :

Theorem

For a doubly transitive subgroup [math]G\subset S_N^+[/math], we have:

[[math]] \int_Gu_{ij}u_{kl}=\begin{cases} \frac{1}{N}&{\rm if}\ i=k,j=l\\ 0&{\rm if}\ i=k,j\neq l\ {\rm or}\ i\neq k,j=l\\ \frac{1}{N(N-1)}&{\rm if}\ i\neq k,j\neq l \end{cases} [[/math]]

Moreover, this formula characterizes the double transitivity.

Show Proof

We use the standard fact, from , that the integrals in the statement form the projection onto [math]Fix(u^{\otimes 2})[/math]. Now if we assume that [math]G[/math] is doubly transitive, [math]Fix(u^{\otimes 2})[/math] has dimension 2, and therefore coincides with [math]Fix(u^{\otimes 2})[/math] for the usual symmetric group [math]S_N[/math]. Thus the integrals in the statement coincide with those for the symmetric group [math]S_N[/math], which are given by the above formula. Finally, the converse is clear as well.

■

So long for orbits, orbitals, and transitivity. As already mentioned, Theorem 15.9, which makes the connection with the actions on graphs [math]G\curvearrowright X[/math], is something quite far-reaching, and for the continuation of this, we refer to and subsequent papers.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].