Permanente (matematica)

In matematica, il permanente di una matrice quadrata $A$ di ordine $n$ , di elementi $a_{ij}$ è definito come

\operatorname {perm} (A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i\sigma _{i}}=\sum _{\sigma \in S_{n}}a_{1\sigma (1)}a_{2\sigma (2)}\cdots a_{n\sigma (n)},

dove $\sigma _{i}$ rappresenta una permutazione, ossia un elemento del gruppo simmetrico $S_{n}$ , quindi ci sono n! addendi, ciascuno dei quali è un $n$ -prodotto di elementi della matrice. La definizione ricorda quella molto simile di determinante: ci sono gli stessi addendi, ma con l'unica differenza che nel determinante sono alcuni col segno più e altri col segno meno che dipendono dal segno della permutazione fissata nell' $n$ -prodotto, nel permanente sono tutti col segno più. Infatti si ha:

\operatorname {det} (A)=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )\prod _{i=1}^{n}a_{i\sigma _{i}}=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )\ a_{1\sigma (1)}a_{2\sigma (2)}\cdots a_{n\sigma (n)}.

Di fatto, come quest'ultimo, il permanente è un caso particolare di immanente, una più generale operazione su matrici di ordine $n$ . Al contrario del determinante, il permanente non ha una semplice interpretazione geometrica. Esso è usato principalmente in combinatoria e nello studio dei bosoni.

Proprietà

Considerando il permanente come una funzione i cui argomenti sono $n$ vettori, esso è una applicazione multilineare ed è simmetrica.

Sia $A$ una matrice quadrata di ordine $n$ si ha:

$\operatorname {perm} (A)$ è invariante rispetto a permutazioni arbitrarie di righe o colonne di $A$ ;
moltiplicando una riga o una colonna di $A$ per uno scalare $\lambda$ anche il permanente viene moltiplicato per $\lambda$ ;
$\operatorname {perm} (A)$ è invariante rispetto alla trasposizione, cioè $\operatorname {perm} (A^{T})=\operatorname {perm} (A)$ .

Se $A=(a_{ij})$ e $B=(b_{ij})$ sono matrici quadrate di ordine $n$ , allora

\operatorname {perm} (A+B)=\sum _{I,J}\operatorname {perm} (a_{ij})_{i\in I,j\in J}\operatorname {perm} (b_{ij})_{i\in {\bar {I}},j\in {\bar {J}}},

dove $I$ e $J$ sono sottoinsiemi di $\{1,2,\ldots ,n\}$ che hanno la stessa cardinalità e ${\bar {I}}$ e ${\bar {J}}$ sono i rispettivi complementari in tale insieme.

D'altra parte la proprietà moltiplicativa del determinante non è soddisfatta dal permanente. Ad esempio:

4=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.

Per il calcolo del permanente è valida una formula simile allo sviluppo di Laplace del determinante, in cui tutti i segni dei minori sono positivi. Per esempio, sviluppando lungo la prima colonna la seguente matrice si ha

{\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)&=1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)=\\&=1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}

mentre sviluppando rispetto all'ultima riga si ha

{\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)&=4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)=\\&=4(1)+0+0+1(6)=10.\end{aligned}}

Matrici rettangolari

La funzione permanente si generalizza per il calcolo di matrici non quadrate. In certi testi, molti autori danno la definizione generale e considerano come caso particolare le matrici quadrate.^[1] Sia data una matrice $m\times n,$ in notazione:

A=\left(a_{ij}\right){\underset {\begin{aligned}1&\leq i\leq m\\1&\leq j\leq n\end{aligned}}{}}

con $m\leq n,$ a cui possiamo associare due insiemi:

{\begin{aligned}X_{n}&=\{1,2,\ldots ,n\}&&|X_{n}|=n\\X_{m}&=\{j_{1},j_{2},\ldots ,j_{m}\}\subseteq X_{n}&&|X_{m}|=m\end{aligned}}

denominati l'insieme degli indici colonna della matrice $A$ e i sottoinsiemi degli indici colonna di $A.$ Fatta questa premessa si definisce il permanente di una matrice rettangolare la relazione

\operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (j_{1})}a_{2\sigma (j_{2})}\ldots a_{m\sigma (j_{m})},

