guide:2ff34151ce

[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 so far that the circulant graphs are quite interesting objects. Our purpose now is to extend the theory that we have for them, to a more general class of graphs, the “transitive” ones. Let us start with a basic observation, as follows:

Proposition

A graph [math]X[/math], with vertices labeled [math]1,2,\ldots,N[/math], is circulant precisely when for any two vertices [math]i,j\in X[/math] there is a permutation [math]\sigma\in S_N[/math] such that:

• [math]\sigma[/math] maps one vertex to another, [math]\sigma(i)=j[/math].
• [math]\sigma[/math] is cyclic, [math]\sigma(k)=k+s[/math] modulo [math]N[/math], for some [math]s[/math].
• [math]\sigma[/math] leaves invariant the edges, [math]k-l\iff\sigma(k)-\sigma(l)[/math].

Show Proof

This is obvious from definitions, and with the remark that the number [math]s[/math] appearing in (2) is uniquely determined by (1), as being [math]s=j-i[/math], modulo [math]N[/math].

■

The point now is that, with this picture of the circulant graphs in mind, it is quite clear that if we remove the assumption (2), that our permutation is cyclic, we will reach to a quite interesting class of graphs, generalizing them. So, let us formulate:

Definition

A graph [math]X[/math], with vertices labeled [math]1,2,\ldots,N[/math], is called transitive when for any two vertices [math]i,j\in X[/math] there is a permutation [math]\sigma\in S_N[/math] such that:

• [math]\sigma[/math] maps one vertex to another, [math]\sigma(i)=j[/math].
• [math]\sigma[/math] leaves invariant the edges, [math]k-l\iff\sigma(k)-\sigma(l)[/math].

In short, what we did here is to copy the statement of Proposition 4.9, with the assumption (2) there removed, and call this a Definition. In view of this, obviously, any circulant graph is transitive. But, do we have other interesting examples?

As a first piece of answer to this question, which is very encouraging, we have:

Theorem

The cube graph, namely

[[math]] \xymatrix@R=20pt@C=20pt{ &\bullet\ar@{-}[rr]&&\bullet\\ \bullet\ar@{-}[rr]\ar@{-}[ur]&&\bullet\ar@{-}[ur]\\ &\bullet\ar@{-}[rr]\ar@{-}[uu]&&\bullet\ar@{-}[uu]\\ \bullet\ar@{-}[uu]\ar@{-}[ur]\ar@{-}[rr]&&\bullet\ar@{-}[uu]\ar@{-}[ur] } [[/math]]

is transitive, but not circulant.

Show Proof

The fact that the cube is transitive is clear, because given any two vertices [math]i,j\in X[/math], we can certainly rotate the cube in 3D, as to have [math]i\to j[/math]. As for the fact that the cube is not circulant, this is something more tricky, as follows:

(1) As a first observation, when trying to draw the cube on a circle, in a somewhat nice and intuitive way, as to have it circulant, we reach to the following picture:

[[math]] \xymatrix@R=16pt@C=16pt{ &\bullet\ar@{-}[r]\ar@{-}[drr]&\bullet\ar@{-}[dll]\\ \bullet\ar@{-}[d]\ar@{-}[ddr]&&&\bullet\ar@{-}[d]\\ \bullet\ar@{-}[uur]\ar@{-}[drr]&&&\bullet\ar@{-}[uul]\\ &\bullet\ar@{-}[r]\ar@{-}[urr]&\bullet\ar@{-}[uur]} [[/math]]

Thus, our cube is indeed not circulant, or at least not in an obvious way.

(2) However, this does not stand for a proof, and the problem of abstractly proving that the cube is not circulant remains. Normally this can be done by attempting to label the vertices in a circulant way. Indeed, up to some discussion here, that we will leave as an instructive exercise, we can always assume that [math]1,2[/math] are connected by an edge:

[[math]] 1-2 [[/math]]

(3) But with this in hand, we can now start labeling the vertices of the cube, in a circulant way. Since [math]1-2[/math] implies via our circulant graph assumption [math]2-3[/math], [math]3-4[/math], and so on, in order to start our labeling, we must pick one vertex, and then follow a path on the cube, emanating from there. But, by some obvious symmetry reasons, this means that we can always assume that our first three vertices [math]1,2,3[/math] are as follows:

[[math]] \xymatrix@R=17pt@C=20pt{ &\bullet\ar@{-}[rr]&&\bullet\\ 1\ar@{-}[rr]\ar@{-}[ur]&&2\ar@{-}[ur]\\ &\bullet\ar@{-}[rr]\ar@{-}[uu]&&\bullet\ar@{-}[uu]\\ \bullet\ar@{-}[uu]\ar@{-}[ur]\ar@{-}[rr]&&3\ar@{-}[uu]\ar@{-}[ur] } [[/math]]

(4) So, the question comes now, where the vertex 4 can be, as for all this to lead, in the end, to a circulant graph. And the point is that, among the two possible choices for the vertex 4, as new neighbors of 3, none works. Thus, our cube is indeed not circulant, and we will leave the remaining details here as an instructive exercise.

■

Let us look now for some more examples. Thinking a bit, it is in fact not necessary to go up to the cube, which is a rather advanced object, in order to have an example of a transitive, non-circulant graph, and this because two triangles will do too:

[[math]] \xymatrix@R=20pt@C=20pt{ &\bullet\ar@{-}[ddl]\ar@{-}[ddr]&&&&\bullet\ar@{-}[ddl]\ar@{-}[ddr]\\ \\ \bullet\ar@{-}[rr]&&\bullet&\ &\bullet\ar@{-}[rr]&&\bullet } [[/math]]

However, this latter graph is not connected, and so is not very good, as per our usual geometric philosophy. But, we can make it connected, by adding edges, as follows:

[[math]] \xymatrix@R=20pt@C=20pt{ &&&&\bullet\ar@{-}[ddl]\ar@{-}[ddr]\\ &\bullet\ar@{-}[ddl]\ar@{-}[ddr]\ar@{-}[urrr]\\ &&&\bullet\ar@{-}[rr]&&\bullet\\ \bullet\ar@{-}[rr]\ar@{-}[urrr]&&\bullet\ar@{-}[urrr] } [[/math]]

What we got here is a prism, and it is convenient now, for aesthetical and typographical reasons, to draw this prism on a circle, a bit like we did for the cube, at the beginning of the proof of Theorem 4.11. We are led in this way to the following statement:

Theorem

The prism, which is as follows when drawn on a circle,

[[math]] \xymatrix@R=13pt@C=28pt{ &\bullet\ar@{-}[dddl]\ar@{-}[dddr]\ar@{-}[dl]\\ \bullet\ar@{-}[rr]\ar@{-}[dddr]&&\bullet\ar@{-}[dddl]\ar@{-}[dd]\\ \\ \bullet\ar@{-}[rr]\ar@{-}[dr]&&\bullet\\ &\bullet } [[/math]]

is transitive and non-circulant too, exactly as the cube was.

Show Proof

The fact that the prism is indeed transitive follows from the above discussion, but it is convenient to view this as well directly on the above picture. Indeed:

-- The prism as drawn above has 3 obvious symmetry axes, allowing us to do many of the [math]i\to j[/math] operations required by the definition of transitivity.

-- In addition, the prism is invariant as well by the [math]120^\circ[/math] and [math]240^\circ[/math] rotations, and when combining this with the above 3 symmetries, we have all that we need.

Finally, the fact that the prism is indeed not circulant is quite clear, intuitively speaking, and this can be proved a bit as for the cube, as in the proof of Theorem 4.11.

■

Summarizing, we have interesting examples, and our theory of transitive graphs seems worth developing. In order now to reach to something more conceptual, it is pretty much clear that we must get into group theory. So, let us formulate the following definition:

Definition

A group of permutations is a subset [math]G\subset S_N[/math] which is stable under the composition of permutations, and under their inversion. We say that:

• [math]G[/math] acts transitively on the set [math]\{1,\ldots,N\}[/math] if for any two points [math]i,j[/math] we can find [math]\sigma\in G[/math] mapping one point to another, [math]\sigma(i)=j[/math].
• [math]G[/math] acts on a graph [math]X[/math] with vertices labeled [math]1,\ldots,N[/math] when each [math]\sigma\in G[/math] leaves invariant the edges, [math]k-l\iff\sigma(k)-\sigma(l)[/math].

Also, we say that [math]G[/math] acts transitively on a graph [math]X[/math] with vertices labeled [math]1,\ldots,N[/math] when it acts on [math]X[/math] in the sense of (2), and the action is transitive in the sense of (1).

All this might seem a bit heavy, but as we will soon discover, is worth the effort, because group theory is a powerful theory, and having it into our picture will be certainly a good thing, a bit similar to the update from the Stone Age to the Bronze Age. Or perhaps to the update from the Bronze Age to the Iron Age, because what we did so far in this book was sometimes non-trivial, and can be counted as Bronze Age weaponry.

As a first good surprise, once Definition 4.13 formulated and digested, our definition of the circulant and transitive graphs becomes something very simple, as follows:

Theorem

The following happen, for a graph [math]X[/math] having [math]N[/math] vertices:

• [math]X[/math] is circulant when we have an action [math]\mathbb Z_N\curvearrowright X[/math].
• [math]X[/math] is transitive when we have a transitive action [math]G\curvearrowright X[/math].

Show Proof

This is something trivial and self-explanatory, and with the remark that in (1) we do not have to say something about transitivity, because the subgroup [math]\mathbb Z_N\subset S_N[/math] is transitive, in the sense of Definition 4.13. As usual, we have called this statement Theorem instead of Proposition simply due to its theoretical importance.

■

As a second good surprise, our previous transitivity considerations regarding the cube and the prism take now a very simple form, in terms of groups, as follows:

Proposition

The following are transitive graphs:

• The cube, due to an action [math]\mathbb Z_2^3\curvearrowright X[/math].
• The prism, due to an action [math]\mathbb Z_2\times\mathbb Z_3\curvearrowright X[/math].

Show Proof

As before with Theorem 4.14, this is trivial and self-explanatory, with the actions being the obvious ones, coming from our previous study of the cube and prism.

■

Many things can be said about the transitive graphs, in general, but thinking well, what we would mostly like to have would be an extension of what we did in the previous section for the circulant graphs, including the Fourier transform material, which was something highly non-trivial and powerful, perhaps to a class of graphs smaller than that of the general transitive graphs. So, let us formulate the following definition:

Definition

A finite graph [math]X[/math] is called generalized circulant when it has a transitive action [math]G\curvearrowright X[/math], with [math]G[/math] being a finite abelian group.

And this looks like a very good definition. Indeed, as examples we have the circulant graphs, but also the cube, and the prism, since products of abelian groups are obviously abelian. So, no interesting transitive graphs lost, when assuming that [math]G[/math] is abelian.

In order now to further build on this definition, and in particular to develop our generalized Fourier transform machinery, as hoped in the above, let us temporarily leave aside the graphs [math]X[/math], and focus on the finite abelian groups [math]G[/math]. We first have:

Proposition

Given a finite abelian group [math]G[/math], the group morphisms

[[math]] \chi:G\to\mathbb T [[/math]]

with [math]\mathbb T[/math] being the unit circle, called characters of [math]G[/math], form a finite abelian group [math]\widehat{G}[/math].

Show Proof

There are several things to be proved here, the idea being as follows:

(1) Our first claim is that [math]\widehat{G}[/math] is a group, with the pointwise multiplication, namely:

[[math]] (\chi\rho)(g)=\chi(g)\rho(g) [[/math]]

Indeed, if [math]\chi,\rho[/math] are characters, so is [math]\chi\rho[/math], and so the multiplication is well-defined on [math]\widehat{G}[/math]. Regarding the unit, this is the trivial character, constructed as follows:

[[math]] 1:G\to\mathbb T\quad,\quad g\to1 [[/math]]

Finally, we have inverses, with the inverse of [math]\chi:G\to\mathbb T[/math] being its conjugate:

[[math]] \bar{\chi}:G\to\mathbb T\quad,\quad g\to\overline{\chi(g)} [[/math]]

(2) Our next claim is that [math]\widehat{G}[/math] is finite. Indeed, given a group element [math]g\in G[/math], we can talk about its order, which is smallest integer [math]k\in\mathbb N[/math] such that [math]g^k=1[/math]. Now assuming that we have a character [math]\chi:G\to\mathbb T[/math], we have the following formula:

[[math]] \chi(g)^k=1 [[/math]]

Thus [math]\chi(g)[/math] must be one of the [math]k[/math]-th roots of unity, and in particular there are finitely many choices for [math]\chi(g)[/math]. Thus, there are finitely many choices for [math]\chi[/math], as desired.

(3) Finally, the fact that [math]\widehat{G}[/math] is abelian follows from definitions, because the pointwise multiplication of functions, and in particular of characters, is commutative.

■

The above construction is quite interesting, and we have:

Theorem

The character group operation [math]G\to\widehat{G}[/math] for the finite abelian groups, called Pontrjagin duality, has the following properties:

• The dual of a cyclic group is the group itself, [math]\widehat{\mathbb Z}_N=\mathbb Z_N[/math].
• The dual of a product is the product of duals, [math]\widehat{G\times H}=\widehat{G}\times\widehat{H}[/math].
• Any product of cyclic groups [math]G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_k}[/math] is self-dual, [math]G=\widehat{G}[/math].

