Characteristic Polynomial

The characteristic polynomial is the polynomial left-hand side of the characteristic equation

(1)

where is a square matrix and is the identity matrix of identical dimension. Samuelson's formula allows the characteristic polynomial to be computed recursively without divisions. The characteristic polynomial of a matrix may be computed in the Wolfram Language as CharacteristicPolynomial[m, x].

The characteristic polynomial of a matrix

(2)

can be rewritten in the particularly nice form

(3)

where is the matrix trace of and is its determinant.

Similarly, the characteristic polynomial of a matrix is

(4)

where Einstein summation has been used, which can also be written explicitly in terms of traces as

(5)

In general, the characteristic polynomial has the form

			(6)
			(7)

where is the matrix trace of the matrix , , and is the sum of the -rowed diagonal minors of the matrix (Jacobson 1974, p. 109).

Le Verrier's algorithm for computing the characteristic polynomial of a graph (Balasubramanian 1984; Trinajstić 1988; Ivanciuc and Balaban 2000, p. 89) can be formulated as the solution of the linear system

(8)

where

(9)

, and .

An algorithm due to Balasubramanian computes using the equation

(10)

where

(11)

(Balasubramanian 1985, 1985, 1991; Ivanciuc and Balaban 2000, p. 90; typo corrected) with and .

The characteristic polynomial of a graph is defined as the characteristic polynomial of its adjacency matrix and can be computed in the Wolfram Language using CharacteristicPolynomial[AdjacencyMatrix[g], x]. The precomputed characteristic polynomial of a named graph in terms of a variable can also be obtained using GraphData[graph, "CharacteristicPolynomial"][x].

Characteristic polynomials are not diagnostic for graph isomorphism, i.e., two nonisomorphic graphs may share the same characteristic polynomial. The smallest such example occurs for the two graphs on five nodes illustrated above, both of which have characteristic polynomial . The number of distinct characteristic polynomials for simple undirected graphs on , 2, ... nodes are 1, 2, 4, 11, 33, 151, 988, 11453, ... (OEIS A082104), giving the number of duplicated characteristic polynomials as 0, 0, 0, 0, 1, 5, 56, 893, 27311, ....

The following table summarizes the characteristic polynomials for some simple graphs.

graph	characteristic polynomial
complete graph
complete graph
complete graph
cyclic graph
cyclic graph
cyclic graph
cubical graph
octahedral graph
tetrahedral graph
wheel graph
wheel graph

Wolfram Web Resources