Die dauerhafte von einer Quadratmatrix in der geradlinigen Algebra ist eine Funktion der der Determinante ähnlichen Matrix. Das dauerhafte, sowie die Determinante, ist ein Polynom in den Einträgen der Matrix. Sowohl dauerhaft als auch Determinante sind spezielle Fälle einer allgemeineren Funktion einer Matrix genannt den immanant.

Definition

Die dauerhafte von einer n-by-n Matrix = (a) wird als definiert

:

Die Summe hier streckt sich über alle Elemente σ von der symmetrischen Gruppe S, d. h. über alle Versetzungen der Nummern 1, 2..., n aus.

Zum Beispiel (2×2 Matrix),

:

Die Definition des dauerhaften von A unterscheidet sich von dieser der Determinante darin die Unterschriften der Versetzungen werden nicht in Betracht gezogen. Wenn man das dauerhafte als eine Karte ansieht, die n Vektoren als Argumente nimmt, dann ist es eine mehrgeradlinige Karte, und es ist symmetrisch (das Meinen, dass jede Ordnung der Vektoren auf dasselbe dauerhaft hinausläuft). Eine Formel, die Laplace für die Entwicklung einer Determinante entlang einer Reihe oder Säule ähnlich ist, ist auch für das dauerhafte gültig; alle Zeichen müssen für das dauerhafte ignoriert werden.

Die dauerhafte von einer Matrix A wird pro A, Dauerwelle A, oder Pro A manchmal mit Parenthesen um das Argument angezeigt. In seiner Monografie, Gebrauch Pro (A) für den dauerhaften von rechteckigem matrices und Gebrauch pro (A), wenn A eine Quadratmatrix ist. verwendet die Notation.

Das Wort, dauerhaft hervorgebracht mit als "fonctions symétriques permanentes" für einen zusammenhängenden Typ von Funktionen, und wurde durch im modernen, spezifischeren, Sinn verwendet.

Eigenschaften und Anwendungen

Verschieden von der Determinante hat das dauerhafte keine leichte geometrische Interpretation; es wird in combinatorics und im Behandeln boson die Funktionen von Green in der Quant-Feldtheorie hauptsächlich verwendet. Jedoch hat es zwei mit dem Graphen theoretische Interpretationen: als die Summe von Gewichten von Zyklus-Deckel eines geleiteten Graphen, und als die Summe von Gewichten von vollkommenem matchings in einem zweiteiligen Graphen.

Zyklus-Deckel

Jede Quadratmatrix kann als die Angrenzen-Matrix eines belasteten geleiteten Graphen, mit dem Darstellen des Gewichts des Kreisbogens vom Scheitelpunkt i zum Scheitelpunkt j angesehen werden.

Ein Zyklus-Deckel eines belasteten geleiteten Graphen ist eine Sammlung von mit dem Scheitelpunkt zusammenhanglosen geleiteten Zyklen im Digraph, der alle Scheitelpunkte im Graphen bedeckt. So hat jeder Scheitelpunkt i im Digraph einen einzigartigen "Nachfolger" im Zyklus-Deckel, und ist eine Versetzung darauf, wo n die Zahl von Scheitelpunkten im Digraph ist. Umgekehrt entspricht jede Versetzung darauf einem Zyklus-Deckel, in dem es einen Kreisbogen vom Scheitelpunkt i zum Scheitelpunkt für jeden ich gibt.

Wenn das Gewicht eines Zyklus-Deckels definiert wird, um das Produkt der Gewichte der Kreisbogen in jedem Zyklus, dann zu sein

:

Die dauerhafte von einer Matrix A wird als definiert

:

wo eine zu Ende Versetzung ist. So ist der dauerhafte von A der Summe der Gewichte aller Zyklus-Deckel des Digraphs gleich.

Vollkommener matchings

Eine Quadratmatrix kann auch als die biadjacency Matrix eines zweiteiligen Graphen angesehen werden, der Scheitelpunkte auf einer Seite und auf der anderen Seite, mit dem Darstellen des Gewichts des Randes vom Scheitelpunkt bis Scheitelpunkt hat. Wenn das Gewicht eines vollkommenen Zusammenbringens, das dazu zusammenpasst, definiert wird, um das Produkt der Gewichte der Ränder im Zusammenbringen, dann zu sein

:

So ist der dauerhafte von A der Summe der Gewichte des ganzen vollkommenen matchings des Graphen gleich.

0-1 permanents: das Zählen in unbelasteten Graphen

In einem unbelasteten, geleiteten, einfachen Graphen, wenn wir jeden veranlassen, 1 zu sein, wenn es einen Rand vom Scheitelpunkt i zum Scheitelpunkt j gibt, dann hat jeder Nichtnullzyklus-Deckel Gewicht 1, und hat die Angrenzen-Matrix 0-1 Einträge. So ist der dauerhafte von einem 01-Matrizen-der Zahl von Zyklus-Deckel eines unbelasteten geleiteten Graphen gleich.

Für einen unbelasteten zweiteiligen Graphen, wenn wir = 1 untergehen, wenn es einen Rand zwischen den Scheitelpunkten und und = 0 sonst gibt, dann hat jedes vollkommene Zusammenbringen Gewicht 1. So ist die Zahl von vollkommenem matchings in G der dauerhaften von der Matrix A gleich.

Minimal dauerhaft

Des ganzen doppelt stochastischen matrices haben die Matrix = 1/n (d. h. die gleichförmige Matrix) ausschließlich das kleinste dauerhafte. Das wurde von van der Waerden vermutet, und hat sich gegen Ende der 1970er Jahre unabhängig durch Falikman und Egorychev erwiesen. Der Beweis von Egorychev ist eine Anwendung der Alexandrov-Fenchel Ungleichheit.

Berechnung

Wie man

glaubt, ist das dauerhafte schwieriger zu rechnen als die Determinante. Während die Determinante in der polynomischen Zeit durch die Beseitigung von Gaussian geschätzt werden kann, kann Beseitigung von Gaussian nicht verwendet werden, um das dauerhafte zu schätzen. Außerdem ist die Computerwissenschaft der dauerhaften von einer 0-1 Matrix (Matrix, deren Einträge 0 oder 1 sind) #P-complete. So, wenn das dauerhafte in der polynomischen Zeit durch eine Methode geschätzt werden kann, dann FP = #P, der eine noch stärkere Behauptung ist als P = NP. Wenn die Einträge von A jedoch nichtnegativ sind, kann das dauerhafte ungefähr in der probabilistic polynomischen Zeit bis zu einem Fehler von εM geschätzt werden, wo M der Wert des dauerhaften ist und ε> 0 willkürlich ist.

Siehe auch

• Determinante
• Bapat-bitten Sie um Lehrsatz, eine Anwendung von dauerhaften in der Ordnungsstatistik

Weiterführende Literatur

Links

• Dauerhaft an PlanetMath