Show Proof

We have several things to be proved, the idea being as follows:

(1) A character [math]\chi:\mathbb Z_N\to\mathbb T[/math] is uniquely determined by its value [math]z=\chi(g)[/math] on the standard generator [math]g\in\mathbb Z_N[/math]. But this value must satisfy:

[[math]] z^N=1 [[/math]]

Thus we must have [math]z\in\mathbb Z_N[/math], with the cyclic group [math]\mathbb Z_N[/math] being regarded this time as being the group of [math]N[/math]-th roots of unity. Now conversely, any [math]N[/math]-th root of unity [math]z\in\mathbb Z_N[/math] defines a character [math]\chi:\mathbb Z_N\to\mathbb T[/math], by setting, for any [math]r\in\mathbb N[/math]:

[[math]] \chi(g^r)=z^r [[/math]]

Thus we have an identification [math]\widehat{\mathbb Z}_N=\mathbb Z_N[/math], as claimed.

(2) A character of a product of groups [math]\chi:G\times H\to\mathbb T[/math] must satisfy:

[[math]] \chi(g,h)=\chi\left[(g,1)(1,h)\right]=\chi(g,1)\chi(1,h) [[/math]]

Thus [math]\chi[/math] must appear as the product of its restrictions [math]\chi_{|G},\chi_{|H}[/math], which must be both characters, and this gives the identification in the statement.

