Due conseguenze del teorema di Kirchoff

(1)

Due conseguenze del teorema di Kirchoff

F. Pugliese November 18, 2015

Abstract

Come corollari del teorema ”matrice-albero” di Kirchoff, dimostriamo la formula di Cayley e la formula che esprime il numero di alberi generatori tramite lo spettro laplaciano.

0.1 Richiami sul laplaciano di un grafo

Sia G = (E, V ) un grafo (semplice, non orientato) connesso con n vertici ed m lati, e siano F ' R ⁿ , H ' R ^m , rispettivamente, lo spazio delle funzioni V → R e lo spazio delle funzioni E → R. Fissata arbitrariamente un’orientazione dei lati di G, l’operatore d’incidenza orientata D : H → F `e definito tramite la formula

D(h)(v) ^def = X

e∼v

(−1) ^e,v h(e),

per ogni h ∈ H, v ∈ V . Il laplaciano di G `e l’operatore

L ^def = D ◦ D ^∗ ∈ End(F),

dove D ^∗ : F → H `e l’operatore aggiunto di D (rispetto alle strutture euclidee standard di F e di H); com’`e noto (v. [[1]]), vale

L = ∆ − A, (1)

dove A ∈ End(F) `e l’operatore d’adiacenza, definito da A(f )(v) ^def = X

w∼v

f (w), ∀f ∈ F, v ∈ V

e ∆ ∈ End(F) `e definito da

∆(f )(v) ^def = d(v)f (v)

(essendo d(v) il grado di v ∈ V ). Inoltre (v. sempre [[1]]) si ha che:

(2)

1. L `e simmetrico e semidefinito positivo;

2. Ker L = KerD ^∗ = h1i = {funzioni costanti}

Im L = Im D = h1i ^⊥ = {funzioni a somma nulla}

in particolare, L ha rango n − 1.

0.2 Richiami sull’aggiugato di una matrice

Sia A ∈ M n (R) una matrice quadrata reale d’ordine; l’aggiugato (o aggiunto classico) di A `e la matrice

adj(A) = kA ji k ⁿ _i,j=1 ,

con A ij complemento algebrico di a ij in A (cioè, il prodotto di (−1) î+j per il minore di A ottenuto eliminando la i-ma riga e la j-ma colonna). Le principali proprietà dell’aggiugato sono:

a) Valgono le identit`a

adj(A) A = A adj(A) = |A| I; (2)

in particolare, se A `e invertibile vale

adj(A) = |A| A ⁻¹ (3)

b)

adj(AB) = adj(B)adj(A), adj(I) = I (4) c)

adj(A ^T ) = adj(A) ^T (5)

d)

adj(λA) = λ ⁿ⁻¹ adj(A), per ogni λ ∈ R

e) se A ha rango n − 1, allora adj(A) ha rango 1; se A ha rango minore di n − 1, allora adj(A) = 0

f ) Se P `e una proiezione ortogonale (cio`e P ² = P = P ^T ) di rango n − 1, allora

adj(P ) `e la proiezione ortogonale complementare (cio`e quella sulla retta

KerP )

(3)

g) se R `e ortogonale, allora lo `e anche adj(R)

Dimostriamo, di queste proprietà, solo quelle che non compaiono già nell’appendice di [[1]]. La (4) ₁ segue banalmente da (3) quando A è invertibile; nel caso

|A| = 0, basta tenere conto che l’insieme GL(n, R) delle matrici invertibili è denso in M n (R) e che la condizione (4) 1 descrive un sottoinsieme chiuso di M n (R), per cui, se è valida nell’insieme GL(n, R) delle matrici invertibili lo è anche in M n (R) = GL(n, R).

La proprietà d) è un’immediata conseguenza della definizione di aggiugato e della multilinearità dei determinanti.

La propriet`a f) segue facilmente dalle propriet`a b), c), e); infatti, da (4) 1

segue

adj(P ) ² = adj(P ² ) = adj(P )

per cui, se adj(P ) non `e nulla (cio`e, per la e), se P ha rango n − 1), allora essa

`e una proiezione di rango 1; d’altra parte, la (5) implica che dalla simmetria di P segue quella di adj(P ), per cui anche adj(P ) `e una proiezione ortogonale; che poi l’immagine di tale proiezione sia il kernel di P segue banalmente dalla (2) per A = P .

La propriet`a g) segue anch’essa banalmente dalle propriet`a b) e c):

adj(R)adj(R) ^T = adj(R ^T R) = adj(I) = I

0.3 Corollari del teorema di Kirchoff

