Permanent -- 来自 Wolfram MathWorld

积和式

积和式是行列式的类似物，其中按子式展开式中的所有符号都取为正号。矩阵的积和式是的系数，在

(1)

(Vardi 1991)。另一个等式是雷瑟公式

$perm(a_(ij))=(-1)^nsum_(s subset= {1,...,n})(-1)^(|s|)product_(i=1)^nsum_(j in s)a_(ij),$

(2)

其中求和是对的所有子集进行的，而是中元素的数量 (Vardi 1991)。Muir (1960, p. 19) 使用符号来表示积和式。

积和式可以在 Wolfram 语言中实现为

  Permanent[m_List] :=
    With[{v = Array[x, Length[m]]},
      Coefficient[Times @@ (m.v), Times @@ v]
  ]

积和式的计算在代数复杂性理论中得到了相当广泛的研究。已知最佳算法的复杂度随着矩阵大小的指数增长 (Knuth 1998, p. 499)，考虑到积和式与易处理的行列式的相似性，这似乎非常令人惊讶。积和式的计算是 #P-完全问题 (即 sharp-P 完全问题；Valiant 1979)。

如果是一个酉矩阵，那么

(3)

(Minc 1978, p. 25; Vardi 1991)。对于 (0,1)-矩阵，最大积和式为，对应于所有元素都为 1。

另请参阅

行列式, 弗罗贝尼乌斯-柯尼希定理, Immanant, 雷瑟公式, 舒尔矩阵

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Borovskikh, Y. V. 和 Korolyuk, V. S. Random Permanents. Philadelphia, PA: Coronet Books, 1994.Comtet, L. "Permanents." §4.9 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 197-198, 1974.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 51, 1997.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, pp. 499 和 515-516, 1998.Minc, H. Permanents. Reading, MA: Addison-Wesley, 1978.Muir, T. §27 in A Treatise on the Theory of Determinants. New York: Dover, p. 19 1960.Seifter, N. "Upper Bounds for Permanents of

-Matrices." Israel J. Math. 48, 69-78, 1984.Valiant, L. G. "The Complexity of Computing the Permanent." Theoret. Comp. Sci. 8, 189-201, 1979.Vardi, I. "Permanents." §6.1 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 108 和 110-112, 1991.Wang, E. T.-H. "On Permanents of

-Matrices." Israel J. Math. 18, 353-361, 1974.

在 Wolfram|Alpha 上被引用

积和式

请引用本文为

Weisstein, Eric W. "Permanent." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Permanent.html