This header plots the critical line of the Riemann Zeta Function.  A complete understanding wins a $1,000,000 prize.
. . .
Main   Links   Orders   Post   Next Page   Next + 10

Some Relationships between Simple Graphs and their Characteristic Polynomials

By John C. Bollinger

Contents

Introduction

In this discussion I consider simple graphs without loops. Except where noted otherwise, all graphs discussed will be assumed to have those properties. The aim is to look at relationships among graphs, their adjacency matrices, and their characteristic polynomials. The discussion can be extended to polyhedra as well, inasmuch as polyhedra can be mapped to graphs by mapping each face to a vertex and mapping the edge between each pair of adjoining faces to a connection between the corresponding nodes of the graph. (One could also just as easily go straight from polyhedron to adjacency matrix.)

The discussion is not of sufficient rigor for the mathematical literature, but it is certainly targeted above the level of the mathematical novice. I suppose that makes the mathematical hobbyist the principal audience, which is the group in which I would place myself.

(Disclaimer: I am not a graph theorist, nor indeed a professional mathematician at all, and it is likely that none of these results is novel. For the record, however, I have derived all results in this discussion de novo.)
 
 

Definitions and Background

The following material is presented without proof. It contains some of the key concepts necessary for understanding the rest of the discussion.

Given a finite set S of n elements x1, x2, …, xn, a permutation of S is any 1:1 mapping of S onto itself. It can be regarded as a reordering of an ordered collection of n distinct objects.

The simplest non-trivial permutations on S map each element to itself save two, which are each mapped to the other. Such a permutation is called a transposition. Every permutation can be represented as a composition of zero or more transpositions. These representations are not unique, but it is the case that if a permutation p can be expressed as the composition of an even number of transpositions then every such expression of p contains an even number of transpositions. p is then called an even permutation. Permutations that are not even are odd, and every representation of an odd permutation as a composition of transpositions contains an odd number of transpositions. The set of all permutations on a given set form a group under the composition operation.

 Let A = ( aij ) be an n x n matrix. Let P be the set of all permutations on set { 1, 2, …, n }.  The determinant of A, |A| or det(A), is the sum over all elements, p, of P of (–1)p times the product over i=1,n of aip(i), where (–1)p is defined to be 1 when p is even and –1 when p is odd. For the purpose of this discussion (principally Result 6), we define the determinant of an empty (i.e., 0 x 0) matrix to be 1. For the purpose of this discussion, the characteristic polynomial of an n x n matrix A is the determinant of (A – xI), where I is the n-dimensional identity matrix. This is standard up to the sign, for which there seems to be no consensus. A simple graph is a set of finitely many points (nodes) together with a set of connections between pairs of those points, such that no two distinct connections join the same two points and no connection joins any point to itself. One node is adjacent to another node if and only if there is a connection between them. If G is a graph with nodes xi, i=1,n, then the adjacency matrix A(G) is the n x n matrix with elements aij such that aij = 1 if xi is adjacent to xj, and 0 otherwise. If G is a simple graph then A(G) must be symmetric about the main diagonal. A simple graph can be reconstructed from its adjacency matrix. We will define the characteristic polynomial of a simple graph to be the characteristic polynomial of its adjacency matrix. If S is a subset of the nodes of G, then G – S is the subgraph of G formed by removing all nodes in S, and all connections to them, from G. Discussion

The main theme of this discussion is that information about the form of a simple graph can be gleaned from its characteristic polynomial. We approach this topic by way of considering the additive terms in the determinant calculation. But first,

Definition 1

If G is any graph, then its adjacency matrix shall be denoted A(G). Furthermore, the matrix A(G) – xI shall be denoted MG(x), or simply M when the context is clear, and its elements shall be denoted mGij.

 and Result 1

If G is a simple graph then every element of the main diagonal of MG(x) is –x and all other elements are either 0 or 1.

Proof:

Let the elements of A(G) be aij. Because G is simple, none of its nodes is adjacent to itself, so for all i, aii is 0. For all i, (xI)ii is x. Thus for all i, mGii = 0 – x = –x. Every element of A(G) is either 0 or 1, and all (xI)ij are 0 where i is different from j, so it follows that where i is different from j, mGij = aij, which by definition is either 0 or 1.

 We are now prepared to start considering the additive terms in det(MG(x)). Each term is associated with a distinct permutation, p, of set { 1, 2, …, n }, where n is the number of nodes of G. It is convenient to write Definition 2

If G is any graph on n nodes and p is a permutation of the set { 1, 2, …, n }, then we define t(G, p) = (–1)p times the product over i=1,n of mGip(i).

 The following result then comes directly from Definition 2 and the definitions of the determinant and the characteristic polynomial of a graph; it is given without further proof. Result 2

If G is any graph on n nodes then its characteristic polynomial is the sum over all distinct permutations of { 1, 2, …, n } of t(G, p).

 This prepares the way for Result 3

If G is a simple graph containing n nodes and p is a permutation of { 1, 2, …, n } which leaves l elements fixed, then t(G, p) is either 0 or (–1)p( –x)l.

Proof:

First consider the numbers not left fixed by p. For each such number k, p(k) is different from k, and thus by Result 1, mGkp(k) is either 0 or 1. If any one or more of these mGkp(k) is 0 then t(G, p) is identically 0 and the result is correct. Suppose, then, that for all k such that p(k) is different from k, mGkp(k) is 1. There are l more numbers i such that p(i)=i. For each one, Result 1 gives us that mGip(i) is –x. t(G, p) is therefore a product of (–1)p, zero or more 1’s, and l (–x)’s. That is, t(G, p) = (–1)p( –x)l.

 With that, it is straightforward to show Result 4

If G is a simple graph with n nodes then the highest-order nonzero term of its characteristic polynomial is (–x)n.

