Permanent (wiskunde)

In de lineaire algebra, een deelgebied van de wiskunde, is de permanent van een vierkante matrix $A$, net als de determinant, een functie van de elementen van $A$ die op overeenkomstige wijze berekend wordt, zij het dat de summanden in de permanent geen voorteken krijgen, zoals bij de determinant.

De term 'permanent' is afgeleid van de term 'fonctions symétriques permanentes', bedacht door Cauchy in 1812 voor een verwant begrip.. In de huidige betekenis werd de term in 1882 gebruikt door de Schotse wiskundige Sir Thomas Muir.

Definitie

De permanent $\mathrm {per} (A)$ van de $n\times n$-matrix $A=(a_{rk})$ is gedefinieerd door:

$\mathrm {per} (A)=\sum _{\sigma }\prod _{r=1}^{n}a_{r,\sigma (r)}=\sum _{\sigma }a_{1,\sigma (1)}a_{2,\sigma (2)}\ldots a_{n,\sigma (n)}$,

waarin de som loopt over alle permutaties $\sigma$ van de getallen 1 t/m $n$.

Berekening

Het berekenen van de permanent van een matrix vergt nogal wat rekenwerk. Er zin enkele formules die het rekenwerk vereenvoudigen.

Formule van Spies

De Nederlandse wiskundige Jaap Spies geeft in een recent verschenen artikel in het Nieuw Archief voor Wiskunde een formule die reeds eerder in 2006 zijdelings door hem vermeld werd in een eerder artikel in het NAW.

Spies merkt op dat de permanent de coëfficiënt is van $x_{1}x_{2}\ldots x_{n}$ in de veelterm

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

$=\prod _{r=1}^{n}(a_{r1}x_{1}+a_{r2}x_{2}+\ldots +a_{rn}x_{n})$

Definieer

$Q(x_{1},x_{2},\ldots ,x_{n})=(\prod _{i=1}^{n}x_{i})\cdot P(x_{1},x_{2},\ldots ,x_{n})$

en bereken de som over alle mogelijke $x_{i}=\pm 1$:

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

Dan draagt alleen de term

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

in $P(x_{1},x_{2},\ldots ,x_{n})$ altijd bij aan deze som, omdat $x_{i}^{2}=1$ voor $i=1,2,\ldots ,n$.

Een term waarin de factor $x_{k}$ ontbreekt in $P(x_{1},\ldots ,x_{n})$ telt één keer als $t$ en één keer als $-t$.

Er zijn $2^{n}$ mogelijkheden met $x_{i}=\pm 1$ dus de permanent van $A$ is

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

Om redenen van symmetrie kan de formule vereenvoudigd worden door een $x_{k}$ vast te kiezen, bijvoorbeeld $x_{1}=1$. Er zijn dan $2^{n-1}$ mogelijkheden. De formule wordt dan:

$\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}\sum _{j=1}^{n}a_{ij}x_{j}$

Vergelijk deze formule met de formule van Glynn hieronder.

Formule van Ryser

De berekening van de permanent met de formule uit de definitie is nogal bewerkelijk en verlangt $n!\cdot n$ rekenkundige operaties. De Amerikaanse wiskundige H. J. Ryser publiceerde in 1963 een snellere formule die het tot nu toe snelste algoritme is voor de exacte berekening van de permanent. De formule van Ryser is:

${\rm {per}}(A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}$,

waarin $\Sigma _{k}$ de som is over alle matrices $A_{k}$ van de producten $\pi (A_{k})$ van de rijsommen van $A_{k}$, een matrix die uit $A$ ontstaat door $k$ kolommen te schrappen.

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

waarin

$\pi (A_{k})=\prod _{r=1}^{n}\left(a_{r,i_{1}}+\ldots +a_{r,i_{n-k}}\right)$

Uitgeschreven in de elementen van $A$ luidt de formule:

${\rm {per}}(A)=(-1)^{n}\sum _{S\subset \{1,\ldots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}$

Het aantal rekenkundige operaties benodigd met de formule van Ryser is van de orde $2^{n}n^{2}$.

Formule van Glynn

Een andere formule is van de Australische wiskundige David G. Glynn, gepubliceerd in 2010, en rekentechnisch net zo snel als de formule van Ryser. De formule van Glynn luidt, mits de karakteristiek van het lichaam ongelijk is aan 2:

${\rm {per}}(A)={\frac {1}{2^{n-1}}}\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}.$

Daarin loopt de eerste som over alle $2^{n-1}$ rijtjes $\delta =(1,\delta _{2},\ldots ,\delta _{n})$ met $\delta _{i}=\pm 1,i=2,\ldots ,n$.

Ontwikkeling naar rij of kolom

Net als de determinant kan de permanent berekend worden door een ontwikkeling naar een rij of een kolom. De ontwikkeling naar de $k$-de kolom is:

${\rm {per}}(A)=\sum _{r=1}^{n}a_{rk}{\rm {per}}(A_{[rk]}),$

