# 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. 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\}.$ 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
    ${\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)$.

## 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.