Università degli Studi di Firenze Scuola di Scienze Matematiche, Fisiche e Naturali C.d.L. Magistrale in Matematica

Università degli Studi di Firenze

Scuola di Scienze Matematiche, Fisiche e Naturali C.d.L. Magistrale in Matematica

Anno Accademico 2013-2014 Tesi di Laurea

COMPLESSITÀ DELL'ALGORITMO DI STRASSEN PER IL PRODOTTO DI

MATRICI. UN APPROCCIO TENSORIALE

Complexity of Strassen's algorithm for matrix multiplication. A tensor-based approach

Candidato: Relatore:

Luca Simi Prof. Giorgio Ottaviani

Indice

1 Algebra Multilineare 7

1.1 Prodotti Tensoriali . . . 7

1.2 Cambiamenti di Base . . . 10

1.3 Proprietà del Prodotto Tensoriale . . . 11

1.4 Tensori Simmetrici e Tensori Alternanti . . . 13

1.5 Decomposizione di V^⊗3 in GL(V )-sottomoduli . . . 16

1.6 Rango . . . 17

1.7 Flattening . . . 18

2 Geometria Algebrica 21 2.1 Varietà Proiettive . . . 21

2.2 Varietà di Segre . . . 24

2.3 Varietà Secanti . . . 25

2.4 Rango Bordo . . . 25

2.5 Spazio Tangente . . . 27

3 Prodotto di Matrici 31

3

3.1 Algoritmo di Strassen . . . 33

3.2 Varietà di Algoritmi Ottimali . . . 34

3.3 Il Tensore Ψh2,2,2i ha rango 7 . . . 38

3.4 Flattening di Koszul . . . 39

Introduzione

Nel 1969 il matematico tedesco Volker Strassen propose in [14] un algorit- mo innovativo per calcolare il prodotto di matrici. La novità consisteva nelle prestazioni: era in grado di moltiplicare matrici n × n usando soltanto O n^log2(7)
≈ O n^2.81

operazioni, contro le O n³

dell'algoritmo righe per colonne. Parte centrale dell'algoritmo è la possibilità di moltiplicare matrici 2 × 2 usando soltanto sette prodotti invece che otto, come verrà esposto in quanto segue.

Siano A e B matrici 2 × 2 e sia C = AB

A =

"

A1,1 A1,2

A_2,1 A_2,2

#

, B =

"

B1,1 B1,2

B_2,1 B_2,2

#

1. Calcoliamo i seguenti 7 prodotti:

M₁ = (A_1,1+ A_2,2)(B_1,1+ B_2,2) M₂ = A_1,1(B_1,2− B_2,2)

M3 = A2,2(B2,1− B_1,1) M4 = (A2,1+ A2,2)B1,1

M5 = (A1,2+ A1,1)B2,2

M₆ = (A_2,1− A_1,1)(B_1,1+ B_1,2) M₇ = (A_1,2− A_2,2)(B_2,2+ B_2,1)

2. Calcoliamo i coecienti di C usando le seguenti combinazioni lineari 5

degli Mi:

C_1,1= M₁+ M₃− M₅+ M₇ C_1,2= M₂+ M₅

C_2,1= M₄+ M₃

C2,2= M1− M₄+ M2+ M6

La validità dell'algoritmo è facilmente vericabile mediante il calcolo espli- cito. Dal momento che il prodotto di matrici si comporta sui blocchi come sui coecienti possiamo estendere l'algoritmo a matrici 2^k× 2^k utilizzando il metodo divide et impera: ad ogni iterazione si considerano A e B come matrici a blocchi 2 × 2 e si calcolano i sette prodotti in maniera ricorsiva.

Siamo in grado di calcolare C usando in totale 7^k prodotti. Nel caso di ma- trici n × n basta aumentare il formato no alla potenza di due più vicina, inserendo zero nei nuovi coecienti e procedendo come nel caso già visto.

Protagonista nelle applicazioni computazionali, il prodotto di matrici cat- tura l'interesse del mondo tecnico e scientico. La possibilità di migliorare gli algoritmi di cui disponiamo, oltre a costituire un argomento interessante dal punto di vista teorico, ore vantaggi pratici ed economici non indieren- ti. In queste pagine saranno presentati argomenti volti a limitare dal basso il numero di prodotti che un algoritmo ottimale può impiegare. Vedremo come l'algoritmo di Strassen costituisca per il caso 2 × 2 un algoritmo otti- male (risultato provato indipendentemente in [15] e [8]), risultato per il quale verrà presentata una dimostrazione alternativa. Molti argomenti verranno accompagnati da alcuni script utilizzabili in maniera interattiva durante una sessione di Macaulay2.¹

Vorrei rivolgere un ringraziamento particolare al Prof. Giorgio Ottaviani per l'argomento interessante, per i suggerimenti e le esperienze formative proposte durante il periodo dedicato alla tesi.

1Macaulay2 è un software dedicato alla ricerca in geometria algebrica e in algebra commutativa. Viene rilasciato sotto la licenza GNU GPL ed è liberamente scaricabile da http://www.math.uiuc.edu/Macaulay2/

Capitolo 1

Algebra Multilineare

L'algebra multilineare è lo studio delle applicazioni multilineari, ovvero linea- ri in ogni loro argomento. Il primo strumento che verrà presentato in questo capitolo è il linguaggio dei tensori, che permette di parlare in maniera ge- nerale e unicata degli oggetti dell'algebra lineare. Contemporaneamente fornirà un metodo preciso e geometrico per parlare di algoritmi. Le deni- zioni in questo capitolo costituiscono un adattamento di quanto contenuto in [2], in cui la trattazione è svolta in un contesto più generale. In particolare lo studio sarà rivolto a spazi vettoriali di dimensione nita.

1.1 Prodotti Tensoriali

Denizione. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimen- sione nita su K. Il prodotto tensoriale di V1, . . . , V_n è l'insieme

V₁⊗ . . . ⊗ V_n= {T : V₁^∗× . . . × V_n^∗ −→ K multilineare}

Gli elementi di V1⊗ . . . ⊗ V_nsi dicono tensori. Inoltre se di =dim(Vi)diremo che T ∈ V1⊗ . . . ⊗ V_n è un tensore di ordine n e tipo d1× . . . × d_n.

Osservazione. In quanto segue saranno trattati esclusivamente prodotti ten- soriali di spazi vettoriali di dimensione nita. In questo modo sarà lecito identicare uno spazio vettoriale V col suo biduale V^∗∗. Tuttavia l'iden- ticazione non è possibile per spazi vettoriali di dimensione innita: se V è uno spazio vettoriale di dimensione innita la cardinalità di V^∗ è sem- pre maggiore della cardinalità di V . Pertanto possiamo pensare ai tensori

7

T ∈ V₁^∗⊗ . . . ⊗ V_n^∗ come alle applicazioni multilineari T : V₁× . . . × V_n−→ K

