TOPICS
Search

Characteristic Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The characteristic polynomial of an n×n square matrix A is defined here by

P_n(lambda)=det(A-lambdaI),
(1)

where I is the identity matrix of identical dimension. Its roots satisfy the characteristic equation det(A-lambdaI)=0. This convention is also used by the Wolfram Language (Wolfram Research). The alternative monic convention defines f(lambda)=det(lambdaI-A)=(-1)^nP_n(lambda) (Axler 2024, p. 363). The two conventions agree when n is even and differ by an overall sign when n is odd. They have the same roots with the same multiplicities. Samuelson's formula allows the characteristic polynomial to be computed recursively without divisions. The characteristic polynomial of a matrix m may be computed in the Wolfram Language as CharacteristicPolynomial[m, x].

The characteristic polynomial of a 2×2 matrix

P_2(x)=(a_(11)a_(22)-a_(12)a_(21))-x(a_(11)+a_(22))+x^2
(2)

can be rewritten in the particularly nice form

P_2(x)=det(A)-xTr(A)+x^2,
(3)

where Tr(A) is the matrix trace of A and det(A) is its determinant.

For a 3×3 matrix over a field of characteristic 0 or greater than 3, the characteristic polynomial is

P_3(x)=det(A)+1/2(a_(ij)a_(ji)-a_(ii)a_(jj))x+Tr(A)x^2-x^3,
(4)

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

P_3(x)=1/6[Tr^3(A)+2Tr(A^3)-3Tr(A)Tr(A^2)]-1/2[Tr^2(A)-Tr(A^2)]x+Tr(A)x^2-x^3,
(5)

The monic convention has the form

f(lambda)=det(lambdaI-A)=(-1)^nP_n(lambda)
(6)
=lambda^n-a_1lambda^(n-1)+...+(-1)^na_n,
(7)

where a_1=suma_(ii) is the matrix trace Tr(A) of the matrix A, a_n=det(A), and a_i is the sum of the i-rowed diagonal minors of the matrix A (Jacobson 1974, p. 109).

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

[1 0 ... 0 0; a_1 2 ... 0 0; a_2 a_1 ... 0 0; | ... ... ... |; a_(n-1) a_(n-2) ... a_1 n][c_1; c_2; c_3; |; c_n]=[a_1; a_2; a_3; |; a_n],
(8)

with the signed polynomial

q(x)=-det(xI-A)=sum_(k=0)^nc_kx^(n-k),
(9)

where c_0=-1 and a_k=Tr(A^k). Thus P_n(x)=(-1)^(n+1)q(x). The divisions require a field of characteristic 0 or greater than n.

The corresponding matrix recurrence computes c_k for 1<=k<=n using the equation

c_k=1/kTr(B_(k-1)),
(10)

where

B_k=A(B_(k-1)-c_kI)
(11)

(Balasubramanian 1985, 1991; Ivanciuc and Balaban 1999, p. 90) with B_0=A and c_0=-1.

The characteristic polynomial of a graph g 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 x can also be obtained using GraphData[graph, "CharacteristicPolynomial"][x].

CharacteristicPolynomialGraphs

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 4x^3-x^5. The numbers of distinct characteristic polynomials for simple graphs on n=1, 2, ... nodes are 1, 2, 4, 11, 33, 151, 988, 11453, ... (OEIS A082104). The number of characteristic polynomials shared by at least two nonisomorphic simple graphs is 0, 0, 0, 0, 1, 5, 54, 829, 23728, ... (Brouwer). Counting each polynomial once is distinct from subtracting the number of characteristic polynomials from the number of nonisomorphic simple graphs.

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

graphcharacteristic polynomial
complete graph K_2(z-1)(z+1)
complete graph K_3-(z-2)(z+1)^2
complete graph K_4(z-3)(z+1)^3
cyclic graph C_3-(z-2)(z+1)^2
cyclic graph C_4(z-2)z^2(z+2)
cyclic graph C_5-(z-2)(z^2+z-1)^2
cubical graph Q_3(z-3)(z-1)^3(z+1)^3(z+3)
octahedral graph K_(2,2,2)(z-4)z^3(z+2)^2
tetrahedral graph K_4(z-3)(z+1)^3
wheel graph W_5-z^2(z+2)(z^2-2z-4)
wheel graph W_6(z^2-2z-5)(z^2+z-1)^2

See also

Cayley-Hamilton Theorem, Characteristic Equation, Eigenvalue, Graph Eigenvalue, Graph Spectrum, Matching Polynomial, Matrix Spectrum, Samuelson's Formula, Stability Index

Explore with Wolfram|Alpha

References

Axler, S. Definition 9.63 in Linear Algebra Done Right, 4th ed. Cham, Switzerland: Springer, p. 363, 2024. https://doi.org/10.1007/978-3-031-41026-0.Balasubramanian, K. "Computer Generation of the Characteristic Polynomials of Chemical Graphs." J. Comput. Chem. 5, 387-394, 1984a. https://doi.org/10.1002/jcc.540050417.Balasubramanian, K. "The Use of Frame's Method for the Characteristic Polynomials of Chemical Graphs." Theor. Chim. Acta 65, 49-58, 1984b. https://doi.org/10.1007/BF02427579.Balasubramanian, K. "Computer-Assisted Enumeration of Walks and Self-Returning Walks on Chemical Graphs." Comput. Chem. 9, 43-52, 1985.Balasubramanian, K. "Comments on the Characteristic Polynomial of a Graph." J. Comput. Chem. 12, 248-253, 1991.Brouwer, A. E. "Numbers of Characteristic Polynomials and Cospectral Graphs for A." https://aeb.win.tue.nl/graphs/cospectral/cospectralA.html.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 83-92, 1999.Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins University Press, p. 310, 1996.Hagos, E. M. "The Characteristic Polynomial of a Graph Is Reconstructible from the Characteristic Polynomials of Its Vertex-Deleted Subgraphs and Their Complements." Elec. J. Combin. 7, R12, 2000. https://doi.org/10.37236/1490.Ivanciuc, O. and Balaban, A. T. "The Graph Description of Chemical Structures." Ch. 3 in Topological Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers and A. T. Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 59-167, 1999.Ivanciuc, P. "Chemical Graph Polynomials. Part 2. The Propagation Diagram Algorithm for the Computation of the Characteristic Polynomial of Molecular Graphs." Rev. Roumaine Chim. 37, 1341-134, 1992.Jacobson, N. Basic Algebra I. San Francisco, CA: W. H. Freeman, 1974.Krivka, P.; Jeričević, Ž.; and Trinajstić, N. "On the Computation of Characteristic Polynomial of a Chemical Graph." Int. J. Quant. Chem.: Quant. Chem. Symp. 19, 129-147, 1986.Sloane, N. J. A. Sequence A082104 in "The On-Line Encyclopedia of Integer Sequences."Trinajstić, N. "The Characteristic Polynomial of a Chemical Graph." J. Math. Chem. 2, 197-215, 1988.Wolfram Research. "CharacteristicPolynomial." https://reference.wolfram.com/language/ref/CharacteristicPolynomial.html.Zivković, T. "On the Evaluation of the Characteristic Polynomial of a Chemical Graph." J. Comput. Chem. 11, 217-222, 1990.

Referenced on Wolfram|Alpha

Characteristic Polynomial

Cite this as:

Weisstein, Eric W. "Characteristic Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CharacteristicPolynomial.html

Subject classifications