WikiDer > Festanstellung (Mathematik)

In dem Lineare Algebra, eine Unterregion der Mathematik, ist der dauerhaft von a quadratische Matrix${Anzeigestil A}$, genau wie die bestimmend, eine Funktion der Elemente von ${Anzeigestil A}$ die auf ähnliche Weise berechnet wird, außer dass die Summanden im ständigen Nein Omen erhalten, wie bei der Determinante.

Der Begriff „permanent“ leitet sich von dem Begriff „fonctions symétriques permanents“ ab, geprägt von Cauchy 1812 für ein verwandtes Konzept.^[1]. In seiner heutigen Bedeutung wurde der Begriff 1882 von der schottischMathematiker Sir Thomas Muir.

Definition

Die Dauerwelle ${displaystyle mathrm {per} (A)}$ des ${Anzeigestil n imes n}$-Matrix ${Displaystil A=(a_{rk})}$ ist definiert durch:

${displaystyle mathrm {per} (A)=Summe _{Sigma}prod_{r=1}^{n}a_{r,sigma (r)}=Summe _{Sigma}a_{1,Sigma (1)} a_{2,sigma (2)}ldots a_{n,sigma (n)}}$,

in dem die Summe läuft über alles Permutationen${Displaystil-Sigma}$ der Zahlen 1 bis ${displaystyle n}$.

Berechnung

Die Berechnung der bleibenden Werte einer Matrix erfordert einige Berechnungen. Es gibt einige Formeln, die die Berechnung vereinfachen.

Formelformel der Spione

Der niederländische Mathematiker Jaap Spies gibt in einem kürzlich erschienenen Artikel im Neues Archiv für Mathematik^[2] eine Formel, die er bereits 2006 in einem früheren Artikel im NAW erwähnte.^[3]

Spies stellt fest, dass die Dauerwelle der Koeffizient von ist ${displaystyle x_{1}x_{2}ldots x_{n}}$ in dem Polynom

${displaystyle P(x_{1},x_{2},ldots ,x_{n})=prod _{r=1}^{n}Summe _{k=1}^{n}a_{rk}x_{ k}=}$

${displaystyle =prod_{r=1}^{n}(a_{r1}x_{1} a_{r2}x_{2} ldots a_{rn}x_{n})}$

Definieren

${displaystyle Q(x_{1},x_{2},ldots ,x_{n})=(prod_{i=1}^{n}x_{i})cdot P(x_{1},x_{2 },ldots,x_{n})}$

und berechne die Summe über alle möglichen ${displaystyle x_{i}=pm 1}$:

${displaystyle sum _{x_{i}=pm 1}Q(x_{1},x_{2},ldots ,x_{n})}$

Dann trägt nur der Begriff

${displaystyle mathrm {per} (A)cdot x_{1}x_{2}ldots x_{n}}$

im ${Anzeigestil P(x_{1},x_{2},ldots,x_{n})}$ tragen Sie immer zu dieser Summe bei, denn ${displaystyle x_{i}^{2}=1}$ vor dem ${displaystyle i=1,2,ldots,n}$.

Ein Term, bei dem der Faktor ${displaystyle x_{k}}$ fehlt in ${displaystyle P(x_{1},ldots,x_{n})}$ zählt einmal als ${displaystyle t}$ und einmal als ${displaystyle -t}$.

Es gibt ${Displaystil 2^{n}}$ Möglichkeiten mit ${displaystyle x_{i}=pm 1}$ also die dauerhafte von ${Anzeigestil A}$ ist

${displaystyle mathrm {per} (A)=2^{-n}cdot sum _{x_{i}=pm 1}Q(x_{1},x_{2},ldots ,x_{n})}$

Aus Symmetriegründen kann die Formel vereinfacht werden durch a ${displaystyle x_{k}}$ wählen, zum Beispiel ${displaystyle x_{1}=1}$. Es gibt dann ${Displaystil 2^{n-1}}$ Chancen. Die Formel lautet dann:

${displaystyle mathrm {per} (A)={frac {1}{2^{n-1}}}cdot sum _{x_{1}=1,x_{j}=pm 1,j>1}(prod _{i=1}^{n}x_{i})prod _{i=1}^{n}Summe _{j=1}^{n}a_{ij}x_{j}}$

