9c. Reflection groups

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 already know a number of things about the circulant graphs from Part I, and we also know that these usually generalize to the case where we have a transitive action of an abelian group on [math]X[/math]. Both the group theory and the linear algebra aspects here can be quite subtle, involving the classification of finite abelian groups, and generalized Fourier matrices, and that discussion from Part I can be briefly summarized as follows: \begin{fact} The transitive abelian group actions on graphs, [math]G\curvearrowright X[/math] with

[[math]] G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_s} [[/math]]

can be investigated via discrete Fourier analysis, over the group [math]G[/math]. \end{fact} This is of course something very compact, and we refer to Part I for details. In order to advance now on all this, we have the following result, which is standard in discrete Fourier analysis, extending what we previously knew in the circulant case:

Theorem

For a matrix [math]A\in M_N(\mathbb C)[/math], the following are equivalent,

[math]A[/math] is [math]G[/math]-invariant, [math]A_{ij}=\xi_{j-i}[/math], for a certain vector [math]\xi\in\mathbb C^N[/math],
[math]A[/math] is Fourier-diagonal, [math]A=F_GQF_G^*[/math], for a certain diagonal matrix [math]Q[/math],

and if so, [math]\xi=F_G^*q[/math], where [math]q\in\mathbb C^N[/math] is the vector formed by the diagonal entries of [math]Q[/math].

Show Proof

This is something that we know from chapter 4 in the cyclic case, [math]G=\mathbb Z_N[/math], and the proof in general is similar, by using matrix indices as follows:

[[math]] i,j\in G [[/math]]

To be more precise, in order to get started, with our generalization, let us decompose our finite abelian group [math]G[/math] as a product of cyclic groups, as follows:

[[math]] G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_s} [[/math]]

The corresponding Fourier matrix decomposes then as well, as follows:

[[math]] F_G=F_{N_1}\otimes\ldots\otimes F_{N_s} [[/math]]

Now if we set [math]w_i=e^{2\pi i/N_i}[/math], this means that we have the following formula:

[[math]] (F_G)_{ij}=w_1^{i_1j_1}\ldots w_s^{i_sj_s} [[/math]]

We can now prove the equivalence in the statement, as follows:

[math](1)\implies(2)[/math] Assuming [math]A_{ij}=\xi_{j-i}[/math], the matrix [math]Q=F_G^*AF_G[/math] is diagonal, as shown by the following computation, with all indices being group elements:

[[math]] \begin{eqnarray*} Q_{ij} &=&\sum_{kl}\overline{(F_G)}_{ki}A_{kl}(F_G)_{lj}\\ &=&\sum_{kl}w_1^{-k_1i_1}\ldots w_s^{-k_si_s}\cdot\xi_{l-k}\cdot w_1^{l_1j_1}\ldots w_s^{l_sj_s}\\ &=&\sum_{kl}w_1^{l_1j_1-k_1i_1}\ldots w_s^{l_sj_s-k_si_s}\xi_{l-k}\\ &=&\sum_{kr}w_1^{(k_1+r_1)j_1-k_1i_1}\ldots w_s^{(k_s+r_s)j_s-k_si_s}\xi_r\\ &=&\sum_rw_1^{r_1j_1}\ldots w_s^{r_sj_s}\xi_r\sum_kw_1^{k_1(j_1-i_1)}\ldots w_s^{k_s(j_s-i_s)}\\ &=&\sum_rw_1^{r_1j_1}\ldots w_s^{r_sj_s}\xi_r\cdot N_1\delta_{i_1j_1}\ldots N_s\delta_{i_sj_s}\\ &=&N\delta_{ij}\sum_r(F_G)_{jr}\xi_r \end{eqnarray*} [[/math]]

[math](2)\implies(1)[/math] Assuming [math]Q=diag(q_1,\ldots,q_N)[/math], the matrix [math]A=F_GQF_G^*[/math] is [math]G[/math]-invariant, as shown by the following computation, again with all indices being group elements:

[[math]] \begin{eqnarray*} A_{ij} &=&\sum_{kl}(F_G)_{ik}Q_{kk}\overline{(F_G)}_{kj}\\ &=&\sum_kw_1^{i_1k_1}\ldots w_s^{i_sk_s}\cdot q_k\cdot w_1^{-j_1k_1}\ldots w_s^{-j_sk_s}\\ &=&\sum_kw_1^{(i_1-j_1)k_1}\ldots w_s^{(i_s-j_s)k_s}q_k \end{eqnarray*} [[/math]]

To be more precise, in this formula the last term depends only on [math]j-i[/math], and so shows that we have [math]A_{ij}=\xi_{j-i}[/math], with [math]\xi[/math] being the following vector:

[[math]] \begin{eqnarray*} \item[a]i_i &=&\sum_kw_1^{-i_1k_1}\ldots w_s^{-i_sk_s}q_k\\ &=&\sum_k(F_G^*)_{ik}q_k\\ &=&(F_G^*q)_i \end{eqnarray*} [[/math]]

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

■

As another generalization of what we did in chapter 4, in relation now with the dihedral groups, and then with the hyperoctahedral groups, we can investigate the complex reflection groups [math]H_N^s[/math] that we introduced in the above. Let us recall indeed that [math]H_N^s\subset U_N[/math] is the group of permutation-type matrices with [math]s[/math]-th roots of unity as entries:

[[math]] H_N^s=M_N(\mathbb Z_s\cup\{0\})\cap U_N [[/math]]

We know that at [math]s=1,2[/math], this group equals [math]S_N,H_N[/math], that we both know well. In analogy with what we know at [math]s=1,2[/math], we first have the following result:

Proposition

The number of elements of [math]H_N^s[/math] with [math]s\in\mathbb N[/math] is:

[[math]] |H_N^s|=s^NN! [[/math]]

At [math]s=\infty[/math], the group [math]K_N=H_N^\infty[/math] that we obtain is infinite.

Show Proof

This is indeed clear from our definition of [math]H_N^s[/math], as a matrix group as above, because there are [math]N![/math] choices for a permutation-type matrix, and then [math]s^N[/math] choices for the corresponding [math]s[/math]-roots of unity, which must decorate the [math]N[/math] nonzero entries.

■

Once again in analogy with what we know at [math]s=1,2[/math], we have as well:

Theorem

We have a wreath product decomposition as follows,

[[math]] H_N^s=\mathbb Z_s\wr S_N [[/math]]

which means by definition that we have a crossed product decomposition

[[math]] H_N^s=\mathbb Z_s^N\rtimes S_N [[/math]]

with the permutations [math]\sigma\in S_N[/math] acting via [math]\sigma(e_1,\ldots,e_k)=(e_{\sigma(1)},\ldots,e_{\sigma(k)})[/math].

Show Proof

As explained in the proof of Proposition 9.30, the elements of [math]H_N^s[/math] can be identified with the pairs [math]g=(e,\sigma)[/math] consisting of a permutation [math]\sigma\in S_N[/math], and a decorating vector [math]e\in\mathbb Z_s^N[/math], so that at the level of the cardinalities, we have:

[[math]] |H_N|=|\mathbb Z_s^N\times S_N| [[/math]]

Now observe that the product formula for two such pairs [math]g=(e,\sigma)[/math] is as follows, with the permutations [math]\sigma\in S_N[/math] acting on the elements [math]f\in\mathbb Z_s^N[/math] as in the statement:

[[math]] (e,\sigma)(f,\tau)=(ef^\sigma,\sigma\tau) [[/math]]

Thus, we are in the framework of crossed products, and we obtain [math]H_N^s=\mathbb Z_s^N\rtimes S_N[/math]. But this can be written, by definition, as [math]H_N^s=\mathbb Z_s\wr S_N[/math], and we are done.

■

In relation with graph symmetries, the above groups appear as follows:

Theorem

The complex reflection group [math]H_N^s[/math] appears as symmetry group,

[[math]] H_N^s=G(NC_s) [[/math]]

with [math]NC_s[/math] consisting of [math]N[/math] disjoint copies of the oriented cycle [math]C_s[/math].

Show Proof

This is something elementary, the idea being as follows:

(1) Consider first the oriented cycle [math]C_s[/math], which looks as follows:

[[math]] \xymatrix@R=16pt@C=16pt{ &\bullet\ar[r]&\bullet\ar[dr]\\ \bullet\ar[ur]&&&\bullet\ar[d]\\ \bullet\ar[u]&&&\bullet\ar[dl]\\ &\bullet\ar[ul]&\bullet\ar[l]} [[/math]]

It is then clear that the symmetry group of this graph is the cyclic group [math]\mathbb Z_s[/math].

(2) In the general case now, where we have [math]N\in\mathbb N[/math] disjoint copies of the above cycle [math]C_s[/math], we must suitably combine the corresponding [math]N[/math] copies of the cyclic group [math]\mathbb Z_s[/math]. But this leads to the wreath product group [math]H_N^s=\mathbb Z_s\wr S_N[/math], as stated.

■

Normally, with the theory that we have so far, we can investigate the graphs having small number of vertices. But for more here, going beyond what we have, we need more product results, and we will develop the needed theory in the next chapter.

General references

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