(3) This follows from (1) and (2). Alternatively, any character [math]\chi:G\to\mathbb T[/math] is uniquely determined by its values [math]\chi(g_1),\ldots,\chi(g_k)[/math] on the standard generators of [math]\mathbb Z_{N_1},\ldots,\mathbb Z_{N_k}[/math], which must belong to [math]\mathbb Z_{N_1},\ldots,\mathbb Z_{N_k}\subset\mathbb T[/math], and this gives [math]\widehat{G}=G[/math], as claimed.

■

At a more advanced level now, we have the following result:

Theorem

The finite abelian groups are the following groups,

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

and these groups are all self-dual, [math]G=\widehat{G}[/math].

Show Proof

This is something quite tricky, the idea being as follows:

(1) In order to prove our result, assume that [math]G[/math] is finite and abelian. For any prime number [math]p\in\mathbb N[/math], let us define [math]G_p\subset G[/math] to be the subset of elements having as order a power of [math]p[/math]. Equivalently, this subset [math]G_p\subset G[/math] can be defined as follows:

[[math]] G_p=\left\{g\in G\Big|\exists k\in\mathbb N,g^{p^k}=1\right\} [[/math]]

(2) It is then routine to check, based on definitions, that each [math]G_p[/math] is a subgroup. Our claim now is that we have a direct product decomposition as follows:

