13c. Quantum permutations

[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 will be interested here in the quantum permutation groups, and their relation with the Hadamard matrices. The following key definition is due to Wang :

Definition

A magic unitary matrix is a square matrix over a [math]C^*[/math]-algebra,

[[math]] u\in M_N(A) [[/math]]

whose entries are projections, summing up to [math]1[/math] on each row and each column.

The basic examples of such matrices come from the usual permutation groups, [math]G\subset S_N[/math]. Indeed, given such subgroup, the following matrix is magic:

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

The interest in these matrices comes from the following functional analytic description of the usual symmetric group, from :

Proposition

Consider the symmetric group [math]S_N[/math].

• The standard coordinates [math]v_{ij}\in C(S_N)[/math], coming from the embedding [math]S_N\subset O_N[/math] given by the permutation matrices, are given by [math]v_{ij}=\chi(\sigma|\sigma(j)=i)[/math].
• The matrix [math]v=(v_{ij})[/math] is magic, in the sense that its entries are orthogonal projections, summing up to [math]1[/math] on each row and each column.
• The algebra [math]C(S_N)[/math] is isomorphic to the universal commutative [math]C^*[/math]-algebra generated by the entries of a [math]N\times N[/math] magic matrix.

Show Proof

These results are all elementary, as follows:

(1) The canonical embedding [math]S_N\subset O_N[/math], coming from the standard permutation matrices, is given by [math]\sigma(e_j)=e_{\sigma(j)}[/math]. Thus, we have [math]\sigma=\sum_je_{\sigma(j)j}[/math], so the standard coordinates on [math]S_N\subset O_N[/math] are given by [math]v_{ij}(\sigma)=\delta_{i,\sigma(j)}[/math]. Thus, we must have, as claimed:

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

(2) Any characteristic function [math]\chi\in\{0,1\}[/math] being a projection in the operator algebra sense ([math]\chi^2=\chi^*=\chi[/math]), we have indeed a matrix of projections. As for the sum 1 condition on rows and columns, this is clear from the formula of the elements [math]v_{ij}[/math].

(3) Consider the universal algebra in the statement, namely:

[[math]] A=C^*_{comm}\left((w_{ij})_{i,j=1,\ldots,N}\Big|w={\rm magic}\right) [[/math]]

We have a quotient map [math]A\to C(S_N)[/math], given by [math]w_{ij}\to v_{ij}[/math]. On the other hand, by using the Gelfand theorem we can write [math]A=C(X)[/math], with [math]X[/math] being a compact space, and by using the coordinates [math]w_{ij}[/math] we have [math]X\subset O_N[/math], and then [math]X\subset S_N[/math]. Thus we have as well a quotient map [math]C(S_N)\to A[/math] given by [math]v_{ij}\to w_{ij}[/math], and this gives (3). See Wang .

■

We are led in this way to the following result:

Theorem

The following is a Woronowicz algebra,

[[math]] C(S_N^+)=C^*\left((u_{ij})_{i,j=1,\ldots,N}\Big|u={\rm magic}\right) [[/math]]

and the underlying compact quantum group [math]S_N^+[/math] is called quantum permutation group.

Show Proof

As a first remark, the algebra [math]C(S_N^+)[/math] is indeed well-defined, because the magic condition forces [math]||u_{ij}||\leq1[/math], for any [math]C^*[/math]-norm. Our claim now is that we can define maps [math]\Delta,\varepsilon,S[/math] as in Definition 13.6. Consider indeed the following matrix:

[[math]] U_{ij}=\sum_ku_{ik}\otimes u_{kj} [[/math]]

As a first observation, we have [math]U_{ij}=U_{ij}^*[/math]. In fact the entries [math]U_{ij}[/math] are orthogonal projections, because we have as well:

[[math]] U_{ij}^2 =\sum_{kl}u_{ik}u_{il}\otimes u_{kj}u_{lj} =\sum_ku_{ik}\otimes u_{kj} =U_{ij} [[/math]]

In order to prove now that the matrix [math]U=(U_{ij})[/math] is magic, it remains to verify that the sums on the rows and columns are 1. For the rows, this can be checked as follows:

[[math]] \sum_jU_{ij} =\sum_{jk}u_{ik}\otimes u_{kj} =\sum_ku_{ik}\otimes1 =1\otimes1 [[/math]]

For the columns the computation is similar, as follows:

[[math]] \sum_iU_{ij} =\sum_{ik}u_{ik}\otimes u_{kj} =\sum_k1\otimes u_{kj} =1\otimes1 [[/math]]

Thus the matrix [math]U=(U_{ij})[/math] is magic indeed, as claimed above, and so we can define a comultiplication map, simply by setting:

[[math]] \Delta(u_{ij})=U_{ij} [[/math]]

By using a similar reasoning, and similar elementary computations, we can define as well a counit map by [math]\varepsilon(u_{ij})=\delta_{ij}[/math], and an antipode by [math]S(u_{ij})=u_{ji}[/math]. Thus the Woronowicz algebra axioms from Definition 13.6 are satisfied, and this finishes the proof.

■

The terminology comes from the following result, also from Wang :

Proposition

The quantum group [math]S_N^+[/math] acts on the set [math]X=\{1,\ldots,N\}[/math], the corresponding coaction map [math]\Phi:C(X)\to C(X)\otimes C(S_N^+)[/math] being given by:

[[math]] \Phi(\delta_i)=\sum_j\delta_j\otimes u_{ji} [[/math]]

In fact, [math]S_N^+[/math] is the biggest compact quantum group acting on [math]X[/math], by leaving the counting measure invariant, in the sense that [math](tr\otimes id)\Phi=tr(.)1[/math], where [math]tr(\delta_i)=\frac{1}{N},\forall i[/math].

Show Proof

Our claim is that given a compact quantum group [math]G[/math], the formula [math]\Phi(\delta_i)=\sum_j\delta_j\otimes u_{ji}[/math] defines a morphism of algebras, which is a coaction map, leaving the trace invariant, precisely when the matrix [math]u=(u_{ij})[/math] is a magic corepresentation of [math]C(G)[/math]. Indeed, let us first determine when [math]\Phi[/math] is multiplicative. We have:

[[math]] \Phi(\delta_i)\Phi(\delta_k) =\sum_{jl}\delta_j\delta_l\otimes u_{ji}u_{lk} =\sum_j\delta_j\otimes u_{ji}u_{jk} [[/math]]

On the other hand, we have as well:

[[math]] \Phi(\delta_i\delta_k) =\delta_{ik}\Phi(\delta_i) =\delta_{ik}\sum_j\delta_j\otimes u_{ji} [[/math]]

We conclude that the multiplicativity of [math]\Phi[/math] is equivalent to the following conditions:

[[math]] u_{ji}u_{jk}=\delta_{ik}u_{ji}\quad,\quad\forall i,j,k [[/math]]

Regarding now the unitality of [math]\Phi[/math], we have the following formula:

[[math]] \Phi(1) =\sum_i\Phi(\delta_i) =\sum_{ij}\delta_j\otimes u_{ji} =\sum_j\delta_j\otimes\left(\sum_iu_{ji}\right) [[/math]]

Thus [math]\Phi[/math] is unital when the following conditions are satisfied:

[[math]] \sum_iu_{ji}=1\quad,\quad\forall i [[/math]]

Finally, the fact that [math]\Phi[/math] is a [math]*[/math]-morphism translates into:

[[math]] u_{ij}=u_{ij}^*\quad,\quad\forall i,j [[/math]]

Summing up, in order for [math]\Phi(\delta_i)=\sum_j\delta_j\otimes u_{ji}[/math] to be a morphism of [math]C^*[/math]-algebras, the elements [math]u_{ij}[/math] must be projections, summing up to 1 on each row of [math]u[/math]. Regarding now the preservation of the trace condition, observe that we have:

[[math]] (tr\otimes id)\Phi(\delta_i)=\frac{1}{N}\sum_ju_{ji} [[/math]]

Thus the trace is preserved precisely when the elements [math]u_{ij}[/math] sum up to 1 on each of the columns of [math]u[/math]. We conclude from this that [math]\Phi(\delta_i)=\sum_j\delta_j\otimes u_{ji}[/math] is a morphism of [math]C^*[/math]-algebras preserving the trace precisely when [math]u[/math] is magic, and since the coaction conditions on [math]\Phi[/math] are equivalent to the fact that [math]u[/math] must be a corepresentation, this finishes the proof of our claim. But this claim proves all the assertions in the statement.

■

As a quite surprising result now, also from Wang , we have:

Theorem

We have an embedding [math]S_N\subset S_N^+[/math], given at the algebra level by:

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

This is an isomorphism at [math]N\leq3[/math], but not at [math]N\geq4[/math], where [math]S_N^+[/math] is not classical, nor finite.

Show Proof

The fact that we have indeed an embedding as above is clear. Regarding now the second assertion, we can prove this in four steps, as follows:

\underline{Case [math]N=2[/math]}. The fact that [math]S_2^+[/math] is indeed classical, and hence collapses to [math]S_2[/math], is trivial, because the [math]2\times2[/math] magic matrices are as follows, with [math]p[/math] being a projection:

[[math]] U=\begin{pmatrix}p&1-p\\1-p&p\end{pmatrix} [[/math]]

\underline{Case [math]N=3[/math]}. It is enough to check that [math]u_{11},u_{22}[/math] commute. But this follows from:

[[math]] \begin{eqnarray*} u_{11}u_{22} &=&u_{11}u_{22}(u_{11}+u_{12}+u_{13})\\ &=&u_{11}u_{22}u_{11}+u_{11}u_{22}u_{13}\\ &=&u_{11}u_{22}u_{11}+u_{11}(1-u_{21}-u_{23})u_{13}\\ &=&u_{11}u_{22}u_{11} \end{eqnarray*} [[/math]]

Indeed, by applying the involution to this formula, we obtain from this that we have [math]u_{22}u_{11}=u_{11}u_{22}u_{11}[/math] as well, and so we get [math]u_{11}u_{22}=u_{22}u_{11}[/math], as desired.

\underline{Case [math]N=4[/math]}. Consider the following matrix, with [math]p,q[/math] being projections:

[[math]] U=\begin{pmatrix} p&1-p&0&0\\ 1-p&p&0&0\\ 0&0&q&1-q\\ 0&0&1-q&q \end{pmatrix} [[/math]]

This matrix is then magic, and if we choose [math]p,q[/math] as for the algebra [math] \lt p,q \gt [/math] to be infinite dimensional, we conclude that [math]C(S_4^+)[/math] is infinite dimensional as well.

\underline{Case [math]N\geq5[/math]}. Here we can use the standard embedding [math]S_4^+\subset S_N^+[/math], obtained at the level of the corresponding magic matrices in the following way:

[[math]] u\to\begin{pmatrix}u&0\\ 0&1_{N-4}\end{pmatrix} [[/math]]

Indeed, with this in hand, the fact that [math]S_4^+[/math] is a non-classical, infinite compact quantum group implies that [math]S_N^+[/math] with [math]N\geq5[/math] has these two properties as well. See .

■

The above results are quite surprising, and you may wonder, okay with all this mathematics, but in practice, how to intuitively accept the fact that [math]\{1,2,3,4\}[/math] has an infinity of quantum permutations. Good point, and in answer, get to learn some quantum mechanics, say from Feynman or Griffiths or Weinberg . You will learn many interesting things from there, and above everything, become a modest person.

General references

Banica, Teo (2024). "Invitation to Hadamard matrices". arXiv:1910.06911 [math.CO].