Deniamo sul prodotto tensoriale le seguenti operazioni: per ogni S, T ∈ V₁⊗ . . . ⊗ V_n e λ ∈ K siano

(T + S)(α1, . . . , αn) = T (α1, . . . , αn) + S(α1, . . . , αn) (λT )(α₁, . . . , α_n) = λT (α₁, . . . , α_n)

Con queste operazioni il prodotto tensoriale è uno spazio vettoriale.

Tra tutti i tensori ce ne sono alcuni più semplici da costruire e da cal- colare, i tensori decomponibili, deniti da n valutazioni sui Vi. Vedremo nella Proposizione 1.1.2 che ogni tensore in V1⊗ . . . ⊗ V_n può essere scritto come somma di tensori decomponibili.

Denizione. Sia K un campo e siano V1, . . . , V_n spazi vettoriali di dimen- sione nita su K. Un tensore T ∈ V1 ⊗ . . . ⊗ V_n si dice decomponibile se esistono v1 ∈ V₁, . . . , v_n∈ V_n tali che

T (α1, . . . , αn) = α1(v1) · . . . · αn(vn)

per ogni α1 ∈ V₁^∗, . . . , α_n ∈ V_n^∗. In questo caso indicheremo T con la notazione v1⊗ . . . ⊗ v_n.

Osservazione. Un tensore decomponibile in V1 ⊗ . . . ⊗ V_n può essere de- nito usando diverse n-uple di vettori v1, . . . , vn. La seguente proposizione specica esattamente tale ambiguità.

Proposizione 1.1.1. Sia K un campo, e siano V1, . . . , V_n spazi vettoriali di dimensione nita su K. Siano v1, u1 ∈ V₁, . . . , vn, un∈ V_n vettori non nulli, allora v1⊗ . . . ⊗ v_n= u1⊗ . . . ⊗ u_n se e solo se esistono scalari λ1, . . . , λn∈ K tali che ui= λ_iv_i per ogni i e λ1· . . . · λ_n= 1.

Dimostrazione. Procediamo per induzione su n.

• n = 1: u1 = v₁ =⇒ λ₁ = 1

• n > 1: Supponiamo la tesi vera per n − 1 coppie di vettori assegnati.

Fissiamo β ∈ Vn^∗ tale che β(vn) 6= 0 e β(un) 6= 0, abbiamo v1⊗ . . . ⊗ (v_n−1β(vn)) = u1⊗ . . . ⊗ (u_n−1β(un))

1.1. PRODOTTI TENSORIALI 9 Per ipotesi induttiva esistono µ1, . . . , µn−1 tali che ui = µivi per 1 ≤ i ≤ n−2, β(un)un−1 = µn−1β(vn)vn−1e µ1·. . .·µ_n−1= 1. Sostituendo otteniamo

v1⊗ . . . ⊗ v_n−1⊗ v_n= (µ1v1) ⊗ . . . ⊗

 µn−1

β(vn) β(u_n)vn−1



⊗ u_n Dunque possiamo scrivere

v₁⊗ . . . ⊗ v_n−1⊗



v_n− β(v_n) β(un)u_n



= 0 Pertanto segue

v_n= β(v_n) β(u_n)u_n

Ponendo λi = µ_i per 1 ≤ i ≤ n − 2, λn−1 = µ_n−1β(u^β(vn)

n), λ_n = ^β(u_β(vⁿ⁾

n) la tesi è provata.

Proposizione 1.1.2. Sia K un campo, e siano V1, . . . , V_nspazi vettoriali di dimensione nita su K. Sia {v₁^k, . . . , v^k_d

k} base di Vk per 1 ≤ k ≤ n, allora V1⊗. . .⊗V_nè uno spazio vettoriale con base {v¹i1⊗. . .⊗vⁿ_i

n}_1≤ik≤dk. Pertanto dim(V1⊗ . . . ⊗ V_n) =Qn

k=1dim(Vk) Dimostrazione. Sia {α^k₁, . . . , α^k_d

k}la base duale di {v₁^k, . . . , v_d^k

k}per 1 ≤ k ≤ n, sia T ∈ V1⊗ . . . ⊗ V_n. Per ogni scelta di elementi βⁱ ∈ V_i^∗ possiamo scrivere βⁱ=P

j1λⁱ_j

iα_jⁱ

i per qualche coeciente λⁱ_ji = βⁱ(v_jⁱ

i), dunque:

T (β¹, . . . , βⁿ) = T



 X

j1

λ¹_j1α¹_j1, . . . ,X

jn

λⁿ_jnαⁿ_jn





= X

j1,...,jn

λ¹_j1 · . . . · λⁿ_jnT (α¹_j1, . . . , αⁿ_jn)

= X

j1,...,jn

β¹(v_j¹₁) · . . . · βⁿ(v_jⁿ_n)T (α¹_j1, . . . , αⁿ_jn)

= X

j1,...,jn

T (α¹_j1, . . . , αⁿ_jn)(v_j¹₁ ⊗ . . . ⊗ v_jⁿ

n)(β¹, . . . , βⁿ) Dunque, ponendo Tj1,...,jn = T (α¹_j

1, . . . , αⁿ_jn) ∈ K, possiamo scrivere:

T = X

j1,...,jn

T_j1,...,jn(v¹_j1⊗ . . . ⊗ vⁿ_j

n)

Osserviamo inne che Ti1,...,in = T (α¹_i1, . . . , αⁿ_in), dunque se T = 0 abbiamo Ti1,...,in = 0 per ogni i1, . . . , in. Dunque la tesi è provata.

Osservazione. I tensori decomponibili costituiscono dunque gli ingredienti fondamentali per costruire un qualsiasi tensore, pertanto possiamo rappre- sentare un tensore come un array n-dimensionale (confrontare con il teorema 1.1.2):

Un modo equivalente per descrivere un tensore T nelle basi assegnate è usare una lista di slice: tensori di ordine inferiore ottenuti dalle sezioni di T lungo una direzione ssata.

1.2 Cambiamenti di Base

Denizione. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimen- sione nita su K. Il gruppo dei cambiamenti di base è il gruppo

G =GL(V1) × . . . ×GL(Vn)

che agisce sui tensori decomponibili in modo naturale ponendo (g₁, . . . , g_n)(v₁⊗ . . . ⊗ v_n) = (g₁v₁) ⊗ . . . ⊗ (g_nv_n) ed estendendo l'azione linearmente.

Osservazione. Fissate delle basi sugli spazi V1, . . . , Vn un tensore è identi- cato da un array n-dimensionale. È interessante capire come questa rappre- sentazione si trasformi sotto cambiamenti di base negli spazi V1, . . . , V_n.

1.3. PROPRIETÀ DEL PRODOTTO TENSORIALE 11 Proposizione 1.2.1. Sia K un campo e siano V1, . . . , Vn spazi vettoria- li di dimensione nita su K. Sia {v1^k, . . . , v^k_d

k} base di Vk, con base duale {α^k₁, . . . , α^k_d

k}. Sia T ∈ V1⊗ . . . ⊗ V_n e per 1 ≤ k ≤ n con coordinate Ti1,...,in

nella base corrispondente su V1⊗ . . . ⊗ V_n. Se {w₁^k, . . . , w^k_d

k} è una nuova base di Vk e vale v_j^k = P

ia^k_i,jw_i^k le coordinate di T nella nuova base su V₁⊗ . . . ⊗ V_n sono date dagli scalari

T_j⁰_1,...,jn = X

i1,...,in

a¹_j1,i1 · . . . · a_jⁿ_n,inTi1,...,in

Dimostrazione. Come già osservato nella Proposizione 1.1.2 possiamo scri- vere

T_j1,...,jn = T (α¹_j1, . . . , αⁿ_jn) dunque

T = X

i1,...,in

Ti1,...,in(vi1 ⊗ . . . ⊗ v_in)

= X

i1,...,in

Ti1,...,in







 X

j1

a¹_j1,i1w¹_j1



⊗ . . . ⊗



 X

jn

ajn,inw_jⁿ_n









= X

j1,...,jn



 X

i1,...,in

a¹_j1,i1· . . . · aⁿ_j

n,inTi1,...,in



 w_j¹₁ ⊗ . . . ⊗ w_jⁿ

n

1.3 Proprietà del Prodotto Tensoriale

Proposizione 1.3.1. Sia K un campo e siano U, V, W spazi vettoriali di dimensione nita su K, allora:

1. U ⊗ V ' V ⊗ U

2. U ⊗ V ⊗ W ' (U ⊗ V ) ⊗ W ' U ⊗ (V ⊗ W ) 3. Se U ' U⁰ e V ' V⁰ allora U ⊗ V ' U⁰⊗ V⁰ 4. (U ⊗ V )^∗' U^∗⊗ V^∗.

5. U^∗⊗ V 'Hom(U, V )

Dimostrazione. Per ogni punto dell'enunciato costruiamo esplicitamente un isomorsmo naturale (indipendente dalle basi assegnate).

1. Costruiamo l'isomorsmo mandando un tensore A ∈ U ⊗V nel tensore B ∈ V ⊗ U denito ponendo per ogni α ∈ U^∗, β ∈ V^∗

B(β, α) = A(α, β)

L'applicazione così denita è lineare e invertibile (basta invertire i ruoli di U e V nell'enunciato).

