主題
Search

特徵多項式

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

特徵多項式是特徵方程左側的多項式

det(A-lambdaI)=0,
(1)

其中 A 是一個方陣，而 I 是相同維度的單位矩陣。薩繆爾森公式允許遞迴計算特徵多項式，而無需除法。矩陣 m 的特徵多項式可以在 Wolfram 語言 中計算為CharacteristicPolynomial[m, x].

一個 2×2 矩陣的特徵多項式

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

可以特別簡潔地重寫為

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

其中 Tr(A) 是 A 的矩陣的跡，而 det(A) 是其行列式。

類似地，一個 3×3 矩陣的特徵多項式是

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

其中使用了愛因斯坦求和，也可以用跡顯式地寫成

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)

一般來說，特徵多項式具有以下形式

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

其中 a_1=suma_(ii) 是矩陣 A 的矩陣的跡 Tr(A), a_n=det(A), 並且 a_i 是矩陣 A 的 i 階對角子式的和 (Jacobson 1974, p. 109)。

用於計算圖的特徵多項式的 Le Verrier 演算法 (Balasubramanian 1984; Trinajstić 1988; Ivanciuc 和 Balaban 2000, p. 89) 可以表述為線性系統的解

[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)

其中

f(x)=sum_(k=0)^nc_kx^(n-k),
(9)

c_0=-1, 並且 a_k=Tr(A^k)。

Balasubramanian 提出的演算法使用以下公式計算 c_k

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

其中

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

(Balasubramanian 1985, 1985, 1991; Ivanciuc 和 Balaban 2000, p. 90; 筆誤已更正)，其中 B_0=A 且 c_0=-1。

一個圖 g 的特徵多項式定義為其鄰接矩陣的特徵多項式，並且可以在 Wolfram 語言 中使用以下方法計算CharacteristicPolynomial[AdjacencyMatrix[g], x]。也可以使用以下方法獲得命名圖的預計算特徵多項式，以變數 x 表示GraphData[graph,"CharacteristicPolynomial"][x]。

CharacteristicPolynomialGraphs

特徵多項式不是圖同構的診斷方法，即兩個非同構圖可能共享相同的特徵多項式。最小的此類示例發生在上面說明的五個節點的兩個圖上，這兩個圖都具有特徵多項式 4x^3-x^5。對於 n=1, 2, ... 個節點的簡單無向圖，不同特徵多項式的數量為 1, 2, 4, 11, 33, 151, 988, 11453, ... (OEIS A082104)，給出重複特徵多項式的數量為 0, 0, 0, 0, 1, 5, 56, 893, 27311, ....

下表總結了一些簡單圖的特徵多項式。

圖特徵多項式
完全圖 K_2(z-1)(z+1)
完全圖 K_3-(z-2)(z+1)^2
完全圖 K_4(z-3)(z+1)^3
迴圈圖 C_3-(z-2)(z+1)^2
迴圈圖 C_4(z-2)z^2(z+2)
迴圈圖 C_5-(z-2)(z^2+z-1)^2
立方圖(z-3)(z-1)^3(z+1)^3(z+3)
八面體圖(z-4)z^3(z+2)^2
四面體圖(z-3)(z+1)^3
輪圖 W_5-z^2(z+2)(z^2-2z-4)
輪圖 W_6(z^2-2z-5)(z^2+z+1)^2

另請參閱

Cayley-Hamilton 定理, 特徵方程, 特徵值, 圖特徵值, 圖譜, 匹配多項式, 矩陣譜, 薩繆爾森公式, 穩定性指標

使用 探索

參考文獻

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 Balaban, A. T. (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.

在 上引用

特徵多項式

請引用為

Weisstein, Eric W. "特徵多項式。" 來自 Web 資源。 https://mathworld.tw/CharacteristicPolynomial.html

主題分類