Ricordiamo l’enunciato del teorema ”matrix-tree” di Kirchoff (per la dimostrazione, v. [2] oppure [3]):

Theorem 1 (Teorema ”Matrix-Tree”) Detto L = ∆ − A il laplaciano del grafo connesso G, vale

adj(L) = kJ, (6)

con J matrice con tutte le entrate uguali a 1 e

k = k(G) = numero degli alberi generatori di G

Mostriamo come da tale teorema seguano facilmente la formula di Cayley sul numero di alberi con insieme di vertici assegnato, e un’altra espressione di k(G) tramite gli autovalori del laplaciano.

Proposition 2 (Formula di Cayley). Il numero di alberi che si possono costru-

ire su n vertici `e n ⁿ⁻²

(4)

Proof. Notiamo che nell’enunciato si parla di tutti gli alberi su un insieme dato v 1 , . . . , v n di vertici, cioè si considerano distinti anche due alberi equivalenti che differiscano solo per una permutazione dei vertici (”labelled trees”): ad esempio, per n = 3 esistono 3 alberi ”etichettati” distinti (cioè i 2-cammini v ₁ − v ₂ − v ₃ , v ₁ − v ₃ − v ₂ , v ₂ − v ₁ − v ₃ ) che però sono ovviamente isomorfi!

Poich`e gli alberi sui vertici v 1 , . . . , v n coincidono con gli alberi generatori del grafo completo K n su questi stessi vertici, per dimostrare la proposizione basta applicare il teorema ”matrix-tree” al grafo K n . Sia L = L(K n ) la matrice lapla- ciana (cio`e la matrice che rappresenta l’operatore L rispetto alla base standard di F K

n

); allora da (1) segue che

L = ∆(K n ) − A(K n ) = (n − 1)I n − (J n − I n )

(7)

= nI n − J n ,

con I n matrice identica e J n = 1 · 1 ^T matrice con tutte le entrate uguali a 1.

Notiamo che (1/n)J `e la (matrice rappresentativa della) proiezione ortogonale sulla retta h1i, in quanto

J ² = nJ, Im J = h1i , J ^T = J;

quindi, da (7) segue che

L ² = n ² I + J ² − 2nJ = n(nI − J) = nL,

cioè (1/n)L è la proiezione ortogonale su Im L = h1i ^⊥ ; ma allora, applicando le proprietà f) e d) dell’aggiugato, si ha che

1 n ⁿ⁻¹ adj(L) = adj( 1 n L)

è la proiezione ortogonale su KerL = h1i, cioè coincide con (1/n)J, cioè adj(L) = n ⁿ⁻² J,

da cui, tenendo conto del teorema di Kirchoff, segue l’asserto.

Come secondo corollario del teorema ”matrix-tree”, dimostriamo la seguente formula alternativa per il numero degli alberi generatori.

Proposition 3 Sia λ 1 = 0 < λ 2 ≤ · · · ≤ λ n lo spettro laplaciano di un grafo connesso G; allora il numero degli alberi generatori di G `e

k(G) = λ 2 · · · λ n

n

(5)

Proof. Osserviamo che h1i = KerL e h1i ^⊥ = Im L sono spazi invarianti per L;

di conseguenza, detta (w 1 , . . . , w n−1 ) una base ortonormale di h1i ^⊥ , la matrice di L nella base ortonormale (w 1 , . . . , w n−1 , 1/ √

n) `e della forma diagonale

L = e

° °

° λ 2

. ..

λ n

0 ° °

° °

° ,

sicch`e, applicando la definizione di aggiugato,

adj(e L) =

° °

° 0

. ..

0 λ 2 · · · λ n

° °

°

D’altra parte, poich`e L ed e L rappresentano lo stesso operatore lineare L in due basi ortonormali diverse, esse sono legate da una relazione del tipo

L = R ^T LR, e

con R matrice ortogonale; quindi, applicando le propriet`a b), c) e g) dell’aggiugato si ottiene

adj(L) = adj(R)adj(e L)adj(R) ^T = adj(R)adj(e L)adj(R) ⁻¹

Dunque, adj(L) e adj(e L) sono simili e quindi, in particolare, hanno la stessa traccia:

T r(adj(L)) = T r(adj(e L)) = λ ₂ · · · λ _n ; (8) ma, per la (6), vale anche

T r(adj(L)) = k(G)T r(J) = nk(G) (9)

e dal confronto di (8) e (9) segue l’asserto.

References

[1] F. Pugliese: ”Algebra lineare e teoria dei grafi”

[2] N. Biggs: ”Algebraic Graph Theory”, Chap. 6

[3] Godsil, Royle: ”Algebraic Graph Theory”, chap. 13, sec. 2

Due conseguenze del teorema di Kirchoff

Due conseguenze del teorema di Kirchoff

F. Pugliese November 18, 2015

Abstract

Come corollari del teorema ”matrice-albero” di Kirchoff, dimostriamo la formula di Cayley e la formula che esprime il numero di alberi generatori tramite lo spettro laplaciano.

0.1 Richiami sul laplaciano di un grafo

D(h)(v) def = X

e∼v

(−1) e,v h(e),

per ogni h ∈ H, v ∈ V . Il laplaciano di G `e l’operatore