2. Deniamo l'isomorsmo sui tensori decomponibili mandando per ogni u ∈ U, v ∈ V, w ∈ W

u ⊗ v ⊗ w 7−→ (u ⊗ v) ⊗ w .

3. Siano φ : U −→ U⁰ e ψ : V −→ V⁰ isomorsmi. Costruiamo l'isomor- smo mandando il tensore A ∈ U ⊗ V nel tensore B ∈ U⁰⊗ V⁰ denito da

B(α, β) = A(α ◦ φ, β ◦ ψ)

per ogni α ∈ (U⁰)^∗, β ∈ (V⁰)^∗. In questo modo è denita un'applica- zione lineare invertibile (per costruire l'inversa è suciente usare φ⁻¹ al posto di φ e ψ⁻¹ al posto di ψ).

4. Costruiamo l'isomorsmo e la sua inversa. Per ogni α ∈ U^∗, β ∈ V^∗ mandiamo α ⊗ β in L ∈ (U ⊗ V )^∗ denito sui tensori decomponibili u ⊗ v da

L(u ⊗ v) = α(u)β(v) ed estendendo linearmente.

Viceversa per costruire l'inversa mandiamo L ∈ (U ⊗ V )^∗ nel tensore G ∈ U^∗⊗ V^∗ denito da

G(u, v) = L(u ⊗ v)

per ogni u ∈ U, v ∈ V , ed estendendo bilinearmente.

5. Costruiamo l'isomorsmo e la sua inversa. Per ogni A ∈ U^∗ ⊗ V mandiamo A in f : U −→ V denendo f(u) per u ∈ U come l'elemento di V^∗∗' V

f (u)(β) = A(u, β)

1.4. TENSORI SIMMETRICI E TENSORI ALTERNANTI 13 per ogni β ∈ V^∗.

Viceversa mandiamo f ∈ Hom(U, V ) in A ∈ U^∗⊗ V denita ponendo A(u, β) = β(f (u))

per ogni u ∈ U, β ∈ V^∗.

1.4 Tensori Simmetrici e Tensori Alternanti

In questa sezione lavoreremo sempre in un campo K con caratteristica nulla.

Consideriamo un tensore T ∈ V^⊗ne una permutazione σ ∈ Sn. Costruiamo σ ◦ T ∈ V^⊗n ponendo:

σ ◦ T : (α1, . . . , αn) 7−→ T α_σ(1), . . . , α_σ(n)

Denizione. Siano K un campo e V uno spazio vettoriale di dimensione

nita su K. Un tensore T ∈ V^⊗nsi dice simmetrico se σ ◦ T = T

per ogni σ ∈ Sn. Indichiamo con SⁿV l'insieme dei tensori simmetrici in V^⊗n.

Denizione. Siano K un campo e V uno spazio vettoriale di dimensione

nita su K. Un tensore T ∈ V^⊗nsi dice alternante se σ ◦ T =sgn(σ)T

per ogni σ ∈ Sn. Indichiamo con ΛⁿV l'insieme dei tensori alternanti in V^⊗n

Osservazione. È facile vericare che SⁿV e ΛⁿV sono sottospazi vettoriali di V^⊗n.

Denizione. Sia V uno spazio vettoriale di dimensione nita su K. Denia- mo operatore di simmetrizzazione l'applicazione lineare πS : V^⊗n −→ V^⊗n denita ponendo

π_S(T ) = 1 n!

X

σ∈Sn

σ ◦ T per ogni T ∈ V^⊗n.

Denizione. Sia V uno spazio vettoriale di dimensione nita su K. De- niamo operatore di antisimmetrizzazione l'applicazione lineare πΛ: V^⊗n−→

V^⊗n denita ponendo

πΛ(T ) = 1 n!

X

σ∈Sn

sgn(σ) · σ ◦ T

per ogni T ∈ V^⊗n.

Proposizione 1.4.1. Sia V uno spazio vettoriale di dimensione nita su K, allora

• π_S(T ) ∈ SⁿV per ogni T ∈ V^⊗n

• π_Λ(T ) ∈ ΛⁿV per ogni T ∈ V^⊗n

Dimostrazione. Sia τ ∈ Sn, allora τ ◦ πS(T ) = 1

n!

X

σ∈Sn

(τ σ) ◦ T

= 1 n!

X

(τ σ)∈Sn

(τ σ) ◦ T

= 1 n!

X

µ∈Sn

µ ◦ T

Analogamente

τ ◦ πΛ(T ) = 1 n!

X

σ∈Sn

sgn(σ)(τσ) ◦ T

