14a. Graph symmetries

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 can get back now to graphs. By using the quantum permutation group [math]S_N^+[/math] constructed in the previous chapter, we can perform the following construction:

Theorem

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 indeed 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 [math]\Delta,\varepsilon,S[/math] factorize. Regarding now 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 we have [math]u_{ij}(\sigma)=\delta_{\sigma(j)i}[/math]. We therefore obtain:

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

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

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

Thus [math]du=ud[/math] reformulates as [math]d_{ij}=d_{\sigma(i)\sigma(j)}[/math], which gives the result.

■

Let us work out some examples. With the convention that [math]\hat{*}[/math] is the dual free product, obtained by diagonally concatenating the magic unitaries, we have:

Proposition

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-1[/math], where [math]\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, and so [math]G^+(X)=S_N^+[/math].

(3) The adjacency matrices of [math]X,X^c[/math] being related by the following formula:

[[math]] d_X+d_{X^c}=\mathbb I-1 [[/math]]

By using now the above formula [math]u\mathbb I=\mathbb Iu=N\mathbb I[/math], 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], and we obtain, 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:

Theorem

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], and we have the following formula:

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

Thus [math]d\in End(u)[/math] when [math]P_\lambda\in End(u)[/math] for all [math]\lambda\in\mathbb R[/math], which gives the result.

■

In order to exploit Theorem 14.3, we will often combine it with the following fact:

Proposition

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

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

and 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]] \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} [[/math]]

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

[[math]] (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} [[/math]]

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

■

As an application of the above results, we have the following computation:

Theorem

The quantum automorphism group of the [math]N[/math]-cycle is, at [math]N\neq4[/math]:

[[math]] G^+(X)=D_N [[/math]]

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

Show Proof

We know from Proposition 14.2, and from [math]S_N=S_N^+[/math] at [math]N\leq3[/math], that the various assertions hold indeed at [math]N\leq4[/math]. So, assume [math]N\geq5[/math]. Given a [math]N[/math]-th root of unity, [math]w^N=1[/math], the vector [math]\xi=(w^i)[/math] is an eigenvector of [math]d[/math], with eigenvalue as follows:

[[math]] \lambda=w+w^{N-1} [[/math]]

Now by taking [math]w=e^{2\pi i/N}[/math], it follows that the are eigenvectors of [math]d[/math] are:

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

More precisely, the invariant subspaces of [math]d[/math] are as follows, with the last subspace having dimension 1 or 2 depending on the parity of [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]]

Assuming [math]G\subset G^+(X)[/math], consider the 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 the following formula:

[[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 the following formula:

[[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 the following formula:

[[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]] (ab)(ab)^* =abb^*a^* =ab^Na^{N-1} =(ab^2)b^{N-2}a^{N-1} =0 [[/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.

■

The above result is quite suprising, but we will be back to this, with a more conceptual explanation for the fact that the square [math]\square[/math] has quantum symmetry. Back to theory now, we have the following useful result, complementary to Theorem 14.3:

Theorem

Given a matrix [math]p\in M_N(\mathbb C)[/math], consider its “color” decomposition

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

with the color components [math]p_c\in M_N(0,1)[/math] with [math]c\in\mathbb C[/math] being constructed as follows:

[[math]] (p_c)_{ij}=\begin{cases} 1&{\rm if}\ p_{ij}=c\\ 0&{\rm otherwise} \end{cases} [[/math]]

Then a magic matrix [math]u=(u_{ij})[/math] commutes with [math]p[/math] iff 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\quad,\quad 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]] M^{(k)}p^{\otimes k}C^{(k)} =\sum_{c\in\mathbb C}c^kp_c \in End(u) [[/math]]

Now since this formula holds for any [math]k\in\mathbb N[/math], we obtain the result.

■

The above results can be combined, and we are led to the following statement:

Theorem

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

[[math]] u=(u_{ij}) [[/math]]

commutes with all the matrices coming from the color-spectral decomposition of [math]d[/math].

Show Proof

This follows by combining Theorem 14.3 and Theorem 14.6, with the “color-spectral” decomposition in the statement referring to what comes out by succesively doing the color and spectral decomposition, until the process stabilizes.

■

This latter statement is quite interesting, with the color-spectral decomposition there being something quite intriguing. We will be back to this later, when discussing planar algebras, which is the good framework for discussing such things.

General references

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