[[math]] G=\prod_pG_p [[/math]]

(3) Indeed, by using the fact that our group [math]G[/math] is abelian, we have a morphism as follows, with the order of the factors when computing [math]\prod_pg_p[/math] being irrelevant:

[[math]] \prod_pG_p\to G\quad,\quad (g_p)\to\prod_pg_p [[/math]]

Moreover, it is routine to check that this morphism is both injective and surjective, via some simple manipulations, so we have our group decomposition, as in (2).

(4) Thus, we are left with proving that each component [math]G_p[/math] decomposes as a product of cyclic groups, having as orders powers of [math]p[/math], as follows:

[[math]] G_p=\mathbb Z_{p^{r_1}}\times\ldots\times\mathbb Z_{p^{r_s}} [[/math]]

But this is something that can be checked by recurrence on [math]|G_p|[/math], via some routine computations, and we are led to the conclusion in the statement.

(5) Finally, the fact that the finite abelian groups are self-dual, [math]G=\widehat{G}[/math], follows from the structure result that we just proved, and from Theorem 4.18 (3).

■

In relation now with Fourier analysis, the result is as follows:

Theorem

Given a finite abelian group [math]G[/math], we have an isomorphism as follows, obtained by linearizing/delinearizing the characters,

[[math]] C^*(G)\simeq C(\widehat{G}) [[/math]]