Proof:

The characteristic polynomial of G is the determinant of MG(x). Each additive term in the determinant is a product of n elements of MG(x), and is characterized by a particular permutation, p, of the natural numbers from 1 to n. Each distinct such permutation provides one term. In particular, the identity permutation provides one term, and because the identity permutation is even and leaves all operands fixed, we have from Result 3 that t(G, I) is either 0 or (–x)n.  As we consider the proof of Result 3, however, we see that the term associated with a polynomial p is zero if and only if there is an i, 1 £ i£ n, such that p(i) is different from i and mGip(i) = 0. By definition there can be no such i for the identity permutation, therefore t(G, I) = (–x)n. No other distinct permutation of the set { 1, …, n } can leave all n numbers fixed, for then it would be the same as I, nor can any other such permutation leave more numbers fixed because each has only n numbers in its domain, hence all other terms are lower-order than the one associated with I. Thus when the sum of all the terms is computed, the highest-order term is equal to t(G, I).

 It is perhaps even more straightforward to show Result 5

If G is a simple graph with n 0 nodes then the coefficient of xn–1 in its characteristic polynomial is 0.

Proof:

The characteristic polynomial of G is det(MG(x)). Each additive term in the determinant is associated with a distinct permutation, p, of { 1, …, n }. From Result 3 we have that t(G, p) is either 0 or ±(–x)l, where l is the number of numbers left fixed by p. Suppose p leaves n–1 numbers fixed. Now consider the one other number; call it k. What are the possible values of p(k)? Because p is a 1:1 mapping from { 1, …, n } onto itself, and because every element of { 1, …, n } other than k is already an image of itself under p, the only possible value of p(k) is k. Therefore the total number of numbers left fixed by p is n, p is the identity permutation, and by Result 4, t(G, p) = (–x)n. There is thus no permutation that leaves exactly n–1 numbers fixed, and hence no nonzero term in xn–1.

 The same technique can be extended to prove results for successively lower-order terms, but it is more fruitful to concentrate now on a more general result, which will then obviate proofs for the individual cases. In order to do so, it is useful to first introduce some additional definitions regarding permutations: Definition 3

If S is a finite set then the group of all permutations on S is designated P(S).

If S is the set of natural numbers i, 1 £ i £ n, then P(S) is also designated Pn.

 This provides enough background for the central result of this work: Result 6

If G is a simple graph with n nodes and 0 £ m £ n then the coefficient of xm in the characteristic polynomial of G is (–1)m times the sum over all m-element subsets, S, of the nodes of G of the determinant of the adjacency matrix of G–S.

Proof:

Results 4 and 5 prove this result for special cases m = n and m = n –1, respectively. The proof gets complicated for terms in xm with general m; I provide only an outline here. Result 3 tells us that we need only consider the additive terms of the determinant associated with permutations leaving exactly m numbers fixed. Divide the set of all such permutations into subsets such that in each subset, all permutations leave the same m numbers fixed. Associate each such subset with the m-element subset S of the nodes of G that corresponds to those m fixed numbers. Show that we can construct a renumbering of the nodes of G such that the renumbered nodes of G – S are assigned the numbers from 1 to n – m. We can use the same renumbering to map the set of permutations associated with S to a subset of Pn–m and to construct the adjacency matrix of G – S from the adjacency matrix of G. We can then map all the terms in the determinant of the adjacency matrix of G – S back to terms in the determinant of MG(x), noting that the only terms thereby missing from det(A(G – S)) are those containing elements of the main diagonal. Because G is simple it has no loops, and thus neither does G – S; therefore all of the elements of the main diagonal of its adjacency matrix are zero and the missing terms of the determinant are all identically zero. Observe the combined factor of (–1)m associated with the x’s to complete the proof.

Corollary

If G is a simple graph then the constant term of its characteristic polynomial is the determinant of its adjacency matrix.

 Now we can look at some of the implications of this result. The first one immediately provides a new handle on interpreting the characteristic polynomial of a graph: Result 7

If G is a simple graph with n 1 nodes then the coefficient of xn–2 in G’s characteristic polynomial is c(–1)n–1, where c is the number of connections in G.

Proof:

In this case the sum specified by Result 6 is over all 2-node subgraphs of G. The adjacency matrix of each such subgraph is either all zero (with determinant zero) if there is no connection between the two nodes, or zero along the main diagonal and one elsewhere (with determinant –1) if there is a connection between the two nodes. Each two nodes have a connection in their two-node subgraph if and only if they have a connection in G, and no two nodes have more than one connection, so by Result 6, each connection in G contributes (–1) (–1)n–2 = (–1)n–1 to the sum, and there are no other nonzero contributions.

 Furthermore, Result 8

If G is a simple graph with n 2 nodes then the coefficient of xn–3 in G’s characteristic polynomial is 2c(–1)n–1, where c is the number of unique 3-cycles in G.

Proof:

In this case the sum specified by Result 6 is over all 3-node subgraphs of G. There are eight possible adjacency matrices for these subgraphs, but all have determinant zero except the one with ones everywhere except the main diagonal, which is all zero. That matrix corresponds to a 3-cycle, and has determinant 2. By result 5, therefore, each unique 3-cycle contributes 2(–1)n–3 = 2(–1)n–1 to the coefficient of xn–3; all other contributions are zero.

 Unfortunately, the relationships between a graph’s topology and its characteristic polynomial become considerably more complicated as we go on to lower-order variable terms.
 
 

Avenues for Future Work

It should be clear from Result 6 that determinants of adjacency matrices are very important, but more work needs to be done to understand their significance. Furthermore, this work was inspired by Ed Pegg’s observations about the factorability of characteristic equations, which are not adequately explained herein.