4a. Circulant graphs
You might have noticed already, some graphs look good, and some other look bad. This is of course a matter of taste, and there are several possible notions for what “good” should mean, and with this being a potential source of serious mathematical matter. As an example, we have already met a particularly beautiful graph before, namely:
Such a graph is called a tree, because when looking at a tree from the above, what you see is something like this. In general, trees can be axiomatized as follows:
A tree is a graph having no cycles. That is, there is no loop
And aren't trees beautiful, hope you agree with me. But it is not about trees that we want to talk about here, these are in fact quite complicated mathematical objects, and we will keep them for later. As an alternative to them, we have the circulant graphs, which are equally beautiful, but in a somewhat opposite sense. Here is one, which is actually the most important graph in the history of mankind, along with the fire graph:
Here is another circulant graph, again with 8 vertices, again with the picture suggesting the name “circulant”, and of course, again beautiful as well:
You get the point with these graphs, we are trying here to get in a sense which is opposite to that of Definition 4.1, with the cycles being not only welcome, but somehow mandatory. In general, the circulant graphs can be axiomatized as follows:
A graph is called circulant if, when drawn with its vertices on a circle, equally spaced, it is invariant under rotations.
To be more precise, this is the definition of the circulant graphs, when the vertices are labeled in advance [math]1,\ldots,N[/math]. In general, when the vertices are not labeled in advance, the convention is that the graph is called circulant when it is possible to label the vertices [math]1,\ldots,N[/math], as for the graph to become circulant in the above sense.
In order to understand this, let us pick a graph which is obviously circulant, such as the wheel graph above, and mess up the labeling of the vertices, see what we get. For this purpose, let us put some random labels [math]1,2,\dots,8[/math] on our wheel graph, say as follows:
Now let us redraw this graph, with the vertices [math]1,2,\ldots,8[/math] ordered on a circle, equally spaced, as Definition 4.2 requires. We get something not very beautiful, as follows:
So, here is the point. This graph, regarded as a graph with vertices labeled [math]1,2,\ldots,8[/math] is obviously not circulant, in the sense of Definition 4.2. However, when removing the labels, this graph does become circulant, as per our conventions above.
All this might seem a bit confusing, when first seen, and you are probably in this situation, so here is a precise statement in this sense, coming with a full proof:
The following graph is circulant, despite its bad look,
As already mentioned, this normally follows from the above discussion, but let us prove this as well directly. The idea is as follows:
(1) Let us label the vertices of our graph as follows, and I will explain in moment where this tricky labeling choice comes from:
Now let us redraw this graph, with the vertices [math]1,2,\ldots,8[/math] ordered on a circle, equally spaced, as Definition 4.2 requires. We get something very nice, as follows:
Thus, our original graph was indeed circulant, as stated.
(2) In order for everything to be fully clarified, we still must explain where the tricky labeling choice in (1) comes from. For this purpose, let us recall where the graph in the statement came from. Well, this graph was obtained by messing up the labeling of the vertices of the wheel graph, by using the following permutation:
The point now is that, if we want to unmess our graph, we must use the inverse of the above permutation, obtained by reading things upside-down, which is given by:
Thus, we must label our vertices [math]1,5,4,6,2,8,7,3[/math], precisely as done in (1).
As a conclusion to all this, deciding whether a graph is circulant or not is not an easy business. In what follows we will rather focus on the graphs which come by definition in circulant form, and leave decision problems for arbitrary graphs for later.
As basic examples now of circulant graphs, we have the triangle, the square, the pentagon, the hexagon and so on. As usual, let us record the formula of the adjacency matrix for such graphs. In the general case of the [math]N[/math]-gon, this is as follows:
The adjacency matrix of the [math]N[/math]-gon is
This is clear indeed from definitions, because with the indices taken modulo [math]N[/math], and arranged on a circle, being neighbor means [math]i=j\pm1[/math], and so [math]|i-j|=1[/math].
Now observe that the adjacency matrix computed above best looks when written in usual matrix form, with its circulant nature being quite obvious. As an illustration for this, here is the adjacency matrix of the hexagon, which is obviously circulant:
Passed the [math]N[/math]-gons, we can have more examples of circulant graphs by adding spokes to the [math]N[/math]-gons. Here is a hexagonal wheel, that we already met in chapter 1:
Of course, not all circulant graphs appear in this way. As an example, here is another sort of “hexagonal wheel”, without spokes, namely the Star of David:
But probably enough examples, you got the point, and time now to do some theory. Inspired by the above examples of explicit adjacency matrices, we have:
A graph is circulant precisely when its adjacency matrix is circulant, in the sense that it is of the following form, with the indices taken modulo [math]N[/math]:
This is something quite obvious. Indeed, at [math]N=4[/math] for instance, our assumption that [math]X[/math] is circulant means that the adjacency matrix must look as follows:
Now let us call [math]\gamma[/math] the first row vector, [math](x,y,z,t)[/math]. With matrix indices [math]0,1,2,3[/math], taken modulo 4, as indicated in the statement, our matrix is then given by:
In the general case, [math]N\in\mathbb N[/math], the situation is similar, and this leads to the result.
Observe that the above result is not the end of the story, because we still have to discuss when a circulant matrix is symmetric, and has 0 on the diagonal. But this is something easy to do, and our final result is then as follows:
The adjacency matrices of the circulant graphs are precisely the matrices of the following form, with indices [math]0,1,\ldots,N-1[/math], taken modulo [math]N[/math],
This follows from our observations in Proposition 4.5, because:
(1) We know from there that we have [math]d_{ij}=\gamma_{j-i}[/math].
(2) The symmetry of [math]d[/math] translates into the condition [math]\gamma_i=\gamma_{-i}[/math].
(3) The fact that [math]d[/math] has 0 on the diagonal translates into the condition [math]\gamma_0=0[/math].
All this is very nice, and with the circulant graphs being the same as the vectors [math]\gamma\in(0,1)^N[/math], subject to the simple assumptions above, this suggests that this might be the end of the story. Error. Recall that in chapter 2 we studied the [math]N[/math]-simplex from a spectral point of view, and got into non-trivial things. But this [math]N[/math]-simplex is, perhaps in rivalry with the [math]N[/math]-gon, the simplest example of a circulant graph.
So, let us first recall our findings from chapter 2. We have seen there that the adjacency matrix of the simplex, with a copy of the identity added for simplifying things, diagonalizes as follows, with [math]F_N=(w^{ij})_{ij}[/math] with [math]w=e^{2\pi i/N}[/math] being the Fourier matrix:
More generally now, going towards the case of the general circulant graphs, we have the following result, which is something standard in discrete Fourier analysis:
For a matrix [math]A\in M_N(\mathbb C)[/math], the following are equivalent,
- [math]A[/math] is circulant, [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_NQF_N^*[/math], for a certain diagonal matrix [math]Q[/math],
and if so, [math]\xi=F_N^*q[/math], where [math]q\in\mathbb C^N[/math] is the vector formed by the diagonal entries of [math]Q[/math].
This follows from some basic computations with roots of unity, as follows:
[math](1)\implies(2)[/math] Assuming [math]A_{ij}=\xi_{j-i}[/math], the matrix [math]Q=F_N^*AF_N[/math] is indeed diagonal, as shown by the following computation:
[math](2)\implies(1)[/math] Assuming [math]Q=diag(q_1,\ldots,q_N)[/math], the matrix [math]A=F_NQF_N^*[/math] is indeed circulant, as shown by the following computation:
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:
Thus, we are led to the conclusions in the statement.
The above result is something quite powerful, and useful, and suggests doing everything in Fourier, when dealing with the circulant matrices. And we can use here:
The various basic sets of [math]N\times N[/math] circulant matrices are as follows, with the convention that associated to any [math]q\in\mathbb C^N[/math] is the matrix [math]Q=diag(q_1,\ldots,q_N)[/math]:
- The set of all circulant matrices is:
[[math]] M_N(\mathbb C)^{circ}=\left\{F_NQF_N^*\Big|q\in\mathbb C^N\right\} [[/math]]
- The set of all circulant unitary matrices is:
[[math]] U_N^{circ}=\left\{\frac{1}{N}F_NQF_N^*\Big|q\in\mathbb T^N\right\} [[/math]]
- The set of all circulant orthogonal matrices is:
[[math]] O_N^{circ}=\left\{\frac{1}{N}F_NQF_N^*\Big|q\in\mathbb T^N,\bar{q}_i=q_{-i},\forall i\right\} [[/math]]
In addition, in this picture, the first row vector of [math]F_NQF_N^*[/math] is given by [math]\xi=F_N^*q[/math].
All this follows from Theorem 4.7, as follows:
(1) This assertion, along with the last one, is Theorem 4.7 itself.
(2) This is clear from (1), and from the fact that the rescaled matrix [math]F_N/\sqrt{N}[/math] is unitary, because the eigenvalues of a unitary matrix must be on the unit circle [math]\mathbb T[/math].
(3) This follows from (2), because the matrix is real when [math]\xi_i=\bar{\xi}_i[/math], and in Fourier transform, [math]\xi=F_N^*q[/math], this corresponds to the condition [math]\bar{q}_i=q_{-i}[/math].
There are many other things that can be said about the circulant matrices, and all this is quite interesting, in relation with the circulant graphs. We will be back to this.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].