where [math]C^*(G)[/math] is the algebra of functions [math]\varphi:G\to\mathbb C[/math], with convolution product, and [math]C(\widehat{G})[/math] is the algebra of functions [math]\varphi:\widehat{G}\to\mathbb C[/math], with usual product.

Show Proof

There are many things going on here, the idea being as follows:

(1) Given a finite abelian group [math]G[/math], we can talk about the complex algebra [math]C(G)[/math] formed by the complex functions [math]\varphi:G\to\mathbb C[/math], with usual product, namely:

[[math]] (\varphi\psi)(g)=\varphi(g)\psi(g) [[/math]]

Observe that we have [math]C(G)\simeq\mathbb C^N[/math] as an algebra, where [math]N=|G|[/math], with this being best seen via the basis of [math]C(G)[/math] formed by the Dirac masses at the points of [math]G[/math]:

[[math]] C(G)=\left\{\sum_{g\in G}\lambda_g\delta_g\Big|\lambda_g\in\mathbb C\right\} [[/math]]

(2) On the other hand, we can talk as well about the algebra [math]C^*(G)[/math] formed by the same functions [math]\varphi:G\to\mathbb C[/math], but this time with the convolution product, namely:

[[math]] (\varphi*\psi)(g)=\sum_{h\in G}\varphi(gh^{-1})\psi(h) [[/math]]

Since we have [math]\delta_k*\delta_l=\delta_{kl}[/math] for any [math]k,l\in G[/math], as you can easily check by using the above formula, the Dirac masses [math]\delta_g\in C^*(G)[/math] behave like the group elements [math]g\in G[/math]. Thus, we can view our algebra as follows, with multiplication given by [math]g\cdot h=gh[/math], and linearity:

[[math]] C^*(G)=\left\{\sum_{g\in G}\lambda_gg\Big|\lambda_g\in\mathbb C\right\} [[/math]]

(3) Now that we know what the statement is about, let us go for the proof. The first observation is that we have a morphism of algebras as follows:

[[math]] C^*(G)\to C(\widehat{G})\quad,\quad g\to\left[\chi\to\chi(g)\right] [[/math]]

Now since on both sides we have vector spaces of dimension [math]N=|G|[/math], it is enough to check that this morphism is injective. But this is best done via Theorem 4.19, which shows that the characters [math]\chi\in\widehat{G}[/math] separate the points [math]g\in G[/math], as desired.

■