Vergleichen Sie diese Formel mit der folgenden Formel von Glynn.

Rysers Formel

Die Berechnung der bleibenden mit der Formel aus der Definition ist ziemlich mühsam und erfordert ${displaystyle n!cdot n}$Rechenoperationen. Das amerikanischMathematikerH. J. Ryser veröffentlichte 1963 eine schnellere Formel, die bis heute die schnellste ist Algorithmus dient der genauen Berechnung der Dauerwelle. Die Formel von Ryser lautet:

${Anzeigestil {m {per}}(A)=Summe _{k=0}^{n-1}(-1)^{k}Sigma _{k}}$,

in welchem ${displaystyle Sigma_{k}}$ die Summe ist über alle Matrizen ${Displaystil A_{k}}$ der Produkte ${displaystyle pi(A_{k})}$ der steigenden Summen von ${Displaystil A_{k}}$, eine Matrix, die besteht aus ${Anzeigestil A}$ verursacht durch ${displaystyle k}$ Spalten löschen.

${displaystyle Sigma _{k}=Summe _{{i_{1},ldots ,i_{n-k}}}pi (A_{k})}$,

in welchem

${displaystyle pi (A_{k})=prod_{r=1}^{n}left(a_{r,i_{1}} ldots a_{r,i_{n-k}}ight)}$

Ausgeschrieben in den Elementen von ${Anzeigestil A}$ die formel lautet:

${displaystyle {m {pro}}(A)=(-1)^{n}summe _{Ssubset {1,ldots,n}}(-1)^{|S|}prod _{i=1}^ {n}Summe _{jin S}a_{ij}}$

Die Anzahl der arithmetischen Operationen, die mit der Ryser-Formel erforderlich sind, liegt in der Größenordnung ${Displaystil 2^{n}n^{2}}$.

Glynn .s Formel

Eine andere Formel ist aus dem australisch Mathematiker David G. Glynn, veröffentlicht im Jahr 2010, und rechnerisch genauso schnell wie die Ryser-Formel. Glynns Formel lautet, sofern die Körpereigenschaft ungleich 2 ist:

${displaystyle {m {per}}(A)={frac {1}{2^{n-1}}}sum _{delta }left(prod_{k=1}^{n}delta _{k} ight)prod _{j=1}^{n}Summe _{i=1}^{n}Delta _{i}a_{ij}.}$

Darin läuft die erste Summe über alle ${Displaystil 2^{n-1}}$ Reihen ${Anzeigestil-Delta =(1,Delta_{2},ldots,Delta_{n})}$ mit ${Displaystil-Delta _{i}=pm 1,i=2,ldots,n}$.

Entwicklung nach Zeile oder Spalte

Wie die Determinante kann auch die bleibende durch Entwicklung zu einer Zeile oder Spalte berechnet werden. Die Entwicklung hin zum ${displaystyle k}$- die Spalte lautet:

${Anzeigestil {m {pro}}(A)=Summe _{r=1}^{n}a_{rk}{m {pro}}(A_{[rk]}),}$

in welchem ${Displaystil A_{[rk]}}$ ist die Matrix aus ${Anzeigestil A}$ das${displaystyle k}$-die Säule und die ${displaystyle r}$- Zeile löschen.

Die Entwicklung zu einer Reihe ist ähnlich definiert.

Beispiele

In zwei Dimensionen

${displaystyle {m {pro}}(A)=a_{11}a_{22} a_{12}a_{21}}$

Als Koeffizient von ${displaystyle x_{1}x_{2}}$ im

${displaystyle (a_{11}x_{1} a_{12}x_{2})(a_{21}x_{1} a_{22}x_{2})=a_{11}a_{21}x_{1 }^{2} (a_{11}a_{22} a_{12}a_{21})x_{1}x_{2} a_{12}a_{22}x_{2}^{2}}$

Mit der Ryser-Formel:

${displaystyle Sigma _{0}=(a_{11} a_{12})(a_{21} a_{22})=a_{11}a_{21} a_{11}a_{22} a_{12}a_ {21} a_{12}a_{22}}$

