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

---

REFERENCES

Balasubramanian, K. "Computer-Generation of the Characteristic-Polynomials of Chemical Graphs." J. Comput. Chem. 5, 387-394, 1984.

Balasubramanian, K. "The Use of Frames Method for the Characteristic-Polynomials of Chemical Graphs." Theor. Chim. Acta 65, 49-58, 1984.

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.

Devillers, J. and A. T. Balaban (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 83-92, 2000.

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, No. 1, R12, 1-9, 2000.

 http://www.combinatorics.org/Volume_7/Abstracts/v7i1r12.html.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.

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, 2000.

Jacobson, N. Basic Algebra I. San Francisco: 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.

Zivković, T. "On the Evaluation of the Characteristic Polynomial of a Chemical Graph." J. Comput. Chem. 11, 217-222, 1990.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الإعلام يشارك في الاجتماع التحضيري لمناقشة الخطة الإعلامية لزيارة عاشوراء

بحضور متوليها الشرعي.. العتبة العباسية المقدسة تواصل إقامة المجالس الحسينية لإحياء شهر المحرم

قسم الشؤون الفكرية يطلق برنامجه التبليغي في أكثر من 20 دولة إفريقية

شعبتا الخطابة النسوية والتوجيه الديني تواصلان إقامة المجالس الحسينية في مرقد أبي الفضل العباس (عليه السلام)

المزيد

الآخبار الصحية

دراسة تكشف علاقة خطيرة بين عمر الأم وصحة مولودها

دراسة تحذر.. اضطراب نوم بسيط قد يسبب الموت المبكر ؟

الاستحمام بالماء الساخن.. راحة مؤقتة وأضرار دائمة للبشرة

ماذا يحدث للجسم عند تخطي وجبة الإفطار؟

المزيد

الآخبار التكنلوجية

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

السد الصيني العملاق يعيق دوران الأرض ويغيّر شكلها ؟

السعودية تطلق 10 تجارب علمية إلى محطة الفضاء الدولية

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength