10a. Finite graphs

[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.

Many interesting examples of quantum permutation groups appear as particular cases of the following general construction from , involving finite graphs:

Proposition

Given a finite graph [math]X[/math], with adjacency matrix [math]d\in M_N(0,1)[/math], the following construction produces a quantum permutation group,

[[math]] C(G^+(X))=C(S_N^+)\Big/\Big \lt du=ud\Big \gt [[/math]]

whose classical version [math]G(X)[/math] is the usual automorphism group of [math]X[/math].

Show Proof

The fact that we have a quantum group comes from the fact that [math]du=ud[/math] reformulates as [math]d\in End(u)[/math], which makes it clear that we are dividing by a Hopf ideal. Regarding the second assertion, we must establish here the following equality:

[[math]] C(G(X))=C(S_N)\Big/\Big \lt du=ud\Big \gt [[/math]]

For this purpose, recall that [math]u_{ij}(\sigma)=\delta_{\sigma(j)i}[/math]. By using this formula, we have:

[[math]] \begin{eqnarray*} (du)_{ij}(\sigma) &=&\sum_kd_{ik}u_{kj}(\sigma)\\ &=&\sum_kd_{ik}\delta_{\sigma(j)k}\\ &=&d_{i\sigma(j)} \end{eqnarray*} [[/math]]

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

[[math]] \begin{eqnarray*} (ud)_{ij}(\sigma) &=&\sum_ku_{ik}(\sigma)d_{kj}\\ &=&\sum_k\delta_{\sigma(k)i}d_{kj}\\ &=&d_{\sigma^{-1}(i)j} \end{eqnarray*} [[/math]]

Thus the condition [math]du=ud[/math] reformulates as [math]d_{ij}=d_{\sigma(i)\sigma(j)}[/math], and we are led to the usual notion of an action of a permutation group on [math]X[/math], as claimed.

■

Let us work out some basic examples. We have the following result:

Theorem

The construction [math]X\to G^+(X)[/math] has the following properties:

• For the [math]N[/math]-point graph, having no edges at all, we obtain [math]S_N^+[/math].
• For the [math]N[/math]-simplex, having edges everywhere, we obtain as well [math]S_N^+[/math].
• We have [math]G^+(X)=G^+(X^c)[/math], where [math]X^c[/math] is the complementary graph.
• For a disconnected union, we have [math]G^+(X)\,\hat{*}\,G^+(Y)\subset G^+(X\sqcup Y)[/math].
• For the square, we obtain a non-classical, proper subgroup of [math]S_4^+[/math].

Show Proof

All these results are elementary, the proofs being as follows:

(1) This follows from definitions, because here we have [math]d=0[/math].

(2) Here [math]d=\mathbb I[/math] is the all-one matrix, and the magic condition gives [math]u\mathbb I=\mathbb Iu=N\mathbb I[/math]. We conclude that [math]du=ud[/math] is automatic in this case, and so [math]G^+(X)=S_N^+[/math].

(3) The adjacency matrices of [math]X,X^c[/math] being related by the formula [math]d_X+d_{X^c}=\mathbb I[/math]. We can use here the above formula [math]u\mathbb I=\mathbb Iu=N\mathbb I[/math], and we conclude that [math]d_Xu=ud_X[/math] is equivalent to [math]d_{X^c}u=ud_{X^c}[/math]. Thus, we obtain, as claimed, [math]G^+(X)=G^+(X^c)[/math].

(4) The adjacency matrix of a disconnected union is given by [math]d_{X\sqcup Y}=diag(d_X,d_Y)[/math]. Now let [math]w=diag(u,v)[/math] be the fundamental corepresentation of [math]G^+(X)\,\hat{*}\,G^+(Y)[/math]. Then [math]d_Xu=ud_X[/math] and [math]d_Yv=vd_Y[/math] imply, as desired, [math]d_{X\sqcup Y}w=wd_{X\sqcup Y}[/math].

(5) We know from (3) that we have [math]G^+(\square)=G^+(|\ |)[/math]. We know as well from (4) that we have [math]\mathbb Z_2\,\hat{*}\,\mathbb Z_2\subset G^+(|\ |)[/math]. It follows that [math]G^+(\square)[/math] is non-classical. Finally, the inclusion [math]G^+(\square)\subset S_4^+[/math] is indeed proper, because [math]S_4\subset S_4^+[/math] does not act on the square.

■

In order to further advance, and to explicitely compute various quantum automorphism groups, we can use the spectral decomposition of [math]d[/math], as follows:

Proposition

A closed subgroup [math]G\subset S_N^+[/math] acts on a graph [math]X[/math] precisely when

[[math]] P_\lambda u=uP_\lambda\quad,\quad\forall\lambda\in\mathbb R [[/math]]

where [math]d=\sum_\lambda\lambda\cdot P_\lambda[/math] is the spectral decomposition of the adjacency matrix of [math]X[/math].

Show Proof

Since [math]d\in M_N(0,1)[/math] is a symmetric matrix, we can consider indeed its spectral decomposition, [math]d=\sum_\lambda\lambda\cdot P_\lambda[/math]. We have then the following formula:

[[math]] \lt d \gt =span\left\{P_\lambda\Big|\lambda\in\mathbb R\right\} [[/math]]

But this shows that we have the following equivalence:

[[math]] d\in End(u)\iff P_\lambda\in End(u),\forall\lambda\in\mathbb R [[/math]]

Thus, we are led to the conclusion in the statement.

■

In order to exploit this, we will often combine it with the following standard fact:

Proposition

Consider a closed subgroup [math]G\subset S_N^+[/math], with associated coaction map

[[math]] \Phi:\mathbb C^N\to \mathbb C^N\otimes C(G) [[/math]]

For a linear subspace [math]V\subset\mathbb C^N[/math], the following are equivalent:

• The magic matrix [math]u=(u_{ij})[/math] commutes with [math]P_V[/math].
• [math]V[/math] is invariant, in the sense that [math]\Phi(V)\subset V\otimes C(G)[/math].

Show Proof

Let [math]P=P_V[/math]. For any [math]i\in\{1,\ldots,N\}[/math] we have the following formula:

[[math]] \begin{eqnarray*} \Phi(P(e_i)) &=&\Phi\left(\sum_kP_{ki}e_k\right)\\ &=&\sum_{jk}P_{ki}e_j\otimes u_{jk}\\ &=&\sum_je_j\otimes (uP)_{ji} \end{eqnarray*} [[/math]]

On the other hand the linear map [math](P\otimes id)\Phi[/math] is given by a similar formula:

[[math]] \begin{eqnarray*} (P\otimes id)(\Phi(e_i)) &=&\sum_kP(e_k)\otimes u_{ki}\\ &=&\sum_{jk}P_{jk}e_j\otimes u_{ki}\\ &=&\sum_je_j\otimes (Pu)_{ji} \end{eqnarray*} [[/math]]

Thus [math]uP=Pu[/math] is equivalent to [math]\Phi P=(P\otimes id)\Phi[/math], and the conclusion follows.

■

We have as well the following useful complementary result, from :

Proposition

Let [math]p\in M_N(\mathbb C)[/math] be a matrix, and consider its “color” decomposition, obtained by setting [math](p_c)_{ij}=1[/math] if [math]p_{ij}=c[/math] and [math](p_c)_{ij}=0[/math] otherwise:

[[math]] p=\sum_{c\in\mathbb C}c\cdot p_c [[/math]]

Then [math]u=(u_{ij})[/math] commutes with [math]p[/math] if and only if it commutes with all matrices [math]p_c[/math].

Show Proof

Consider the multiplication and counit maps of the algebra [math]\mathbb C^N[/math]:

[[math]] M:e_i\otimes e_j\to e_ie_j [[/math]]

[[math]] C:e_i\to e_i\otimes e_i [[/math]]

Since [math]M,C[/math] intertwine [math]u,u^{\otimes 2}[/math], their iterations [math]M^{(k)},C^{(k)}[/math] intertwine [math]u,u^{\otimes k}[/math], and so:

[[math]] \begin{eqnarray*} p^{(k)} &=&M^{(k)}p^{\otimes k}C^{(k)}\\ &=&\sum_{c\in\mathbb C}c^kp_c\\ &\in&End(u) \end{eqnarray*} [[/math]]

Let [math]S=\{c\in\mathbb C|p_c\neq 0\}[/math], and [math]f(c)=c[/math]. By Stone-Weierstrass we have [math]S= \lt f \gt [/math], and so for any [math]e\in S[/math] the Dirac mass at [math]e[/math] is a linear combination of powers of [math]f[/math]:

[[math]] \begin{eqnarray*} \delta_e &=&\sum_{k}\lambda_kf^k\\ &=&\sum_{k}\lambda_k \left(\sum_{c\in S}c^k\delta_c\right)\\ &=&\sum_{c\in S}\left(\sum_{k}\lambda_kc^k\right)\delta_c \end{eqnarray*} [[/math]]

The corresponding linear combination of matrices [math]p^{(k)}[/math] is given by:

[[math]] \begin{eqnarray*} \sum_k\lambda_kp^{(k)} &=&\sum_k\lambda_k \left(\sum_{c\in S}c^kp_c\right)\\ &=&\sum_{c\in S}\left(\sum_{k}\lambda_kc^k\right)p_c \end{eqnarray*} [[/math]]

The Dirac masses being linearly independent, in the first formula all coefficients in the right term are 0, except for the coefficient of [math]\delta_e[/math], which is 1. Thus the right term in the second formula is [math]p_e[/math], and it follows that we have [math]p_e\in End(u)[/math], as claimed.

■

The above results can be combined, and we are led into a “color-spectral” decomposition method for [math]d[/math], which can lead to a number of nontrivial results. In fact, all this is best understood in terms of Jones' planar algebras . We refer here to .

As a basic application of this, we can further study [math]G^+(\square)[/math], as follows:

Proposition

The quantum automorphism group of the [math]N[/math]-cycle is as follows:

• At [math]N\neq 4[/math] we have [math]G^+(X)=D_N[/math].
• At [math]N=4[/math] we have [math]D_4\subset G^+(X)\subset S_4^+[/math], with proper inclusions.

Show Proof

We already know that the results hold at [math]N\leq4[/math], so let us assume [math]N\geq5[/math]. Given a [math]N[/math]-th root of unity, [math]w^N=1[/math], consider the following vector:

[[math]] \xi=(w^i) [[/math]]

This is an eigenvector of [math]d[/math], with eigenvalue [math]w+w^{N-1}[/math]. With [math]w=e^{2\pi i/N}[/math], it follows that [math]1,f,f^2,\ldots ,f^{N-1}[/math] are eigenvectors of [math]d[/math]. More precisely, the invariant subspaces of [math]d[/math] are as follows, with the last subspace having dimension 1 or 2, depending on [math]N[/math]:

[[math]] \mathbb C 1,\, \mathbb C f\oplus\mathbb C f^{N-1},\, \mathbb C f^2\oplus\mathbb C f^{N-2},\ldots [[/math]]

Consider now the associated coaction [math]\Phi:\mathbb C^N\to \mathbb C^N\otimes C(G)[/math], and write:

[[math]] \Phi(f)=f\otimes a+f^{N-1}\otimes b [[/math]]

By taking the square of this equality we obtain:

[[math]] \Phi(f^2)=f^2\otimes a^2+f^{N-2}\otimes b^2+1\otimes(ab+ba) [[/math]]

It follows that [math]ab=-ba[/math], and that [math]\Phi(f^2)[/math] is given by the following formula:

[[math]] \Phi(f^2)=f^2\otimes a^2+f^{N-2}\otimes b^2 [[/math]]

By multiplying this with [math]\Phi(f)[/math] we obtain:

[[math]] \Phi(f^3)=f^3\otimes a^3+f^{N-3}\otimes b^3+f^{N-1}\otimes ab^2+f\otimes ba^2 [[/math]]

Now since [math]N\geq 5[/math] implies that [math]1,N-1[/math] are different from [math]3,N-3[/math], we must have [math]ab^2=ba^2=0[/math]. By using this and [math]ab=-ba[/math], we obtain by recurrence on [math]k[/math] that:

[[math]] \Phi(f^k)=f^k\otimes a^k+f^{N-k}\otimes b^k [[/math]]

In particular at [math]k=N-1[/math] we obtain:

[[math]] \Phi(f^{N-1})=f^{N-1}\otimes a^{N-1}+f\otimes b^{N-1} [[/math]]

On the other hand we have [math]f^*=f^{N-1}[/math], so by applying [math]*[/math] to [math]\Phi(f)[/math] we get:

[[math]] \Phi(f^{N-1})=f^{N-1}\otimes a^*+f\otimes b^* [[/math]]

Thus [math]a^*=a^{N-1}[/math] and [math]b^*=b^{N-1}[/math]. Together with [math]ab^2=0[/math] this gives:

[[math]] \begin{eqnarray*} (ab)(ab)^* &=&abb^*a^*\\ &=&ab^Na^{N-1}\\ &=&(ab^2)b^{N-2}a^{N-1}\\ &=&0 \end{eqnarray*} [[/math]]

From positivity we get from this [math]ab=0[/math], and together with [math]ab=-ba[/math], this shows that [math]a,b[/math] commute. On the other hand [math]C(G)[/math] is generated by the coefficients of [math]\Phi[/math], which are powers of [math]a,b[/math], and so [math]C(G)[/math] must be commutative, and we obtain the result.

■

Summarizing, this was a bad attempt in understanding [math]G^+(\square)[/math], which appears to be “exceptional” among the quantum symmetry groups of the [math]N[/math]-cycles.

An alternative approach to [math]G^+(\square)[/math] comes by regarding the square as the [math]N=2[/math] particular case of the [math]N[/math]-hypercube [math]\square_N[/math]. Indeed, the usual symmetry group of [math]\square_N[/math] is the hyperoctahedral group [math]H_N[/math], so we should have a formula of the following type:

[[math]] G(\square)=H_2^+ [[/math]]

In order to clarify this, let us start with the following simple fact:

Proposition

We have an embedding as follows, [math]g_i[/math] being the generators of [math]\mathbb Z_2^N[/math],

[[math]] \widehat{\mathbb Z_2^N}\subset S^{N-1}_{\mathbb R,+}\quad,\quad x_i=\frac{g_i}{\sqrt{N}} [[/math]]

whose image is the geometric hypercube:

[[math]] \square_N=\left\{x\in\mathbb R^N\Big|x_i=\pm\frac{1}{\sqrt{N}},\forall i\right\} [[/math]]

Show Proof

This is something that we already know, from chapter 1 above. Consider indeed the following standard group algebra generators:

[[math]] g_i\in C^*(\mathbb Z_2^N)=C(\widehat{\mathbb Z_2^N}) [[/math]]

These generators satisfy satisfy then [math]g_i=g_i^*[/math], [math]g_i^2=1[/math], and when rescaling by [math]1/\sqrt{N}[/math], we obtain the relations defining [math]\square_N[/math].

■

We can now study the quantum groups [math]G^+(\square_N)[/math], and we are led to the quite surprising conclusion, from , that these are the twisted orthogonal groups [math]\bar{O}_N[/math]:

Theorem

With [math]\mathbb Z_2^N= \lt g_1,\ldots,g_N \gt [/math] we have a coaction map

[[math]] \Phi:C^*(\mathbb Z_2^N)\to C^*(\mathbb Z_2^N)\otimes C(\bar{O}_N)\quad,\quad g_i\to\sum_jg_j\otimes u_{ji} [[/math]]

which makes [math]\bar{O}_N[/math] the quantum isometry group of the hypercube [math]\square_N=\widehat{\mathbb Z_2^N}[/math], as follows:

• With [math]\square_N[/math] viewed as an algebraic manifold, [math]\square_N\subset S^{N-1}_\mathbb R\subset S^{N-1}_{\mathbb R,+}[/math].
• With [math]\square_N[/math] viewed as a graph, with [math]2^N[/math] vertices and [math]2^{N-1}N[/math] edges.
• With [math]\square_N[/math] viewed as a metric space, with metric coming from [math]\mathbb R^N[/math].

Show Proof

Observe first that [math]\square_N[/math] is indeed an algebraic manifold, so (1) as formulated above makes sense, in the general framework of chapter 2. The cube [math]\square_N[/math] is also a graph, as indicated, and so (2) makes sense as well, in the framework of Proposition 10.1. Finally, (3) makes sense as well, because we can define the quantum isometry group of a finite metric space exactly as for graphs, but with [math]d[/math] being this time the distance matrix.

(1) In order for [math]G\subset O_N^+[/math] to act affinely on [math]\square_N[/math], the variables [math]G_i=\sum_jg_j\otimes u_{ji}[/math] must satisfy the same relations as the generators [math]g_i\in \mathbb Z_2^N[/math]. The self-adjointness condition being automatic, the relations to be checked are therefore:

[[math]] G_i^2=1\quad,\quad G_iG_j=G_jG_i [[/math]]

We have the following computation:

[[math]] \begin{eqnarray*} G_i^2 &=&\sum_{kl}g_kg_l\otimes u_{ik}u_{il}\\ &=&1+\sum_{k \lt l}g_kg_l\otimes(u_{ik}u_{il}+u_{il}u_{ik}) \end{eqnarray*} [[/math]]

As for the commutators, these are given by:

[[math]] \begin{eqnarray*} \left[G_i,G_j\right] &=&\sum_{k \lt l}g_kg_l\otimes(u_{ik}u_{jl}-u_{jk}u_{il}+u_{il}u_{jk}-u_{jl}u_{ik}) \end{eqnarray*} [[/math]]

From the first relation we obtain [math]ab=0[/math] for [math]a\neq b[/math] on the same row of [math]u[/math], and by using the antipode, the same happens for the columns. From the second relation we obtain:

[[math]] [u_{ik},u_{jl}]=[u_{jk},u_{il}]\quad,\quad\forall k\neq l [[/math]]

We use the Bhowmick-Goswami trick . By applying the antipode we obtain:

[[math]] [u_{lj},u_{ki}]=[u_{li},u_{kj}] [[/math]]

By relabelling, this gives the following formula:

[[math]] [u_{ik},u_{jl}]=[u_{il},u_{jk}]\quad,\quad j\neq i [[/math]]

Thus for [math]i\neq j,k\neq l[/math] we must have:

[[math]] [u_{ik},u_{jl}]=[u_{jk},u_{il}]=0 [[/math]]

We are therefore led to [math]G\subset\bar{O}_N[/math], as claimed.

(2) We can use here the fact that the cube [math]\square_N[/math], when regarded as a graph, is the Cayley graph of the group [math]\mathbb Z_2^N[/math]. The eigenvectors and eigenvalues of [math]\square_N[/math] are as follows:

[[math]] \begin{eqnarray*} v_{i_1\ldots i_N}&=&\sum_{j_1\ldots j_N} (-1)^{i_1j_1 +\ldots+i_Nj_N}g_1^{j_1}\ldots g_N^{j_N}\\ \lambda_{i_1\ldots i_N}&=&(-1)^{i_1}+\ldots +(-1)^{i_N} \end{eqnarray*} [[/math]]

With this picture in hand, and by using Proposition 10.3 and Proposition 10.4 above, the result follows from the same computations as in the proof of (1). See .

(3) Our claim here is that we obtain the same symmetry group as in (2). Indeed, observe that distance matrix of the cube has a color decomposition as follows:

[[math]] d=d_1+\sqrt{2}d_2+\sqrt{3}d_3+\ldots+ \sqrt{N}d_N [[/math]]

Since the powers of [math]d_1[/math] can be computed by counting loops on the cube, we have formulae as follows, with [math]x_{ij}\in\mathbb N[/math] being certain positive integers:

[[math]] \begin{eqnarray*} d_1^2&=&x_{21}1_N+x_{22}d_2\\ d_1^3&=&x_{31}1_N+x_{32}d_2+ x_{33}d_3\\ &\ldots&\\ d_1^N&=&x_{N1}1_N+x_{N2}d_2+x_{N3}d_3+\ldots+x_{NN}d_N \end{eqnarray*} [[/math]]

But this shows that we have [math] \lt d \gt = \lt d_1 \gt [/math]. Now since [math]d_1[/math] is the adjacency matrix of [math]\square_N[/math], viewed as graph, this proves our claim, and we obtain the result via (2).

■

Now back to our questions regarding the square, we have [math]G^+(\square)=\bar{O}_2[/math], and this formula appears as the [math]N=2[/math] particular case of a general formula, namely [math]G^+(\square_N)=\bar{O}_N[/math]. This is quite conceptual, but still not ok. The problem is that we have [math]G(\square_N)=H_N[/math], and so for our theory to be complete, we would need a formula of type [math]H_N^+=\bar{O}_N[/math]. And this latter formula is obviously wrong, because for [math]\bar{O}_N[/math] the character computations lead to Gaussian laws, who cannot appear as liberations of the character laws for [math]H_N[/math], that we have not computed yet, but which can only be something Poisson-related.

General references

Banica, Teo (2024). "Introduction to quantum groups". arXiv:1909.08152 [math.CO].