L def = D ◦ D ∗ ∈ End(F),

dove D ∗ : F → H `e l’operatore aggiunto di D (rispetto alle strutture euclidee standard di F e di H); com’`e noto (v. [[1]]), vale

L = ∆ − A, (1)

dove A ∈ End(F) `e l’operatore d’adiacenza, definito da A(f )(v) def = X

w∼v

f (w), ∀f ∈ F, v ∈ V

e ∆ ∈ End(F) `e definito da

∆(f )(v) def = d(v)f (v)

(essendo d(v) il grado di v ∈ V ). Inoltre (v. sempre [[1]]) si ha che:

1. L `e simmetrico e semidefinito positivo;

2.

Ker L = KerD ∗ = h1i = {funzioni costanti}

Im L = Im D = h1i ⊥ = {funzioni a somma nulla}

in particolare, L ha rango n − 1.

0.2 Richiami sull’aggiugato di una matrice

Sia A ∈ M n (R) una matrice quadrata reale d’ordine; l’aggiugato (o aggiunto classico) di A `e la matrice

adj(A) = kA ji k n i,j=1 ,

con A ij complemento algebrico di a ij in A (cio`e, il prodotto di (−1) i+j per il minore di A ottenuto eliminando la i-ma riga e la j-ma colonna). Le principali propriet`a dell’aggiugato sono:

a) Valgono le identit`a

adj(A) A = A adj(A) = |A| I; (2)

in particolare, se A `e invertibile vale

adj(A) = |A| A −1 (3)

b)

adj(AB) = adj(B)adj(A), adj(I) = I (4) c)

adj(A T ) = adj(A) T (5)

d)

adj(λA) = λ n−1 adj(A), per ogni λ ∈ R

e) se A ha rango n − 1, allora adj(A) ha rango 1; se A ha rango minore di n − 1, allora adj(A) = 0

f ) Se P `e una proiezione ortogonale (cio`e P 2 = P = P T ) di rango n − 1, allora

adj(P ) `e la proiezione ortogonale complementare (cio`e quella sulla retta

KerP )

g) se R `e ortogonale, allora lo `e anche adj(R)

Dimostriamo, di queste proprietà, solo quelle che non compaiono già nell’appendice di [[1]]. La (4) 1 segue banalmente da (3) quando A è invertibile; nel caso

|A| = 0, basta tenere conto che l’insieme GL(n, R) delle matrici invertibili è denso in M n (R) e che la condizione (4) 1 descrive un sottoinsieme chiuso di M n (R), per cui, se è valida nell’insieme GL(n, R) delle matrici invertibili lo è anche in M n (R) = GL(n, R).

La proprietà d) è un’immediata conseguenza della definizione di aggiugato e della multilinearità dei determinanti.

La propriet`a f) segue facilmente dalle propriet`a b), c), e); infatti, da (4) 1

segue

adj(P ) 2 = adj(P 2 ) = adj(P )

per cui, se adj(P ) non `e nulla (cio`e, per la e), se P ha rango n − 1), allora essa

`e una proiezione di rango 1; d’altra parte, la (5) implica che dalla simmetria di P segue quella di adj(P ), per cui anche adj(P ) `e una proiezione ortogonale; che poi l’immagine di tale proiezione sia il kernel di P segue banalmente dalla (2) per A = P .

La propriet`a g) segue anch’essa banalmente dalle propriet`a b) e c):

adj(R)adj(R) T = adj(R T R) = adj(I) = I

0.3 Corollari del teorema di Kirchoff

Ricordiamo l’enunciato del teorema ”matrix-tree” di Kirchoff (per la dimostrazione, v. [2] oppure [3]):

Theorem 1 (Teorema ”Matrix-Tree”) Detto L = ∆ − A il laplaciano del grafo connesso G, vale

adj(L) = kJ, (6)

con J matrice con tutte le entrate uguali a 1 e

k = k(G) = numero degli alberi generatori di G

