6. Quotient Graphs

Suppose that $\mathbf{M}$ is a $6\times 6$ matrix with characteristic polynomial $$p(x)=det(x\mathbf{I}-\mathbf{M})=x^6-4x^5-12x^4.$$ By inspection we can factor $p(x)$: $$p(x)=x^4(x^2-4x-12)=x^4(x-6)(x+2).$$ Therefore, the eigenvalues of $\mathbf{M}$ are ${\lambda }_1=0$, ${\lambda }_2=6$ and ${\lambda }_3=-2$, and thus $\mathbf{M}$ has only three distinct eigenvalues (even though it is a $6\times 6$ matrix). The algebraic multiplicity of ${\lambda }_1$ is $4$ and it is thus repeated, while ${\lambda }_2$ and ${\lambda }_3$ are both simple eigenvalues. Thus, as a set, the eigenvalues of $\mathbf{M}$ are $\{0,6,-2\}$, whereas if we want to list all the eigenvalues of $\mathbf{M}$ in say increasing order we obtain $$(-2,0,0,0,0,6).$$ The latter is sometimes called the ``set of eigenvalues listed with multiplicities'' or the ``list of eigenvalues with multiplicities''.

If $\mathbf{M}$ is a $n\times n$ matrix and has $n$ simple eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ (i.e., all have algebraic multiplicity $1$) then each eigenspace $\ker ({\lambda }_i\mathbf{I}-\mathbf{M})$ is one-dimensional (i.e., it is a line in ${\mathbb{R}}^n$ through the origin). Therefore, if $\mathbf{v}$ and $\mathbf{w}$ are two eigenvectors associated to the same eigenvalue ${\lambda }_i$ then $\mathbf{v}$ and $\mathbf{w}$ are scalar multiplies of each other, that is, $\mathbf{v}=\alpha \mathbf{w}$ for some non-zero $\alpha \in \mathbb{R}$.

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).