= 1

n!sgn(τ) X

(τ σ)∈Sn

sgn(τσ)(τσ) ◦ T

=sgn(τ)1 n!

X

µ∈Sn

sgn(µ)µ ◦ T

=sgn(τ)πΛ(T )

Proposizione 1.4.2. Sia V uno spazio vettoriale su K, allora:

• π_S(T ) = T per ogni T ∈ SⁿV

1.4. TENSORI SIMMETRICI E TENSORI ALTERNANTI 15

• π_S(T ) = 0 per ogni T ∈ ΛⁿV

• π_Λ(T ) = 0per ogni T ∈ SⁿV

• π_Λ(T ) = T per ogni T ∈ ΛⁿV

Dimostrazione. Seguono immediatamente dalla denizione di tensori simme- trici e alternanti.

Corollario 1.4.1. Sia V uno spazio vettoriale su K, allora:

• SⁿV = π_S(V^⊗n)

• ΛⁿV = π_Λ(V^⊗n)

Dimostrazione. Seguono direttamente dalle Proposizioni 1.4.1 e 1.4.2.

Proposizione 1.4.3. Sia V uno spazio vettoriale su K di dimensione d, allora:

• dim (ΛⁿV ) = _n^d

• dim (SⁿV ) = ^d+n−1_n

Dimostrazione. Una base di SⁿV è costituita dai tensori vi1 ⊗ . . . ⊗ v_in con i₁≤ . . . ≤ i_n, mentre una base di ΛⁿV è costituita dai tensori vi1⊗ . . . ⊗ v_in con i1 < . . . < in. Le dimensioni sono pertanto quelle enunciate.

Proposizione 1.4.4. Sia V uno spazio vettoriale su K, allora V ⊗ V = S²V ⊕ Λ²V.

Dimostrazione. Consideriamo un tensore u ⊗ v ∈ V ⊗ V , osserviamo:

u ⊗ v = 1

2(u ⊗ v − v ⊗ u) + 1

2(u ⊗ v + v ⊗ u) La decomposizione si estende al caso generale per linearità.

1.5 Decomposizione di V

in GL(V )-sottomoduli

Il gruppo GL(V ) agisce sul prodotto tensoriale V^⊗3 in modo naturale. Con questa azione diciamo che V^⊗3 è un GL(V )-modulo. Chiameremo GL(V )- sottomodulo un sottospazio GL(V )-invariante di V^⊗3. Abbiamo visto come V^⊗2sia decomponibile in S²V ⊕ Λ²V. Aggiungendo un fattore gli spazi S³V e Λ³V non sono sucienti per ricostruire V^⊗3.

Denizione. Deniamo le seguenti applicazioni ρ : V^⊗3 −→ V^⊗3 ρ1 2 3 = π_S

ρ1 2 3

= πΛ

ρ1 2

: u ⊗ v ⊗ w 7−→ 1

2u ⊗ v ⊗ w − 1

2v ⊗ u ⊗ w ρ1 3 : u ⊗ v ⊗ w 7−→ 1

2u ⊗ v ⊗ w + 1

2w ⊗ v ⊗ u ρ1

3

: u ⊗ v ⊗ w 7−→ 1

2u ⊗ v ⊗ w − 1

2w ⊗ v ⊗ u ρ1 2 : u ⊗ v ⊗ w 7−→ 1

2u ⊗ v ⊗ w + 1

2v ⊗ u ⊗ w ρ1 3

2

= ρ1 3 ◦ ρ₁

2

ρ1 2 3

= ρ1 2 ◦ ρ1 3

Denendo SρV = ρ V^⊗3

per ogni ρ come sopra otteniamo la seguente decomposizione di V^⊗3 in GL(V )-sottomoduli:

Proposizione 1.5.1. V^⊗3 = S1 2 3V ⊕ S1 2 3

V ⊕ S1 3 2

V ⊕ S1 2 3

V

Dimostrazione. Svolgendo i calcoli per i tensori decomponibili di tipo T = u ⊗ v ⊗ wvale

T = ρ1 2 3(T ) +4 3ρ1 2

3

(T ) +4 3ρ1 3

2

(T ) + ρ1 2 3

(T )

dunque

V^⊗3 = S1 2 3V + S1 2 3

V + S1 3 2

V + S1 2 3

V

1.6. RANGO 17 Per vericare che la somma è diretta osserviamo che

ρ²_{1 2 3} = ρ1 2 3

ρ²_{1 3}

2

= 3ρ1 3 2

ρ²_{1 2}

3

= 3ρ1 2 3

ρ²₁

2 3

= ρ1 2 3

Dato uno spazio vettoriale U e un endomorsmo f : U −→ U tale che esiste λ ∈ K \ {0} per cui f² = λf possiamo decomporre U = Ker(f) ⊕ Im(f), infatti per un generico u ∈ U vale

u = f 1 λu

 +



u − f 1 λu



Dunque per ogni funzione ρα tra quelle appena elencate possiamo scrivere V^⊗3 =Ker(ρα) ⊕Im(ρα). Dal momento che ogni spazio SαV =Im(ρα) per provare che la somma è diretta è suciente vericare le seguenti relazioni

S1 2 3

V + S1 3 2

V + S1 2 3

V ⊆Ker (ρ1 2 3)

S1 2 3V + S1 3 2

V + S1 2 3

V ⊆Ker

 ρ1 2

3



S1 2 3V + S1 2 3

V + S1 2 3

V ⊆Ker

 ρ1 3

2



S1 2 3V + S1 3 2

V + S1 2 3

V ⊆Ker



ρ1 2 3





Ovvero provando che ogni mappa ραcomposta con una distinta ρβotteniamo la mappa nulla. Questo è facilmente vericabile sui tensori decomponibili attraverso il calcolo esplicito.

1.6 Rango

Denizione. Siano K un campo e V1, . . . , Vnspazi vettoriali su K. Dato un tensore T ∈ V1⊗ . . . ⊗ V_n il rango di T è il minimo intero R(T ) tale che T è esprimibile come somma di R(T ) tensori decomponibili.

Come mostrato in [9] molti problemi associati allo studio dei tensori sono NP-hard, e viene usato il rango di un tensore come misura della sua complessità. In particolare calcolare il rango è un problema complesso: dato un tensore T ∈ U ⊗ V ⊗ W e un intero r, determinare se R(T ) ≤ r è un problema NP-completo (vedere [6] per una prova). Pertanto un approccio esaustivo diventa impraticabile anche per dimensioni non troppo elevate.

1.7 Flattening

Denizione. Siano K un campo e U, V, W spazi vettoriali su K. Dato T ∈ U ⊗ V ⊗ W il attening di T su W è l'applicazione lineare TW costruita considerando T ∈ Hom((U ⊗ V )^∗, W ). Deniamo il attening sui tensori decomponibili u ⊗ v ⊗ w ponendo