In practice now, we can clearly feel that Theorem 4.20 is related to Fourier analysis, and more specifically to the Fourier transforms and series that we know from analysis, but also to the discrete Fourier transform from the beginning of this chapter. However, all this remains a bit difficult to clarify, and we have here the following statement: \begin{fact} The following happen, regarding the locally compact abelian groups:

• What we did in the finite case, namely group characters, and construction and basic properties of the dual, can be extended to them.
• As basic examples of this, besides what we have in the finite case, and notably [math]\widehat{\mathbb Z}_N=\mathbb Z_N[/math], we have [math]\widehat{\mathbb Z}=\mathbb T[/math], [math]\widehat{\mathbb T}=\mathbb Z[/math], and also [math]\widehat{\mathbb R}=\mathbb R[/math].
• With some care for analytic aspects, [math]C^*(G)\simeq C(\widehat{G})[/math] remains true in this setting, and in the case [math]G=\mathbb R[/math], this isomorphism is the Fourier transform.

\end{fact} Obviously, all this is a bit heavy, but you get the point, there are 3 types of Fourier analysis in life, namely the “standard” one, that you might know from advanced calculus, corresponding to [math]G=\mathbb R[/math], then the “Fourier series” one, that you might know from advanced calculus too, corresponding to [math]G=\mathbb Z,\mathbb T[/math], and finally the “discrete” one that we started to learn in this book, over [math]G=\mathbb Z_N[/math] and other finite abelian groups.

In practice, all this is a bit complicated, and back now to the finite abelian groups, let us work out a softer version of all the above, which is what is really needed, in practice, when doing discrete Fourier analysis. We have here the following result:

Theorem

Given a finite abelian group [math]G[/math], with dual group [math]\widehat{G}=\{\chi:G\to\mathbb T\}[/math], consider the corresponding Fourier coupling, namely:

[[math]] \mathcal F_G:G\times\widehat{G}\to\mathbb T\quad,\quad (i,\chi)\to\chi(i) [[/math]]

• Via the standard isomorphism [math]G\simeq\widehat{G}[/math], this Fourier coupling can be regarded as a usual square matrix, [math]F_G\in M_G(\mathbb T)[/math].
• This matrix [math]F_G\in M_G(\mathbb T)[/math] is complex Hadamard, in the sense that its entries are on the unit circle, and its rows are pairwise orthogonal.
• In the case of the cyclic group [math]G=\mathbb Z_N[/math] we obtain in this way, via the standard identification [math]\mathbb Z_N=\{1,\ldots,N\}[/math], the Fourier matrix [math]F_N[/math].
• In general, when using a decomposition [math]G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_k}[/math], the corresponding Fourier matrix is given by [math]F_G=F_{N_1}\otimes\ldots\otimes F_{N_k}[/math].

Show Proof

This follows indeed by using the above finite abelian group theory:

(1) Via the identification [math]G\simeq\widehat{G}[/math], we have indeed a square matrix, given by:

[[math]] (F_G)_{i\chi}=\chi(i) [[/math]]

(2) The scalar products between distinct rows are indeed zero, as shown by:

[[math]] \lt R_i,R_j \gt =\sum_\chi\chi(i)\overline{\chi(j)} =\sum_\chi\chi(i-j) =|G|\cdot\delta_{ij} [[/math]]

(3) This follows from the well-known and elementary fact that, via the identifications [math]\mathbb Z_N=\widehat{\mathbb Z_N}=\{1,\ldots,N\}[/math], the Fourier coupling here is as follows, with [math]w=e^{2\pi i/N}[/math]:

[[math]] (i,j)\to w^{ij} [[/math]]

(4) Observe first that [math]\widehat{H\times K}=\widehat{H}\times\widehat{K}[/math] gives, at the level of the Fourier couplings, [math]F_{H\times K}=F_H\otimes F_K[/math]. Now by decomposing [math]G[/math] into cyclic groups, as in the statement, and using (3) for the cyclic components, we obtain the formula in the statement.

■

So long for circulant graphs, finite group actions, transitive graphs, finite abelian groups, discrete Fourier analysis, and Hadamard matrices. We will be back to all this in Part III of the present book, where we will systematically investigate such things.

General references

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