${displaystyle Sigma _{1}=pi left({ egin{bmatrix}a_{11}/a_{21}end{bmatrix}}ight) pi left({ egin{bmatrix}a_{12}/a_{22}end {bmatrix}}ight)=a_{11}a_{21} a_{12}a_{22}}$

${displaystyle {m {per}}(A)=Sigma _{0}-Sigma _{1}=a_{11}a_{22} a_{12}a_{21}}$

Mit Glynns Formel.

Es gibt 2 Reihen: ${Anzeigestil (1,1)}$ und ${Anzeigestil (1,-1)}$

${displaystyle {m {per}}(A)={ frac {1}{2}}left(1cdot 1(a_{11} a_{21})(a_{12} a_{22}) 1cdot (-1) (a_{11}-a_{21})(a_{12}-a_{22})Nacht)=}$

${displaystyle ={ frac {1}{2}}links((a_{11}a_{12} a_{11}a_{22} a_{21}a_{12} a_{21}a_{22})-( a_{11}a_{12}-a_{11}a_{22}-a_{21}a_{12} a_{21}a_{22})ight)=a_{11}a_{22} a_{12} a_{21}}$

In drei Dimensionen

${displaystyle {m {pro}}(A)=a_{11}a_{22}a_{33} a_{11}a_{23}a_{32} a_{12}a_{21}a_{33} a_{ 12}a_{23}a_{31} a_{13}a_{21}a_{32} a_{13}a_{22}a_{31}}$

Als Koeffizient von ${displaystyle x_{1}x_{2}x_{3}}$ im

${displaystyle (a_{11}x_{1} a_{12}x_{2} a_{13}x_{3})(a_{21}x_{1} a_{22}x_{2} a_{23}x_ {3})(a_{31}x_{1} a_{32}x_{2} a_{33}x_{3})=}$

${displaystyle ldots (a_{11}a_{22}a_{33} a_{11}a_{23}a_{32} a_{12}a_{21}a_{33} a_{12}a_{23}a_{ 31} a_{13}a_{21}a_{32} a_{13}a_{22}a_{31})x_{1}x_{2}x_{3} ldots }$

Wählen Sie den Koeffizienten von einem der Faktoren ${displaystyle x_{1}}$, von einem anderen Faktor der Koeffizient von ${displaystyle x_{2}}$ und eines dritten Faktors der Koeffizient von ${displaystyle x_{3}}$.

Mit der Ryser-Formel:

${displaystyle Sigma _{0}=pi (A)=(a_{11} a_{12} a_{13})(a_{21} a_{22} a_{23})(a_{31} a_{32} a_{33})}$

${displaystyle Sigma _{1}=pi left({ egin{bmatrix}a_{12}&a_{13}/a_{22}&a_{23}/a_{32}&a_{33}end{bmatrix}}ight) pi left({ egin{bmatrix}a_{11}&a_{13}/a_{21}&a_{23}/a_{31}&a_{33}end{bmatrix}}ight) pi left({ egin{bmatrix}a_{ 11}&a_{12}/a_{21}&a_{22}/a_{31}&a_{32}end{bmatrix}}ight)=(a_{12} a_{13})(a_{22} a_{23 })(a_{32} a_{33}) ldots }$

${displaystyle Sigma _{2}=pi left({ egin{bmatrix}a_{11}/a_{21}/a_{31}end{bmatrix}}ight) pi left({ egin{bmatrix}a_{12}/ a_{22}/a_{32}end{bmatrix}}ight) pi left({ egin{bmatrix}a_{13}/a_{23}/a_{33}end{bmatrix}}ight)=a_{11} a_{21}a_{31} a_{12}a_{22}a_{32} a_{13}a_{23}a_{33}}$

${displaystyle Sigma_{0}}$ besteht aus 27 Begriffen, von denen 6 die unbefristete. Die verbleibenden 21 Begriffe heben sich gegen 21 der 24 Begriffe von auf ${Displaystil Sigma _{1}}$. Die restlichen 3 Begriffe von ${Displaystil Sigma _{1}}$ fallen weg von den 3 Begriffen von ${displaystyle Sigma_{2}}$.

Verwenden der Glynn-Formel:

Es gibt 4 Reihen: ${Anzeigestil (1,1,1)}$, ${displaystyle(1,1,-1)}$, ${Anzeigestil (1,-1,1)}$ und ${Anzeigestil (1,-1,-1)}$.