(u ⊗ v ⊗ w)_W : α 7−→ α(u ⊗ v)w ed esteso linearmente.

Proposizione 1.7.1. Sia T ∈ U ⊗ V ⊗ W , allora rk(TW) ≤ R(T ).

Dimostrazione. Possiamo scrivere T come somma di R = R(T ) tensori decomponibili

T =

R

X

r=1

u_r⊗ v_r⊗ w_r dunque

T_W(α ⊗ β) =

R

X

r=1

α(u_r)β(v_r)w_r e dim (Im(TW)) ≤ R.

Proposizione 1.7.2. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimensione nita su K. Sia T ∈ V1⊗ . . . ⊗ V_n. Sia

Ti: V₁^∗× . . . × V_i−1^∗ × V_i+1^∗ × . . . × V_n^∗−→ V_i

1.7. FLATTENING 19 denita da

Ti(α1, . . . , αi−1, αi+1, . . . , αn) (αi) = T (α1, . . . , αn)

per αi ∈ V_i^∗ allora R(T ) = 1 se e solo se rk(Ti) = 1 per ogni 1 ≤ i ≤ n.

Dimostrazione. Possiamo scrivere

T =

R(T )

X

k=1

v^(k)₁ ⊗ . . . ⊗ v^(k)_n Dunque

Ti(α1, . . . , ˆαi, . . . , αn) =

R(T )

X

k=1

α1

 v^(k)₁



· . . . · α_n v^(k)_n

 v_i^(k)

Pertanto Im(Ti) =D

v_i⁽¹⁾, . . . , v_i^{(R(T ))}E. Possiamo aermare che se R(T) = 1 allora rk(Ti) = 1 per ogni i. Viceversa se rk(Ti) = 1 per ogni i allora esiste vi ∈ V_i tale che per qualche λk ∈ K vale v^(k)_i = λ^(k)_i vi per 1 ≤ k ≤ R(T ).

Dunque, sostituendo

T =

R(T )

X

k=1



λ^(k)₁ v₁

⊗ . . . ⊗

λ^(k)_n v_n

=









R(T )

X

k=1

λ^(k)₁



v₁



⊗ . . . ⊗









R(T )

X

k=1

λ^(k)_n



v_n



 Dunque R(T ) = 1.

Macaulay2. Riportiamo di seguito una funzione per calcolare il attening di un tensore. Nel codice viene utilizzata la funzione di¹, che in questo caso restituisce una matrice con i valori assunti dagli elementi del duale sul tensore.

-- input: t scritto come polinomio, e gli spazi U e V come ideali -- output: t_U: U^* -> V scritto come matrice

Flatten = (t, U, V) -> ( R := ring(t);

K := coefficientRing(R);

u := numgens(U);

varU := gens(U);

v := numgens(V);

varV := gens(V);

1Per una descrizione più articolata consultare la pagina: http://www.math.uiuc.edu/

Macaulay2/doc/Macaulay2-1.6/share/doc/Macaulay2/Macaulay2Doc/html/_diff.html

map(K^v, K^u, (i, j) -> (

sub(diff(varV_(0, i), diff(varU_(0, j), t)), K) ) )

)

Capitolo 2

Geometria Algebrica

La geometria algebrica è lo studio dei luoghi degli zeri di famiglie di polinomi.

In questa sezione verranno introdotti gli elementi essenziali per ambientare lo studio dei tensori e del loro rango nel contesto della geometria algebrica.

Gran parte delle denizioni sono tratte da [5].

2.1 Varietà Proiettive

Sia K un campo (algebricamente chiuso). Indichiamo con Pⁿ lo spazio proiettivo su Kⁿ⁺¹.

Denizione. Data una famiglia di polinomi omogenei F ⊆ K[x0, . . . , xn]il luogo degli zeri di F è

Z(F ) = {[P ] ∈ Pⁿ t.c. f(P ) = 0 per ogni f ∈ F}

Una varietà proiettiva è un insieme X ⊆ Pⁿ per cui esiste una famiglia di polinomi omogenei F ⊆ K[x0, . . . , xn]tale che X = Z(F).

Osservazione. Se f ∈ K[x0, . . . , xn] è un polinomio omogeneo f(λP ) = λ^deg(f)f (P ), dunque f(P ) = 0 se e solo se f(λP ) = 0, pertanto la denizione di varietà proiettiva è ben posta.

Proposizione 2.1.1. Siano F, G, Fλ ⊆ K[x0, . . . , x_n] famiglie di polinomi omogenei. Allora:

• Z(F ) ∪ Z(G) = Z ({f g t.c. f ∈ F, g ∈ G}) 21

• T

λ

Z(F_λ) = Z

 S

λ

F_λ



• ∅ = Z ({1})

• Pⁿ= Z ({0})

Osservazione. La proposizione appena vista mostra come le varietà proiettive soddisfano gli assiomi per insiemi chiusi, dunque ci consente di denire una topologia su Pⁿ.

Denizione. La topologia di Zariski su Pⁿ è l'unica topologia denita sce- gliendo come chiusi le varietà proiettive.

Denizione. Una varietà X ⊆ Pⁿ si dice irriducibile se per ogni coppia di varietà Y, Z ⊆ X tale che X = Y ∪ Z si ha Y = X oppure Z = X.

Denizione. Dato X ⊆ Pⁿ possiamo denire l'ideale omogeneo di X come I(X) = {f ∈ K[x0, . . . , x_n]omogeneo t.c. f(P ) = 0 per ogni [P ] ∈ X}

Osservazione. I(X) è eettivamente un ideale omogeneo in K[x0, . . . , xn]. Denizione. Un anello R si dice Noetheriano se ogni suo ideale è nitamente generato.

Proposizione 2.1.2. Sia R un anello. Sono equivalenti:

1. R è noetheriano.

2. Ogni catena ascendente innita I1 ≤ I₂ ≤ . . . ≤ I_n≤ . . . di ideali di R si stabilizza, cioè esiste m ∈ N tale che Im = I_k per ogni k ≥ m.

3. Ogni famiglia ∅ 6= F di ideali di R ha un elemento massimale.

Vale il seguente risultato dovuto a Hilbert, che consente di studiare ideali nell'anello di polinomi come generati da una quantità nita di polinomi.

Teorema 2.1.1 (Basissatz). Sia R un anello. Se R è noetheriano allora R[x]è noetheriano.

Osservazione. Applicando il teorema induttivamente otteniamo che K[x0, . . . , x_n] è un anello noetheriano. Pertanto possiamo aermare che I(X) è nitamente generato, ovvero:

I(X) = (f1, . . . , fm)

2.1. VARIETÀ PROIETTIVE 23 per qualche polinomio omogeneo f1, . . . , fm ∈ K[x0, . . . , xn]. Dunque pos- siamo aermare Z (I(X)) = Z ({f1, . . . , fn}), ovvero ogni varietà proiettiva può essere pensata come un sistema polinomiale nito. Oppure, geometrica- mente, come un intersezione nita di varietà denite da una sola equazione polinomiale (omogenea). Osserviamo inoltre che un chiuso di Zariski è an- che un chiuso euclideo in quanto intersezione (nita) di retroimmagini di 0 mediante un polinomio.

