. | . | . |
Main | Links | Orders | Post | Next Page | Next + 10 |
Some Relationships between Simple Graphs and their Characteristic Polynomials
Contents
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.)
The following material is presented without proof. It contains some of the key concepts necessary for understanding the rest of the discussion.
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.
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,
If G is any graph, then its adjacency matrix shall be denoted A(G). Furthermore, the matrix A(G) xI shall be denoted M_{G}(x), or simply M when the context is clear, and its elements shall be denoted m^{G}_{ij}.
If G is a simple graph then every element of the main diagonal of M_{G}(x) is x and all other elements are either 0 or 1.
Proof:
Let the elements of A(G) be a_{ij}. Because G is simple, none of its nodes is adjacent to itself, so for all i, a_{ii }is 0. For all i, (xI)_{ii} is x. Thus for all i, m^{G}_{ii} = 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, m^{G}_{ij} = a_{ij}, which by definition is either 0 or 1.
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 m^{G}_{ip(i)}.
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).
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, m^{G}_{kp(k)} is either 0 or 1. If any one or more of these m^{G}_{kp(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, m^{G}_{kp(k)} is 1. There are l more numbers i such that p(i)=i. For each one, Result 1 gives us that m^{G}_{ip(i)} is x. t(G, p) is therefore a product of (1)^{p}, zero or more 1s, and l (x)s. That is, t(G, p) = (1)^{p}( x)^{l}.
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 M_{G}(x). Each additive term in the determinant is a product of n elements of M_{G}(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 m^{G}_{ip(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).
If G is a simple graph with n 0 nodes then the coefficient of x^{n}1 in its characteristic polynomial is 0.
Proof:
The characteristic polynomial of G is det(M_{G}(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 n1 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 n1 numbers fixed, and hence no nonzero term in x^{n}1.
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 P_{n}.
If G is a simple graph with n nodes and 0 £ m £ n then the coefficient of x^{m} 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 GS.
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 x^{m} 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 P_{nm} 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 M_{G}(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 xs to complete the proof.
If G is a simple graph then the constant term of its characteristic polynomial is the determinant of its adjacency matrix.
If G is a simple graph with n 1 nodes then the coefficient of x^{n}2 in Gs 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.
If G is a simple graph with n 2 nodes then the coefficient of x^{n}3 in Gs 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 x^{n}3; all other contributions are zero.
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 Peggs observations about the factorability of characteristic equations, which are not adequately explained herein.