6. Quotient Graphs

Suppose that $$ is a $$ matrix with characteristic polynomial $$ By inspection we can factor $$: $$ Therefore, the eigenvalues of $$ are $$, $$ and $$, and thus $$ has only three distinct eigenvalues (even though it is a $$ matrix). The algebraic multiplicity of $$ is $$ and it is thus repeated, while $$ and $$ are both simple eigenvalues. Thus, as a set, the eigenvalues of $$ are $$, whereas if we want to list all the eigenvalues of $$ in say increasing order we obtain $$ The latter is sometimes called the ``set of eigenvalues listed with multiplicities'' or the ``list of eigenvalues with multiplicities''.

If $$ is a $$ matrix and has $$ simple eigenvalues $$ (i.e., all have algebraic multiplicity $$) then each eigenspace $$ is one-dimensional (i.e., it is a line in $$ through the origin). Therefore, if $$ and $$ are two eigenvectors associated to the same eigenvalue $$ then $$ and $$ are scalar multiplies of each other, that is, $$ for some non-zero $$.

In Python, one can compute the eigenvalues and eigenvectors of a symmetric matrix by using the function eigh which is contained in the module numpy.linalg or scipy.linalg. The function eigh returns a 2-tuple where the first element is an array of the eigenvalues and the second element is an orthogonal matrix consisting of the eigenvectors. For example, a typical call to eigh is

    E, X = numpy.linalg.eigh(M)

and E is a $$ array that stores the eigenvalues and X is a $$ numpy array whose columns consist of orthonormal eigenvectors of $$. For example, to confirm that the 3rd column of X is an eigenvector whose eigenvalue is the 3rd entry of E we type

    M @ X[:, 2] - E[2] * X[:, 2]

and the returned value should be the zero vector of length $$. To verify that X is an orthogonal matrix (i.e., that $$) type:

    X.T @ X

Consider the graph $$ shown in Figure 6.1 with adjacency matrix $$

The spectrum $$ of $$ and corresponding eigenvectors written as the columns of the matrix $$ are $$ One can verify that for instance $$ is an automorphism of $$. If $$ denotes the permutation matrix of $$, one can verify that $$ which is an eigenvector of $$ with same eigenvalue as $$. As another example, one can verify that $$ and that $$. Hence, in some cases $$ is a scalar multiple of $$ and in some cases $$ is a non-scalar multiple of $$; the latter case can occur if the eigenvalue associated to $$ is repeated as it occurs with $$ and $$ (in this case $$).

Proposition 6.2.2 does not say that $$ will necessarily contain non-trivial automorphisms (of order 2). In fact, most graphs will have distinct eigenvalues and a trivial automorphism group, that is, $$. What Proposition 6.2.2 does say is that if there is any non-trivial automorphism $$ then $$ has order $$ whenever $$ has distinct eigenvalues.

Given a set $$, how many partitions of $$ are there? The total number of partitions of an $$-element set is the Bell number $$. The first several Bell numbers are $$, $$, $$, $$, $$, $$, and $$. The Bell numbers satisfy the recursion $$ See the Wiki page on \href{https://en.wikipedia.org/wiki/Bell_number}{Bell numbers} for more interesting facts.

As an example, consider $$ given by $$ Hence, $$ fixes the integer $$. Thus, if we set $$, $$, $$, $$, $$, then $$ is a partition of the vertex set $$. We say that the partition $$ is induced by the permutation $$.

Consider the graph $$ shown in Figure 6.2, which is called the Petersen graph.

One can verify that $$ is an automorphism of $$. Consider the induced partition $$ $$, and let $$ be the cells of $$. For any vertex $$, one can verify that $$, $$, and $$. For any vertex $$, one can verify that $$, $$, and $$. Lastly, for any vertex $$, one can verify that $$, $$, and $$. We summarize our results using a matrix which we denote by $$ As another example, $$ is an automorphism of $$ and the induced partition is $$. One can verify that for any $$ it holds that $$, $$, $$, and $$. Also, for any $$ it holds that $$, $$, $$, and $$. Similar verifications can be made for vertices in $$ and $$, and in this case $$

Consider again the Petersen graph in Figure 6.2. One can verify that $$ is not the partition induced by any automorphism of $$. However, one can verify that for any $$ it holds that $$, $$, and $$, that for any $$ it holds that $$, $$, and $$; and finally that for any $$ it holds that $$, $$, and $$. Hence, even though $$ is not induced by any automorphism, it still satisfies the degree conditions that are satisfied by a partition induced by an automorphism. In this case, $$

Consider the graph $$ shown in Figure 6.3, which is called the Frucht graph. This graph has a trivial automorphism group, i.e., $$. However, it contains the type of partitions that satisfy the degree conditions of the partitions induced by an automorphism. For example, for $$, one can verify that for any $$ it holds that $$, $$, and $$; for any $$ it holds that $$, $$, and $$; and finally for any $$ it holds that $$, $$, and $$. Hence, in this case $$

If $$ then $$ $$ is a partition of $$ with cells $$, $$, $$, $$, and $$ is a $$-partition. The characteristic matrix of $$ is $$ Now, since $$ has orthogonal columns then we have $$ Notice that the diagonals are just the cardinalities of the cells, i.e., $$.

Suppose that $$ has eigenvalue $$ and let $$ be a set of linearly independent eigenvectors of $$ with eigenvalue $$ ($$ is necessarily $$ the geometric multiplicity of $$). Consider the subspace $$. Let $$ so that there exists constants $$ such that $$. Then, $$ from which we see that $$, that is, $$. Hence, $$ is $$-invariant.

Another partition of the Frucht graph is $$ so that $$ is a $$ partition. One can verify that $$ has $$ linearly independent eigenvectors that are constant on the cells of $$, namely, the 5th eigenvector and the last. The remaining $$ eigenvectors sum to zero on the cells of $$. For example, for the first eigenvector $$ the sum of the entries on cell $$ is $$ (due to rounding errors) and the sum of the entires on cell $$ is $$ (again due to rounding errors).