Denizione. Una topologia su uno spazio X si dice Noetheriana se ogni catena discendente di chiusi

Y1 ⊇ Y₂ ⊇ . . . ⊇ Y_n⊇ . . .

si stabilizza, cioè se esiste m ∈ N tale che Ym = Y_k per ogni k ≥ m.

Proposizione 2.1.3. La topologia di Zariski su Pⁿ è noetheriana.

Dimostrazione. Supponiamo per assurdo che esista una catena discendente innita di chiusi tutti distinti Y1 ) Y2 ) . . . ) Yn ) . . .. Corrispondente- mente abbiamo una catena ascendente di ideali tutti distinti

I(Y1) ( I(Y2) ( . . . ( I(Yn) ( . . .

Dunque un assurdo, dal momento che K[x0, . . . , x_n]è un anello noetheriano.

Proposizione 2.1.4. Sia S ⊆ Pⁿ. Indicando con S la chiusura di S nella topologia di Zariski abbiamo S = Z(I(S)).

Denizione. Sia J ≤ K[x0, . . . , xn]un ideale. Il radicale di J è l'insieme

√

J = {f ∈ K[x0, . . . , x_n] t.c. f^k∈ J per qualche k ∈ N}

L'ideale J di dice radicale se J =√ J.

Proposizione 2.1.5. Sia J ≤ K[x0, . . . , xn]un ideale, allora√

J è un ideale.

Inoltre se J è omogeneo anche√

J è omogeneo.

Proposizione 2.1.6. Sia J ≤ K[x0, . . . , x_n]un ideale, allora Z(J) = Z(√ J ). Il rapporto tra Z(◦) e I(◦) è descritto dal Teorema degli Zeri di Hilbert, che stabilisce una corrispondenza biunivoca tra varietà e ideali radicali.

Teorema 2.1.2 (Nullstellensatz). Sia K un campo algebricamente chiuso e J ≤ K[x1, . . . , x_n] un ideale. Allora

I(Z(J )) =√ J

2.2 Varietà di Segre

Vediamo adesso un modo naturale per ambientare lo studio dei tensori decomponibili in uno spazio proiettivo.

Denizione. Sia K un campo e siano V1, . . . , V_n spazi vettoriali di dimen- sione nita su K. Deniamo embedding di Segre l'applicazione

Seg : PV1× . . . × PVn−→ P(V1⊗ . . . ⊗ V_n) ponendo

Seg([v1], . . . , [v_n]) = [v₁⊗ . . . ⊗ v_n]

Osservazione. Sia di =dim(Vi). Assegnando delle basi negli spazi V1, . . . , V_n l'embedding di Segre ha la forma

Seg : ([v1], . . . , [vn]) = [v₁⁰· . . . · v_n⁰, . . . , v₁^d1 · . . . · v_n^dn] dove v_i⁰, . . . , v_i^di sono le componenti di vi nella base assegnata.

Proposizione 2.2.1. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimensione nita su K. L'embedding di Segre

Seg : PV1× . . . × PVn−→ P(V1⊗ . . . ⊗ V_n) è iniettivo.

Dimostrazione. L'enunciato segue immediatamente dalla Proposizione 1.1.1.

Proposizione 2.2.2. Seg(PV1× . . . × PVn) è una varietà proiettiva.

Dimostrazione. Abbiamo visto nella Proposizione 1.7.2 che un tensore T ∈ V₁⊗ . . . ⊗ V_nha rango R(T ) = 1 se e solo se tutti i suoi attening Ti hanno rango rk(Ti) = 1. Dunque i polinomi (omogenei) che deniscono la varietà di Segre sono i minori 2 × 2 di tutti i attening Ti.

Osservazione. Il gruppo G = GL(V1) × . . . ×GL(Vk)dei cambiamenti di base in V1, . . . , Vk agisce sulla varietà di Segre X = Seg(PV1× . . . × PVk) come segue:

(g₁, . . . , g_k) : [v₁⊗ . . . ⊗ v_k] 7−→ [(g₁v₁) ⊗ . . . ⊗ (g_kv_k)]

La varietà di Segre è invariante sotto l'azione di G appena denita. Diremo che X è G-invariante.

2.3. VARIETÀ SECANTI 25

2.3 Varietà Secanti

Abbiamo visto come sia possibile studiare i tensori decomponibili nel con- testo della geometria algebrica. Adesso vediamo come estendere lo studio a tensori di rango qualsiasi.

Denizione. I punti [P1], . . . , [Pk] ∈ Pⁿsono in posizione generale se P1, . . . , Pk

sono linearmente indipendenti, oppure se k > n + 1 e n + 1 tra questi, comunque scelti, sono linearmente indipendenti.

Denizione. Siano X1, . . . , X_k⊆ Pⁿvarietà proiettive. Il join di X1, . . . , X_n è la varietà

J (X₁, . . . , X_n) = [

[P1]∈X1,...,[Pk]∈Xk

in posizione generale

h[P₁], . . . , [P_k]i

Denizione. Sia X ⊆ Pⁿ una varietà proiettiva. La k-esima secante a X è la varietà

σ_k(X) = J (X, . . . , X

| {z }

k volte

)

Osservazione. In questa denizione la chiusura è intesa nella topologia di Zariski, dunque possiamo pensare a σk(X) come la più piccola varietà pro- iettiva contenente sottospazi di dimensione (proiettiva) k −1 passanti per X.

Una prima osservazione è la seguente:

X = σ1(X) ⊆ σ2(X) ⊆ . . . ⊆ σ_k(X) ⊆ . . . ⊆ Pⁿ

2.4 Rango Bordo

Aver utilizzato una chiusura topologica nella denizione di varietà secan- ti ci porta a denire una grandezza leggermente diversa dal rango (e più topologica) per misurare la complessità di un tensore.

Denizione. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimen- sione nita su K. Sia X = Seg(PV1× . . . × PVn), sia [T ] ∈ P(V1⊗ . . . ⊗ V_n). Il rango bordo di T è il minimo intero R(T ) tale che [T ] ∈ σ_{R(T )}(X).

Osservazione. È possibile denire un tensore di rango bordo ≤ r come limite di una successione di tensori di rango ≤ r.

Proposizione 2.4.1. Sia X ⊆ Pⁿ una varietà irriducibile e sia ∅ 6= U ⊆ X un aperto di Zariski, allora U = X sia come chiusura di Zariski sia come chiusura euclidea.

Dimostrazione. Per la chiusura di Zariski: X = (X \ U) ∪ U. Poiché U 6= ∅ deve essere X \ U 6= X, dunque U = X per irriducibilità.

Per la chiusura euclidea: esistono polinomi omogenei f1, . . . , f_k tali che U = {[P ] ∈ X t.c. f1(P ) 6= 0, . . . , f_k(P ) 6= 0}, dunque per la continuità dei polinomi f1, . . . , f_k la chiusura di U contiene anche i punti di X in cui gli fi

si annullano, dunque U = X.

Vediamo nel seguente corollario come sia possibile denire il rango bor- do in termini di limiti nella topologia euclidea. Per una trattazione più approfondita consultare [10] (Corollario 5.1.1.5).

Corollario 2.4.1. Siano V1, . . . , V_n spazi vettoriali di dimensione nita su C. Sia X = Seg(PV1× . . . × PVn), sia [T ] ∈ P(V1⊗ . . . ⊗ V_n), allora R(T ) ≤ r se e solo se esiste una successione di tensori {Tk}_k∈N ⊆ V₁ ⊗ . . . ⊗ V_n di rango R(Tk) ≤ r convergente a T nella topologia euclidea.

Dimostrazione. (Cenni) σr(X)è una varietà irriducibile (perché X è irridu- cibile e il join di due varietà irriducibili è irriducibile). Sia U l'insieme degli elementi [T ] per cui R(T ) ≤ r. Ponendo nella Proposizione 2.4.1 Z = σr(X) il corollario è provato.

Osservazione. Possiamo parlare di algoritmo approssimato per un tensore T quando consideriamo una successione Tn di tensori convergente a T e consideriamo per ogni n una decomposizione di Tn di lunghezza R(T ).

Proposizione 2.4.2. Sia K un campo e siano V1, . . . , V_n spazi vettoriali di dimensione nita su K. Sia [T ] ∈ P(V1⊗ . . . ⊗ V_n) allora R(T ) ≤ R(T ).

Dimostrazione. Se X = Seg(PV1 × . . . × PVn) allora T ∈ σR(T )(X) per denizione.

Proposizione 2.4.3. Sia K un campo, sia M ∈ Kⁿ⊗ K^m, allora R(M) = R(M ).

2.5. SPAZIO TANGENTE 27 Dimostrazione. Dall'algebra lineare sappiamo che una matrice M ha rango rk(M) ≤ r se e solo se è possibile scriverla come somma di r matrici di rango rk = 1. É immediato vericare che una matrice ha rango rk = 1 se e solo se ha rango R = 1 come tensore. Pertanto le due nozioni di rango (per matrici e per tensori di ordine 2) coincidono. Per dimostrare l'asserto è suciente osservare che l'insieme

X_r= {M ∈ M(n × m, K) t.c. rk(M ) ≤ r}

delle matrici di rango ≤ r è una varietà proiettiva. Infatti, dall'algebra lineare, sappiamo che le equazioni che deniscono Xr sono i determinanti dei minori (r + 1) × (r + 1), pertanto Xr = σr(Seg(Pⁿ× P^m)), concludendo così la dimostrazione.

2.5 Spazio Tangente

Denizione. Sia X ⊆ Pⁿ una varietà proiettiva, sia [P ] ∈ X un punto. Lo spazio tangente a X nel punto [P ] è l'insieme

T_{[P ]}X = (

[x₀, . . . , x_n] ∈ Pⁿ t.c.

n

X

i=0

∂f

∂x_i(P ) · x_i = 0 per ogni f ∈ I(X) )

Lemma 2.5.1. (di Terracini) Siano X1, . . . , Xk ⊆ Pⁿ varietà proiettive.

Siano [P1] ∈ X1, . . . , [P_k] ∈ X_k, [P ] ∈ J (X1, . . . , Xn) punti generali tali che [P ] ∈ h[P₁], . . . , [P_k]i. Allora

T_{[P ]}J (X₁, . . . , X_k) = hT_[P1]X₁, . . . , T_[Pk]X_ki

Proposizione 2.5.1. Sia K un campo e siano U, V spazi vettoriali di di- mensione nita su K e sia X = Seg(PU × PV ). Siano u ∈ U, v ∈ V vettori non nulli, allora

T_[u⊗v]X = P(U ⊗ v + u ⊗ V )

Dimostrazione. Fissiamo delle basi in U e in V . Per comodità possiamo supporre u e v come primi elementi di queste basi, dunque letti nelle basi u = (1, 0, . . . , 0)e v = (1, 0, . . . , 0). Lo spazio tangente T[u⊗v](X)è l'insieme delle matrici

x =







x_0,0 · · · x_0,b ... ... ...

x_a,0 · · · x_a,b







per le quali P_{i,j ∂x}^∂F_i,j(u ⊗ v) · xi,j = 0per ogni F ∈ I(X). In particolare I(X) è generato dai minori 2 × 2, pertanto considerando i polinomi della forma

F = xi1,j1xi2,j2 − x_i1,j2xi2,j2

per ogni i1 6= i₂, j₁6= j₂ abbiamo X

i,j

∂F

∂x_i,j(u ⊗ v) · x_i,j = u_i2v_j2x_i1,j1 + u_i1v_j1x_i2,j2 − u_i2v_j1x_i1,j2− u_i1v_j2x_i2,j1 dunque sostituendo i valori delle componenti di u e v: ui = δi,1 e vj = δj,1

abbiamo le equazioni

xi,j = 0

per ogni i 6= 1, j 6= 1. Quindi possiamo concludere che lo spazio tangente è costituito dalle matrici della forma

x =













x0,0 x0,1 · · · x0,b

x1,0 0 · · · 0 ... ... ... ...

xa,0 0 · · · 0













Ovvero sono esattamente gli elementi dello spazio U ⊗ v + u ⊗ V a meno di un fattore moltiplicativo, e questo conclude la dimostrazione.

Proposizione 2.5.2. Sia K un campo e siano V1, . . . , Vn spazi vettoriali di dimensione nita su K. Sia X = Seg(PV1 × . . . × PVn) e siano v1 ∈ V1, . . . , vn∈ V_n vettori non nulli. Ponendo

T_i= v₁⊗ . . . ⊗ v_i−1⊗ V_i⊗ v_i+1⊗ . . . ⊗ v_n abbiamo

T_{[v1⊗...⊗vn]}X = P (T1+ . . . + T_n)

Dimostrazione. La dimostrazione è analoga a quella della Proposizione 2.5.1.

Proposizione 2.5.3. Sia X = Seg(P¹×P¹×P¹), allora σ2(X) = P⁷. Ovvero un tensore generale T di tipo 2 × 2 × 2 ha rango bordo R(T ) ≤ 2.

Dimostrazione. Usando la proposizione 2.5.2 possiamo calcolare lo spazio tangente a σ2(X)nel punto generale [P ], con P = u1⊗ v₁⊗ w₁+ u2⊗ v₂⊗ w₂.

2.5. SPAZIO TANGENTE 29 Possiamo assumere C²= hu1, u2i = hv₁, v2i = hw₁, w2i, dunque

T₁+ T₂= C²⊗ v₁⊗ w₁+ u₁⊗ C²⊗ w₁+ u₁⊗ v₁⊗ C² + C²⊗ v₂⊗ w₂+ u₂⊗ C²⊗ w₂+ u₂⊗ v₂⊗ C²

= C⁸

Dunque T[P ](σ2(X)) = P⁷ e l'asserto è provato.

= +

Capitolo 3

Prodotto di Matrici

Il rango fornisca una buona stima della complessità computazionale di un tensore. In [1] viene provato come la complessità asintotica del prodotto di matrici si possa stimare attraverso il rango. Vedremo in questo capito- lo come ottenere informazioni utili sui possibili algoritmi minimali per un tensore assegnato, in particolare per il tensore prodotto di matrici. Come ultimo argomento vedremo una dimostrazione alternativa del teorema, pro- vato indipendentemente in [8] e in [15], che per moltiplicare matrici 2 × 2 sono necessari almeno sette prodotti. Inoltre rimandiamo il lettore a [11] per un risultato ancora più forte, ovvero che anche il rango bordo per il prodotto di matrici 2 × 2 è sette.

Denizione. Sia K un campo e siano U, V , W spazi vettoriali su K. Siano

A =Hom(U, V ) ' U^∗⊗ V B =Hom(V, W ) ' V^∗⊗ W C =Hom(U, W ) ' U^∗⊗ W

deniamo il tensore composizione di funzioni l'applicazione Ψ : A×B −→ C ponendo:

Ψ(f, g) = g ◦ f

Utilizzando isomorsmi naturali sui prodotti tensoriali è utile considerare Ψcome un tensore nei seguenti spazi

31

A^∗⊗ B^∗⊗ C ' (U^∗⊗ V )^∗⊗ (V^∗⊗ W )^∗⊗ (U^∗⊗ W ) ' (U ⊗ V^∗) ⊗ (V ⊗ W^∗) ⊗ (U^∗⊗ W ) ' (U ⊗ V ⊗ W )^∗⊗ (U ⊗ V ⊗ W ) 'Hom(U ⊗ V ⊗ W, U ⊗ V ⊗ W )

Ovvero come

Ψ : (U^∗⊗ V ) × (V^∗⊗ W ) × (W^∗⊗ U ) −→ K denita ponendo

Ψ(α ⊗ v, β ⊗ w, γ ⊗ u) = α(u)β(v)γ(w) ed estesa linearmente.

In quanto segue poniamo dim(U) = m, dim(V ) = n, dim(W ) = m e per a, b ∈ N identichiamo lo spazio di matrici M(a × b, K) con Hom(K^b, K^a). Denizione. Siano l, n, m ∈ N. Il tensore prodotto di matrici m × n × l è l'applicazione Ψhm,n,li : M(n×l, K)×M(m×n, K) −→ M(m×l, K) denita da

Ψ_hm,n,li(Y, X) = XY

Possiamo vedere Ψhm,n,li∈ M(m × n, K)^∗⊗ M(n × l, K)^∗⊗ M(m × l, K)

Assegnate delle basi in A^∗, B^∗, Cil tensore Ψhm,n,licorrisponde dunque al tensore Ψ letto nelle basi. Se {αi,j}_i,j, {βi,j}_i,j, {cj,i}_i,j sono le basi canoniche rispettivamente su A^∗, B^∗, C vale la decomposizione

Ψ_hm,n,li=X

i,j,k

α_i,j⊗ β_j,k⊗ c_k,i Equivalentemente possiamo pensare

Ψ_hm,n,li=X

i



 X

j,k

α_i,j⊗ β_j,k⊗ c_k,i





=X

i

(XY Z)i,i

=Tr(XY Z)

3.1. ALGORITMO DI STRASSEN 33 per le matrici X, Y, Z corrispondenti alle coordinate rispetto alle basi scelte in A^∗, B^∗, C. Pertanto Ψhm,n,liè invariante rispetto ai seguenti cambi di base in U, V, W :

Tr(XY Z) = Tr((H⁻¹XK)(K⁻¹Y M )(M⁻¹ZH))

per ogni H ∈ GL(U), K ∈ GL(V ), M ∈ GL(W ).

L'invarianza del tensore prodotto di matrici sotto cambiamenti di ba- se in U, V, W è un fatto non sorprendente: per eettuare la composizio- ne di funzioni mediante prodotto di matrici utilizziamo lo stesso algoritmo, indipendentemente dalla base scelta.

U V W

U V W

Y X

H K M

Y⁰ X⁰

XY

(XY )⁰ = X⁰Y⁰

3.1 Algoritmo di Strassen

Seguendo l'algoritmo di Strassen riportato nell'introduzione possiamo rico- struire una decomposizione del tensore Ψh2,2,2i:

Ψ_h2,2,2i= (α_1,1+ α_2,2) ⊗ (β_1,1+ β_2,2) ⊗ (c_1,1+ c_2,2) + α_1,1⊗ (β_1,2− β_2,2) ⊗ (c_2,1+ c_2,2)

+ α_2,2⊗ (β_2,1− β_1,1) ⊗ (c_1,2+ c_1,1) + (α2,1+ α2,2) ⊗ β1,1⊗ (c_1,2− c_2,2) + (α1,2+ α1,1) ⊗ β2,2⊗ (c_2,1− c_1,1) + (−α1,1+ α2,1) ⊗ (β1,1+ β1,2) ⊗ c2,2

+ (−α_2,2+ α_1,2) ⊗ (β_2,2+ β_2,1) ⊗ c_1,1

3.2 Varietà di Algoritmi Ottimali

L'algoritmo di Strassen non è l'unico algoritmo per il prodotto di matrici dotato di soli 7 addendi di rango 1. Infatti è possibile applicare un qual- siasi cambiamento di base negli spazi U, V, W all'algoritmo di Strassen per ottenerne uno equivalente. Inoltre, come provato in [3] e [4] ogni algoritmo ottimale per il prodotto di matrici 2 × 2 è equivalente all'algoritmo di Stras- sen mediante un opportuno cambiamento di basi. Vediamo brevemente il teorema senza entrare nelle questioni più tecniche.

Denizione. Sia T ∈ A^∗⊗ B^∗⊗ C. Un algoritmo di lunghezza R per T è una R-upla

(α1⊗ β₁⊗ c₁, . . . , αR⊗ β_R⊗ c_R) tale che

T =

R

X

r=1

α_r⊗ β_r⊗ c_r

Gli algoritmi di lunghezza R(T ) per T si dicono ottimali.

Osservazione. Sia R = R(T ) e sia (α1⊗β₁⊗c₁, . . . , α_R⊗β_R⊗c_R)un algoritmo ottimale per T . Sia {ek}_k=1,...,d una base per C. Possiamo scrivere

ci=

d

X

k=1

γ_i,ke_k per qualche γi,k ∈ K, dunque

T =

d

X

k=1 R

X

r=1

γ_i,k(α_r⊗ β_r)

!