dove $\operatorname {P} (n,m)$ è l'insieme di tutte le $m$ -permutazioni dell' $n$ -insieme $\{1,2,\ldots ,n\}.$ ^[2] I sottoinsiemi $X_{m}$ di $X_{n}$ sono pari alle combinazioni degli elementi presi a $m$ a $m,$ cioè la famiglia di sottoinsiemi:

\operatorname {C} _{m}(X_{n})=\{X_{m}^{1},X_{m}^{2},\ldots ,X_{m}^{\binom {n}{m}}\},\quad |\operatorname {C} _{m}(X_{n})|={\binom {n}{m}}

fissato un sottoinsieme $X_{m}^{j}$ , occorre considerare gli elementi del gruppo simmetrico $S_{m}$ ottenendo $m!$ addendi, cioè:

\sigma ={\begin{pmatrix}j_{1}&\ldots &j_{m}\\\sigma (j_{1})&\ldots &\sigma (j_{m})\end{pmatrix}}=\sigma (j_{1})\ldots \sigma (j_{m})

nelle due notazioni comuni (1-linea e 2-linea). Usiamo la notazione $S_{m}(X^{k}),\quad k=1,2,\ldots ,{\binom {n}{m}}$ per indicare le permutazioni di un particolare sottoinsieme di $X_{n}$ . Quindi ci sono esattamente $(n)_{m}={\binom {n}{m}}m!$ addendi nello sviluppo del permanente di una matrice rettangolare. Quindi

\operatorname {P} (n,m)=\bigcup _{k=1}^{\binom {n}{m}}S_{m}(X^{k}).

Ad esempio se consideriamo una generica matrice $2\times 3$ si ha:

{\begin{aligned}X_{n}&=\{1,2,3\}&&|X_{n}|=3\\X_{m}&=\{j_{1},j_{2}\}\subseteq X_{n}&&|X_{m}|=2\\\operatorname {C} _{m}(X_{n})&=\{X_{m}^{1},X_{m}^{2},X_{m}^{3}\}=\{\{1,2\},\{1,3\},\{2,3\}\}&&|\operatorname {C} _{m}(X_{n})|={\binom {3}{2}}=3\\\operatorname {P} (n,m)&=\{12,21;13,31;23,32\}&&|\operatorname {P} (n,m)|=(3)_{2}=6\end{aligned}}

fissato $X_{m}^{1}=\{1,2\}\subseteq X_{n}$ occorre considerare le due permutazioni $\sigma _{1}=(1)(2)=12,\ \sigma _{2}=(21)=21$ degli indici colonna, ottenendo:

\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (j_{1})}a_{2\sigma (j_{2})}=a_{11}a_{22}+a_{12}a_{21},

idem per gli altri due sottoinsiemi. Ottenendo lo sviluppo:

\operatorname {perm} \left({\begin{matrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{matrix}}\right)=(a_{11}a_{22}+a_{12}a_{21})+(a_{12}a_{23}+a_{13}a_{22})+(a_{11}a_{23}+a_{13}a_{21}),

con $(3)_{2}={\binom {3}{2}}2!=6$ addendi della sommatoria.

Formula di Ryser (1963)

Il risultato del matematico statunitense Ryser per il permanente è il calcolo più ottimizzato per matrici generiche. Sia $A$ una matrice $m\times n$ con $m\leq n,$ riprendiamo i due insiemi visti all'inizio con il secondo che dipende da un indice $k$ :

{\begin{aligned}X_{n}&=\{1,2,\ldots ,n\}&&|X_{n}|=n&&\\X_{k}&=\{j_{1},j_{2},\ldots ,j_{k}\}\subseteq X_{n}&&|X_{k}|=k&&k=1,2,\ldots ,m,\end{aligned}}

cioè l'insieme degli indici colonna della matrice $A$ e gli $m$ -sottoinsiemi degli indici colonna. Vediamo di soffermarci sul significato di questi sottinsiemi, definendo la famiglia di sottinsiemi simile a quanto visto prima:

\operatorname {C} _{k}(X_{n})=\{X_{k}^{1},X_{k}^{2},\ldots ,X_{k}^{\binom {n}{k}}\}\quad |\operatorname {C} _{k}(X_{n})|={\binom {n}{k}}\quad k=1,2,\ldots ,m

quindi al variare di $k$ otteniamo $m$ -famiglie di sottoinsiemi. Vogliamo far notare, rispetto alla definizione data all'inizio, che non si hanno permutazioni degli indici fissato un $k$ -sottoinsieme.

Definiamo la sottomatrice rettangolare i cui elementi hanno l'indice riga $1\leq i\leq m$ e l'indice colonna $j\in X_{k}$ con

\operatorname {A} (X_{k})=(a_{ij}){\underset {\begin{aligned}1&\leq i\leq m\\&j\in X_{k}\\\end{aligned}}{}}

e facciamo le seguenti operazioni su tale sottomatrice: consideriamo le $m$ -somme definite dalla seguente relazione:

\sum _{j=j_{1}}^{j_{k}}\ a_{ij},\quad i=1,2,\ldots ,m,

esplicitando si ottengono $m$ -somme

{\begin{aligned}i=1&&\sum _{j=j_{1}}^{j_{k}}\ a_{ij}=a_{1j_{1}}+&&\ldots &&+a_{1j_{k}}\\\ldots &&\ldots &&\ldots &&\ldots \\i=m&&\sum _{j=j_{1}}^{j_{k}}\ a_{ij}=a_{mj_{1}}+&&\ldots &&+a_{mj_{k}}.\end{aligned}}

Infine facciamo il loro prodotto definendo il seguente numero intero (simbolo $w$ -weight) cioè assegniamo un peso alla sottomatrice:

w(\operatorname {A} (X_{k}))=\prod _{i=1}^{m}\sum _{j=j_{1}}^{j_{k}}a_{ij}=\left(a_{1j_{1}}+\ldots +a_{1j_{k}}\right)\cdots \left(a_{mj_{1}}+\ldots +a_{mj_{k}}\right).

Fatte queste premesse, allora il permanente si ottiene con la relazione^[3]

{\begin{aligned}\operatorname {perm} (A)&=\sum _{X\subseteq X_{n}}^{}\ (-1)^{m-|X|}\ {\binom {n-|X|}{n-m}}\ w(A(X))=\\&=\sum _{k=1}^{m}(-1)^{k-1}\ {\binom {n-m+k-1}{n-m}}\ \sum _{X\in C_{m-k+1}(X_{n})}^{}\ w(A(X))=\\&=\sum _{X\in C_{m}(X_{n})}^{}w(\operatorname {A} (X))-{\binom {n-m+1}{n-m}}\ \sum _{X\in C_{m-1}(X_{n})}^{}w(\operatorname {A} (X))+\cdots +(-1)^{m-1}{\binom {n-1}{n-m}}\ \sum _{X\in C_{1}(X_{n})}^{}w(\operatorname {A} (X)).\end{aligned}}

In particolare per $m=n,$ si ottiene la formuna di Ryser per una matrice quadrata $n\times n$ essendo

{\binom {n-|X|}{n-m}}={\binom {n-|X|}{0}}=1,\quad \forall X\in \operatorname {C} _{k}(X_{n}),\quad k=1,2,\ldots ,n,

si ottiene

{\begin{aligned}\operatorname {perm} (A)&=\sum _{X\subseteq X_{n}}^{}\ (-1)^{n-|X|}\ w(A(X))=\\&=\sum _{k=1}^{n}(-1)^{k-1}\ \sum _{X\in C_{n-k+1}(X_{n})}^{}\ w(A(X))=\\&=\sum _{X\in C_{n}(X_{n})}^{}w(\operatorname {A} (X))-\sum _{X\in C_{n-1}(X_{n})}^{}w(\operatorname {A} (X))+\cdots +(-1)^{n-1}\sum _{X\in C_{1}(X_{n})}^{}w(\operatorname {A} (X)).\end{aligned}}

Ritornando all'esempio si ha la formula di Ryser:

\operatorname {perm} (A)=\sum _{X\subseteq X_{n}}^{}\ (-1)^{m-|X|}\ {\binom {n-|X|}{n-m}}\ w(A(X))={\binom {1}{1}}\ \sum _{X\in C_{2}(X_{n})}^{}w(\operatorname {A} (X))-{\binom {2}{1}}\ \sum _{X\in C_{1}(X_{n})}^{}w(\operatorname {A} (X))

con i seguenti insiemi

{\begin{aligned}X_{n}&=\{1,2,3\}&&|X_{n}|=3&&\\X_{1}&=\{j_{1}\}\subseteq X_{n}\ X_{2}=\{j_{1},j_{2}\}\subseteq X_{n}&&|X_{1}|=1,|X_{2}|=2=m&&k=1,2\\\operatorname {C} _{2}(X_{n})&=\{X_{2}^{1},X_{2}^{2},X_{2}^{3}\}=\{\{1,2\},\{1,3\},\{2,3\}\}&&|\operatorname {C} _{2}(X_{n})|={\binom {3}{2}}=3&&\\\operatorname {C} _{1}(X_{n})&=\{X_{1}^{1},X_{1}^{2},X_{1}^{3}\}=\{\{1\},\{2\},\{3\}\}&&|\operatorname {C} _{1}(X_{n})|={\binom {3}{1}}=3&&\end{aligned}}

per cui possiamo calcolare le due sommatorie

{\begin{aligned}\sum _{X\in C_{2}(X_{n})}^{}w(\operatorname {A} (X))&=w(\operatorname {A} (X_{2}^{1}))+w(\operatorname {A} (X_{2}^{2}))+w(\operatorname {A} (X_{2}^{3}))=(a_{11}+a_{12})(a_{21}+a_{22})+(a_{11}+a_{13})(a_{21}+a_{23})+(a_{12}+a_{13})(a_{22}+a_{23})\\\sum _{X\in C_{1}(X_{n})}^{}w(\operatorname {A} (X))&=w(\operatorname {A} (X_{1}^{1}))+w(\operatorname {A} (X_{1}^{2}))+w(\operatorname {A} (X_{1}^{3}))=a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23}\end{aligned}}