Mostriamo come da tale teorema seguano facilmente la formula di Cayley sul numero di alberi con insieme di vertici assegnato, e un’altra espressione di k(G) tramite gli autovalori del laplaciano.

Proposition 2 (Formula di Cayley). Il numero di alberi che si possono costru-

ire su n vertici `e n n−2

); allora da (1) segue che

L = ∆(K n ) − A(K n ) = (n − 1)I n − (J n − I n )

(7)

= nI n − J n ,

con I n matrice identica e J n = 1 · 1 T matrice con tutte le entrate uguali a 1.

Notiamo che (1/n)J `e la (matrice rappresentativa della) proiezione ortogonale sulla retta h1i, in quanto

J 2 = nJ, Im J = h1i , J T = J;

quindi, da (7) segue che

L 2 = n 2 I + J 2 − 2nJ = n(nI − J) = nL,

cioè (1/n)L è la proiezione ortogonale su Im L = h1i ⊥ ; ma allora, applicando le proprietà f) e d) dell’aggiugato, si ha che

1

n n−1 adj(L) = adj( 1 n L)

è la proiezione ortogonale su KerL = h1i, cioè coincide con (1/n)J, cioè adj(L) = n n−2 J,

da cui, tenendo conto del teorema di Kirchoff, segue l’asserto.

Come secondo corollario del teorema ”matrix-tree”, dimostriamo la seguente formula alternativa per il numero degli alberi generatori.

Proposition 3 Sia λ 1 = 0 < λ 2 ≤ · · · ≤ λ n lo spettro laplaciano di un grafo connesso G; allora il numero degli alberi generatori di G `e

k(G) = λ 2 · · · λ n

n

Proof. Osserviamo che h1i = KerL e h1i ⊥ = Im L sono spazi invarianti per L;

D(h)(v) ^def = X

(−1) ^e,v h(e),

L ^def = D ◦ D ^∗ ∈ End(F),

dove D ^∗ : F → H `e l’operatore aggiunto di D (rispetto alle strutture euclidee standard di F e di H); com’`e noto (v. [[1]]), vale

dove A ∈ End(F) `e l’operatore d’adiacenza, definito da A(f )(v) ^def = X

∆(f )(v) ^def = d(v)f (v)

Ker L = KerD ^∗ = h1i = {funzioni costanti}

Im L = Im D = h1i ^⊥ = {funzioni a somma nulla}

adj(A) = kA ji k ⁿ _i,j=1 ,

con A ij complemento algebrico di a ij in A (cioè, il prodotto di (−1) î+j per il minore di A ottenuto eliminando la i-ma riga e la j-ma colonna). Le principali proprietà dell’aggiugato sono:

adj(A) = |A| A ⁻¹ (3)

adj(A ^T ) = adj(A) ^T (5)

adj(λA) = λ ⁿ⁻¹ adj(A), per ogni λ ∈ R

f ) Se P `e una proiezione ortogonale (cio`e P ² = P = P ^T ) di rango n − 1, allora

Dimostriamo, di queste proprietà, solo quelle che non compaiono già nell’appendice di [[1]]. La (4) ₁ segue banalmente da (3) quando A è invertibile; nel caso

adj(P ) ² = adj(P ² ) = adj(P )

adj(R)adj(R) ^T = adj(R ^T R) = adj(I) = I

ire su n vertici `e n ⁿ⁻²

con I n matrice identica e J n = 1 · 1 ^T matrice con tutte le entrate uguali a 1.

J ² = nJ, Im J = h1i , J ^T = J;

L ² = n ² I + J ² − 2nJ = n(nI − J) = nL,

cioè (1/n)L è la proiezione ortogonale su Im L = h1i ^⊥ ; ma allora, applicando le proprietà f) e d) dell’aggiugato, si ha che

n ⁿ⁻¹ adj(L) = adj( 1 n L)

è la proiezione ortogonale su KerL = h1i, cioè coincide con (1/n)J, cioè adj(L) = n ⁿ⁻² J,

Proof. Osserviamo che h1i = KerL e h1i ^⊥ = Im L sono spazi invarianti per L;

di conseguenza, detta (w 1 , . . . , w n−1 ) una base ortonormale di h1i ^⊥ , la matrice di L nella base ortonormale (w 1 , . . . , w n−1 , 1/ √

L = R ^T LR, e

adj(L) = adj(R)adj(e L)adj(R) ^T = adj(R)adj(e L)adj(R) ⁻¹

T r(adj(L)) = T r(adj(e L)) = λ ₂ · · · λ _n ; (8) ma, per la (6), vale anche