${displaystyle 4cdot {m {per}}(A)=}$

${displaystyle ( 1)(a_{11} a_{21} a_{31})(a_{12} a_{22} a_{32})(a_{13} a_{23} a_{33}) }$

${displaystyle (-1)(a_{11} a_{21}-a_{31})(a_{12} a_{22}-a_{32})(a_{13} a_{23}-a_{33} ) }$

${displaystyle (-1)(a_{11}-a_{21} a_{31})(a_{12}-a_{22} a_{32})(a_{13}-a_{23} a_{33} ) }$

${displaystyle ( 1)(a_{11}-a_{21}-a_{31})(a_{12}-a_{22}-a_{32})(a_{13}-a_{23}-a_{ 33})}$

Entwicklung zur ersten Spalte.

${displaystyle {m {per}}(A)=a_{11}{m {per}}left({ egin{bmatrix}a_{22}&a_{23}/a_{32}&a_{33}end{bmatrix} }ight) a_{21}{m {per}}left({ egin{bmatrix}a_{12}&a_{13}/a_{32}&a_{33}end{bmatrix}}ight) a_{31}{m {per}}links({ egin{bmatrix}a_{12}&a_{13}/a_{22}&a_{23}Ende{bmatrix}}ight)=}$

${displaystyle =a_{11}(a_{22}a_{33} a_{23}a_{32}) a_{21}(a_{12}a_{33} a_{13}a_{32}) a_{31 }(a_{12}a_{23} a_{13}a_{22})}$

Anwendung

Es gibt kein einfaches von der bleibenden als von der Determinante Geometer Interpretation. Die Anwendungen liegen im Bereich der Kombinatorik. Ein Beispiel ist die Berechnung von Links in einem zweigeteilte Zählung.

Eigenschaften

Unten ist ${Anzeigestil V}$ die Beteiligten Vektorraum über dem Körper (Ned) / Feld (Be) ${Anzeigestil K}$, und wird der ${Anzeigestil n imes n}$-Matrix ${Anzeigestil A}$ notiert als eine Reihe von Spaltenvektoren: ${displaystyle A=(a_{1},a_{2},ldots,a_{n})}$.

Multilinear

Die Dauerwelle ist a multilineare Funktion der Spalten. D.h. das für alle ${displaystyle a_{1},ldots ,a_{n},bin V,lambda in K}$ gilt:

${displaystyle {m {per}}(a_{1},ldots ,a_{i-1},a_{i} b,a_{i 1},ldots ,a_{n})={m {per}}( a_{1},ldots ,a_{i-1},a_{i},a_{i 1},ldots ,a_{n}) {m {per}}(a_{1},ldots ,a_{i- 1},b,a_{i 1},ldots ,a_{n})}$

und

${displaystyle {m {per}}(a_{1},ldots ,a_{i-1},lambda a_{i},a_{i 1},ldots ,a_{n})=lambda cdot {m {per} }(a_{1},ldots ,a_{i-1},a_{i},a_{i 1},ldots ,a_{n})}$

symmetrisch

Die Dauerwelle ist a symmetrische Funktion der Spalten, d. h. der Wert ändert sich nicht, wenn zwei Spalten vertauscht werden. Für alle ${displaystyle a_{1},ldots ,a_{n},bin V}$ und alles ${displaystyle i,jin {1,ldots,n},ieq j}$ daher gilt:

${displaystyle {m {per}}(a_{1},ldots ,a_{i-1},a_{i},a_{i 1},ldots ,a_{j-1},a_{j},a_{ j 1},ldots ,a_{n})={m {per}}(a_{1},ldots ,a_{i-1},a_{j},a_{i 1},ldots ,a_{j- 1},a_{i},a_{j 1},ldots ,a_{n})}$

Standardisiert

Die Dauerwelle ist standardisiert, d.h. die Dauerwelle des Einheitenmatrix${displaystyle I_{n}}$ hat den Wert 1.

${displaystyle {m {per}}(I_{n})=1}$

transponiert

Die Dauerwelle des transponierte Matrix${Displaystil A^{ auf }}$ ist gleich der bleibenden von ${Anzeigestil A}$ selbst:

${displaystyle {m {pro}}(A^{ on})={m {pro}}(A)}$

Matrixprodukt

Anders als für die Determinante gilt für die bleibende im Allgemeinen nicht, dass die bleibende der Matrixprodukt${Anzeigestil AB}$ ist gleich dem Produkt der Dauerwellen von ${Anzeigestil A}$ und ${Anzeigestil B}$, wie aus dem Folgenden ersichtlich ist Gegenbeispiel:

${displaystyle {m {per}}left({ egin{bmatrix}1&1/1&1end{bmatrix}}{ egin{bmatrix}1&1/1&1end{bmatrix}}ight)={m {per}}left({ egin{bmatrix} 2&2/2&2Ende{bmatrix}}acht)=8,}$

aber

${displaystyle {m {per}}left({ egin{bmatrix}1&1/1&1end{bmatrix}}ight){m {per}}left({ egin{bmatrix}1&1/1&1end{bmatrix}}ight)=4.}$

Nicht-quadratische Matrizen

Die bleibende kann auch für nicht-quadratische Matrizen definiert werden. Für ein ${displaystyle mimen n}$-Matrix ${Anzeigestil A=(a_{ij})}$, mit ${displaystyle mleq n}$, also mit nicht mehr Zeilen als Spalten, ist:

${displaystyle {m {pro}}(A)=Summe _{sigma }a_{1,sigma (1)}a_{2,sigma (2)}ldots a_{m,sigma (m)}}$,

in dem die Summe läuft über alles Variationen${Displaystil-Sigma}$ von ich Zahlen von den Zahlen 1 bis nein.

Die Formel von Ryser kann auch verallgemeinert werden.

${displaystyle {m {per}}(A)=sum _{k=0}^{m-1}(-1)^{k}{ binom {n-m k}{k}}Sigma _{n-m k}}$,

in welchem ${displaystyle Sigma_{k}}$ wieder steht die summe über allen möglichen produkten ${displaystyle pi(A_{k})}$ der steigenden Summen von ${Displaystil A_{k}}$, eine Matrix, die besteht aus ${Anzeigestil A}$ verursacht durch ${displaystyle k}$ Spalten löschen.

Verallgemeinerung

Wie die Determinante ist die bleibende ein Sonderfall der immanent, was für einen Komplex Charakter${displaystyle chi :S_{n}ightarrow mathbb {C}}$ von dem Symmetriegruppe ist definiert als:

${displaystyle {m {imm}}_{chi}(A)=Summe _{sigma in S_{n}}chi (sigma)prod _{i=1}^{n}a_{i,sigma (i)} }$.

Die bleibende wird durch die Wahl des trivialen Charakters erhalten, die Determinante durch die Wahl der Funktion keuze obtained signum.

Beide Möglichkeiten sind insofern besonders, als sie die einzigen endlich-dimensionalen Gruppenvertretungen der Symmetriegruppe.

Literatur

• Glynn, David G. (2010), Die Permanente einer quadratischen Matrix, Europäische Zeitschrift für Kombinatorik 31 (7): 1887–1891, doi:10.1016/j.ejc.2010.01.010
• Brualdi, Richard A.; Ryser, Herbert J. (1991), Kombinatorische Matrixtheorie, Encyclopedia of Mathematics and its Applications 39. Cambridge University Press, Cambridge England New York. ISBN 0521322650
• van Lint, J. H.; Wilson, R. M. (2001), Ein Kurs in Kombinatorik, Cambridge University Press, ISBN 0521422604
• Minc, Henryk (1978). Festangestellte, Encyclopedia of Mathematics and its Applications 6. Mit einem Vorwort von Marvin Marcus. Reading, MA: Addison-Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005.
• Muir, Thomas; Wilhelm H. Metzler. (1960) [1882], Eine Abhandlung über die Theorie der Determinanten, New York: Dover. OCLC 535903.
• Ryser, Herbert John (1963), Kombinatorische Mathematik, The Carus Mathematical Monographien #14, The Mathematical Association of America

Verweise

Externe Links

• [1] - Weisstein, Eric W. "Dauerhaft." Von MathWorld – Eine Web-Ressource von Wolfram.
• Störungen erneut aufgegriffen – Anwendung von Dauerwellen in einem kombinatorischen Problem