waarin $A_{[rk]}$ de matrix is die verkregen wordt door uit $A$ de $k$-de kolom en de $r$-de rij te schrappen.

De ontwikkeling naar een rij is op overeenkomstige wijze gedefinieerd.

Voorbeelden

In twee dimensies

${\rm {per}}(A)=a_{11}a_{22}+a_{12}a_{21}$

Als coëfficiënt van $x_{1}x_{2}$ in

$(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}$

Met de formule van Ryser:

$\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}$

$\Sigma _{1}=\pi \left({\begin{bmatrix}a_{11}\\a_{21}\end{bmatrix}}\right)+\pi \left({\begin{bmatrix}a_{12}\\a_{22}\end{bmatrix}}\right)=a_{11}a_{21}+a_{12}a_{22}$

${\rm {per}}(A)=\Sigma _{0}-\Sigma _{1}=a_{11}a_{22}+a_{12}a_{21}$

Met de formule van Glynn.

Er zijn 2 rijtjes: $(1,1)$ en $(1,-1)$

${\rm {per}}(A)={\tfrac {1}{2}}\left(1\cdot 1(a_{11}+a_{21})(a_{12}+a_{22})+1\cdot (-1)(a_{11}-a_{21})(a_{12}-a_{22})\right)=$

$={\tfrac {1}{2}}\left((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})\right)=a_{11}a_{22}+a_{12}a_{21}$

In drie dimensies

${\rm {per}}(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 coëfficiënt van $x_{1}x_{2}x_{3}$ in

$(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})=$

$\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$

Kies namelijk steeds uit een van de factoren de coëfficiënt van $x_{1}$, uit een andere factor de coëfficiënt van $x_{2}$ en van een derde factor de coëfficiënt van $x_{3}$.

Met de formule van Ryser:

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

$\Sigma _{1}=\pi \left({\begin{bmatrix}a_{12}&a_{13}\\a_{22}&a_{23}\\a_{32}&a_{33}\end{bmatrix}}\right)+\pi \left({\begin{bmatrix}a_{11}&a_{13}\\a_{21}&a_{23}\\a_{31}&a_{33}\end{bmatrix}}\right)+\pi \left({\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\\a_{31}&a_{32}\end{bmatrix}}\right)=(a_{12}+a_{13})(a_{22}+a_{23})(a_{32}+a_{33})+\ldots$

$\Sigma _{2}=\pi \left({\begin{bmatrix}a_{11}\\a_{21}\\a_{31}\end{bmatrix}}\right)+\pi \left({\begin{bmatrix}a_{12}\\a_{22}\\a_{32}\end{bmatrix}}\right)+\pi \left({\begin{bmatrix}a_{13}\\a_{23}\\a_{33}\end{bmatrix}}\right)=a_{11}a_{21}a_{31}+a_{12}a_{22}a_{32}+a_{13}a_{23}a_{33}$

$\Sigma _{0}$ bestaat uit 27 termen waarvan 6 de permanent vormen. De resterende 21 termen vallen weg tegen 21 van de 24 termen van $\Sigma _{1}$. De overblijvende 3 termen van $\Sigma _{1}$ vallen weg tegen de 3 termen van $\Sigma _{2}$.

Met de formule van Glynn:

Er zijn 4 rijtjes: $(1,1,1)$, $(1,1,-1)$, $(1,-1,1)$ en $(1,-1,-1)$.

$4\cdot {\rm {per}}(A)=$

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

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

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

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

Ontwikkeling naar de eerste kolom.

${\rm {per}}(A)=a_{11}{\rm {per}}\left({\begin{bmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{bmatrix}}\right)+a_{21}{\rm {per}}\left({\begin{bmatrix}a_{12}&a_{13}\\a_{32}&a_{33}\end{bmatrix}}\right)+a_{31}{\rm {per}}\left({\begin{bmatrix}a_{12}&a_{13}\\a_{22}&a_{23}\end{bmatrix}}\right)=$

$=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})$

Toepassing

Van de permanent bestaat niet zoals van de determinant een eenvoudige meetkundige interpretatie. De toepassingen liggen op het gebied van de combinatoriek. Een voorbeeld is de berekening van koppelingen in een bipartiete graaf.

Eigenschappen

In het onderstaande is $V$ de betrokken vectorruimte over het lichaam (Ned) / veld (Be) $K$, en wordt de $n\times n$-matrix $A$ genoteerd als een rij van kolomvectoren: $A=(a_{1},a_{2},\ldots ,a_{n})$.

Multilineair

De permanent is een multilineaire functie van de kolommen. D.w.z. dat voor alle $a_{1},\ldots ,a_{n},b\in V,\lambda \in K$ geldt:

${\rm {per}}(a_{1},\ldots ,a_{i-1},a_{i}+b,a_{i+1},\ldots ,a_{n})={\rm {per}}(a_{1},\ldots ,a_{i-1},a_{i},a_{i+1},\ldots ,a_{n})+{\rm {per}}(a_{1},\ldots ,a_{i-1},b,a_{i+1},\ldots ,a_{n})$

