主题
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 定理, 特征方程, 特征值, 图特征值, 图谱, 匹配多项式, 矩阵谱, 萨缪尔森公式, 稳定性指标

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

特征多项式

请引用为

Weisstein, Eric W. "特征多项式。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CharacteristicPolynomial.html

主题分类