e sostituendoli nella formula di Ryser si ottiene:

\operatorname {perm} (A)=(a_{11}+a_{12})(a_{21}+a_{22})+(a_{11}+a_{13})(a_{21}+a_{23})+(a_{12}+a_{13})(a_{22}+a_{23})-2a_{11}a_{21}-2a_{12}a_{22}-2a_{13}a_{23}=a_{11}a_{22}+a_{12}a_{21}+a_{11}a_{23}+a_{13}a_{21}+a_{12}a_{23}+a_{13}a_{22}.

Sistemi di rappresentanti distinti (SDR)

La generalizzazione della definizione di una matrice permanente a matrici non quadrate consente di utilizzare il concetto in modo più naturale in alcune applicazioni. Ad esempio:

Consideriamo $m$ -sottoinsiemi

S_{1},S_{2},\ldots ,S_{m},\quad S_{i}\subseteq X_{n}\quad i=1,2,\ldots ,m,

(non necessariamente distinti) di un $n$ -insieme con $m\leq n.$ La matrice delle incidenze di questa famiglia di sottoinsiemi è una $(0,1)$ -matrice $m\times n.$ Allora il numero SDR di questa famiglia è proprio $\operatorname {perm} (A)$ .^[4]

Applicazioni

In meccanica quantistica, in sistemi a molti bosoni, il permanente può essere utilizzato per determinare uno stato completamente simmetrico che descriva una particolare configurazione del sistema, in modo del tutto analogo al determinante di Slater per i sistemi a molti fermioni.

Note

↑ Esempi sono:
Minc H
Ryser H J
↑ Ryser H J, p. 25
↑ Ryser H J, p. 26
↑ Ryser H J, p. 54

Bibliografia

(EN) Herbert John Ryser, Combinatorial Mathematics, in The Carus Mathematical Monographs #14, MAA, 1963.
(EN) Minc Henryk, Permanents, in Encyclopedia of Mathematics and its Applications, Con una prefazione di Marvin Marcus, vol. 6, Reading, MA, AW, 1978, ISSN 0953-4806, OCLC 3980645, Zbl 0401.15005.

Voci correlate

Collegamenti esterni

(EN) Eric W. Weisstein, Permanent, su MathWorld, Wolfram Research.

[1] Esempi sono:
Minc H
Ryser H J

[2] Ryser H J, p. 25

[Ryser_1963_loc=p._26-3] Ryser H J, p. 26

[4] Ryser H J, p. 54

[1]

[2]

[3]

[4]