en

${\rm {per}}(a_{1},\ldots ,a_{i-1},\lambda a_{i},a_{i+1},\ldots ,a_{n})=\lambda \cdot {\rm {per}}(a_{1},\ldots ,a_{i-1},a_{i},a_{i+1},\ldots ,a_{n})$

Symmetrisch

De permanent is een symmetrische functie van de kolommen, d.w.z. dat de waarde niet verandert bij verwisseling van twee kolommen. Voor alle $a_{1},\ldots ,a_{n},b\in V$ en alle $i,j\in \{1,\ldots ,n\},i\neq j$ geldt dus:

${\rm {per}}(a_{1},\ldots ,a_{i-1},a_{i},a_{i+1},\ldots ,a_{j-1},a_{j},a_{j+1},\ldots ,a_{n})={\rm {per}}(a_{1},\ldots ,a_{i-1},a_{j},a_{i+1},\ldots ,a_{j-1},a_{i},a_{j+1},\ldots ,a_{n})$

Genormeerd

De permanent is genormeerd, d.w.z. dat de permanent van de eenheidsmatrix $I_{n}$ de waarde 1 heeft.

${\rm {per}}(I_{n})=1$

Getransponeerde

De permanent van de getransponeerde matrix $A^{\top }$ is gelijk aan de permanent van $A$ zelf:

${\rm {per}}(A^{\top })={\rm {per}}(A)$

Matrixproduct

Anders dan voor de determinant geldt voor de permanent niet algemeen dat de permanent van het matrixproduct $AB$ gelijk is aan het product van de permanenten van $A$ en $B$, zoals te zien is aan het volgende tegenvoorbeeld:

${\rm {per}}\left({\begin{bmatrix}1&1\\1&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&1\end{bmatrix}}\right)={\rm {per}}\left({\begin{bmatrix}2&2\\2&2\end{bmatrix}}\right)=8,$

maar

${\rm {per}}\left({\begin{bmatrix}1&1\\1&1\end{bmatrix}}\right){\rm {per}}\left({\begin{bmatrix}1&1\\1&1\end{bmatrix}}\right)=4.$

Niet-vierkante matrices

De permanent kan ook gedefinieerd worden voor niet-vierkante matrices. Voor een $m\times n$-matrix $A=(a_{ij})$, met $m\leq n$, dus met niet meer rijen dan kolommen, is:

${\rm {per}}(A)=\sum _{\sigma }a_{1,\sigma (1)}a_{2,\sigma (2)}\ldots a_{m,\sigma (m)}$,

waarin de som loopt over alle variaties $\sigma$ van m getallen uit de getallen 1 t/m n.

De formule van Ryser kan ook gegeneraliseerd worden.

${\rm {per}}(A)=\sum _{k=0}^{m-1}(-1)^{k}{\tbinom {n-m+k}{k}}\Sigma _{n-m+k}$,

waarin $\Sigma _{k}$ weer de som is over alle mogelijke producten $\pi (A_{k})$ van de rijsommen van $A_{k}$, een matrix die uit $A$ ontstaat door $k$ kolommen te schrappen.

Generalisatie

Evenals de determinant is de permanent een speciaal geval van de immanent, die voor een complex karakter $\chi :S_{n}\rightarrow \mathbb {C}$ uit de symmetriegroep gedefinieerd is als:

${\rm {imm}}_{\chi }(A)=\sum _{\sigma \in S_{n}}\chi (\sigma )\prod _{i=1}^{n}a_{i,\sigma (i)}$.

De permanent verkrijgt men door de keuze van het triviale karakter, de determinant door de keuze van de functie signum.

Deze beide mogelijkheden zijn in zoverre speciaal, dat ze de enige eindigdimensionale groepsrepresentaties van de symmetriegroep zijn.

Literatuur

• Glynn, David G. (2010), The permanent of a square matrix, European Journal of Combinatorics 31 (7): 1887–1891, doi:10.1016/j.ejc.2010.01.010
• Brualdi, Richard A.; Ryser, Herbert J. (1991), Combinatorial Matrix Theory, Encyclopedia of Mathematics and its Applications 39. Cambridge University Press, Camebridge England New York. ISBN 0521322650
• van Lint, J.H.; Wilson, R.M. (2001), A Course in Combinatorics, Cambridge University Press, ISBN 0521422604
• Minc, Henryk (1978). Permanents, Encyclopedia of Mathematics and its Applications 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005.
• Muir, Thomas; William H. Metzler. (1960) [1882], A Treatise on the Theory of Determinants, New York: Dover. OCLC 535903.
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus mathematical monographs #14, The Mathematical Association of America

Externe links

• - Weisstein, Eric W. "Permanent." From MathWorld--A Wolfram Web Resource.
• Derangements revisited – Toepassing van permanenten in een combinatorisch probleem