Permanente (matematica)

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

perm (A) = \sum_{σ \in S_{n}} \prod_{i = 1}^{n} a_{i σ_{i}} = \sum_{σ \in S_{n}} a_{1 σ (1)} a_{2 σ (2)} \dots a_{n σ (n)},

dove $σ_{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:

\det (A) = \sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} a_{i σ_{i}} = \sum_{σ \in S_{n}} sgn (σ) a_{1 σ (1)} a_{2 σ (2)} \dots a_{n σ (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:

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

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

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

dove $I$ e $J$ sono sottoinsiemi di ${1, 2, \dots, 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 = perm (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) perm (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) \neq perm ((\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})) = perm (\begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix}) = 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{matrix} perm (\begin{matrix} 1 & 1 & 1 & 1 \\ 2 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 4 & 0 & 0 & 1 \end{matrix}) & = 1 \cdot perm (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) + 2 \cdot perm (\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) + 3 \cdot perm (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) + 4 \cdot perm (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) = \\ = 1 (1) + 2 (1) + 3 (1) + 4 (1) = 10, \end{matrix}

mentre sviluppando rispetto all'ultima riga si ha

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

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 = (a_{i j}) \begin{matrix} 1 & \leq i \leq m \\ 1 & \leq j \leq n \end{matrix}

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

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

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

perm (A) = \sum_{σ \in P (n, m)} a_{1 σ (j_{1})} a_{2 σ (j_{2})} \dots a_{m σ (j_{m})},

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

C_{m} (X_{n}) = {X_{m}^{1}, X_{m}^{2}, \dots, X_{m}^{(\binom{n}{m})}}, | 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è:

σ = (\begin{matrix} j_{1} & \dots & j_{m} \\ σ (j_{1}) & \dots & σ (j_{m}) \end{matrix}) = σ (j_{1}) \dots σ (j_{m})

nelle due notazioni comuni (1-linea e 2-linea). Usiamo la notazione $S_{m} (X^{k}), k = 1, 2, \dots, (\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

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

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

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

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

\sum_{σ \in P (n, m)} a_{1 σ (j_{1})} a_{2 σ (j_{2})} = a_{11} a_{22} + a_{12} a_{21},

idem per gli altri due sottoinsiemi. Ottenendo lo sviluppo:

perm (\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{matrix}) = (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{matrix} X_{n} & = {1, 2, \dots, n} & | X_{n} | = n \\ X_{k} & = {j_{1}, j_{2}, \dots, j_{k}} \subseteq X_{n} & | X_{k} | = k & k = 1, 2, \dots, m, \end{matrix}

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:

C_{k} (X_{n}) = {X_{k}^{1}, X_{k}^{2}, \dots, X_{k}^{(\binom{n}{k})}} | C_{k} (X_{n}) | = (\binom{n}{k}) k = 1, 2, \dots, 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

A (X_{k}) = (a_{i j}) \begin{matrix} 1 & \leq i \leq m \\ j \in X_{k} \end{matrix}

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

\sum_{j = j_{1}}^{j_{k}} a_{i j}, i = 1, 2, \dots, m,

esplicitando si ottengono $m$ -somme

\begin{matrix} i = 1 & \sum_{j = j_{1}}^{j_{k}} a_{i j} = a_{1 j_{1}} + & \dots & + a_{1 j_{k}} \\ \dots & \dots & \dots & \dots \\ i = m & \sum_{j = j_{1}}^{j_{k}} a_{i j} = a_{m j_{1}} + & \dots & + a_{m j_{k}} . \end{matrix}

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

w (A (X_{k})) = \prod_{i = 1}^{m} \sum_{j = j_{1}}^{j_{k}} a_{i j} = (a_{1 j_{1}} + \dots + a_{1 j_{k}}) \dots (a_{m j_{1}} + \dots + a_{m j_{k}}) .

Fatte queste premesse, allora il permanente si ottiene con la relazione

\begin{matrix} 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 (A (X)) - (\binom{n - m + 1}{n - m}) \sum_{X \in C_{m - 1} (X_{n})}^{} w (A (X)) + \dots + (- 1)^{m - 1} (\binom{n - 1}{n - m}) \sum_{X \in C_{1} (X_{n})}^{} w (A (X)) . \end{matrix}

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, \forall X \in C_{k} (X_{n}), k = 1, 2, \dots, n,

si ottiene

\begin{matrix} 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 (A (X)) - \sum_{X \in C_{n - 1} (X_{n})}^{} w (A (X)) + \dots + (- 1)^{n - 1} \sum_{X \in C_{1} (X_{n})}^{} w (A (X)) . \end{matrix}

Ritornando all'esempio si ha la formula di Ryser:

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 (A (X)) - (\binom{2}{1}) \sum_{X \in C_{1} (X_{n})}^{} w (A (X))

con i seguenti insiemi

\begin{matrix} 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 \\ C_{2} (X_{n}) & = {X_{2}^{1}, X_{2}^{2}, X_{2}^{3}} = {{1, 2}, {1, 3}, {2, 3}} & | C_{2} (X_{n}) | = (\binom{3}{2}) = 3 \\ C_{1} (X_{n}) & = {X_{1}^{1}, X_{1}^{2}, X_{1}^{3}} = {{1}, {2}, {3}} & | C_{1} (X_{n}) | = (\binom{3}{1}) = 3 \end{matrix}

per cui possiamo calcolare le due sommatorie

\begin{matrix} \sum_{X \in C_{2} (X_{n})}^{} w (A (X)) & = w (A (X_{2}^{1})) + w (A (X_{2}^{2})) + w (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 (A (X)) & = w (A (X_{1}^{1})) + w (A (X_{1}^{2})) + w (A (X_{1}^{3})) = a_{11} a_{21} + a_{12} a_{22} + a_{13} a_{23} \end{matrix}

e sostituendoli nella formula di Ryser si ottiene:

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}) - 2 a_{11} a_{21} - 2 a_{12} a_{22} - 2 a_{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}, \dots, S_{m}, S_{i} \subseteq X_{n} i = 1, 2, \dots, 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 $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.

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 (WC · ACNP), OCLC 3980645, Zbl 0401.15005.

Voci correlate

Collegamenti esterni

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[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