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.^[1] 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} .$ ^[2] 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:Template:Ancora

\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^[3]

\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)$ .^[4]

Applicazioni

Template:Vedi anche 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:
Template:Cita
Template:Cita
↑ Template:Cita
↑ Template:Cita
↑ Template:Cita

Bibliografia

Voci correlate

Collegamenti esterni

Template:Collegamenti esterni

Template:Portale

[1] Esempi sono:
Template:Cita
Template:Cita

[2] Template:Cita

[Ryser_1963_loc=p._26-3] Template:Cita

[4] Template:Cita

[1]

[2]

[3]

[4]

Permanente (matematica)

Indice

Proprietà

Matrici rettangolari

Formula di Ryser (1963)

Sistemi di rappresentanti distinti (SDR)

Applicazioni

Note

Bibliografia

Voci correlate

Collegamenti esterni

Menu di navigazione

Permanente (matematica)

Proprietà

Matrici rettangolari

Formula di Ryser (1963)

Sistemi di rappresentanti distinti (SDR)

Applicazioni

Note

Bibliografia

Voci correlate

Collegamenti esterni

Menu di navigazione

Ricerca