Kit di sopravvivenza alle matrici di Hadamard

Matrici di Hadamard

Kit di sopravvivenza alle matrici H

di Leonardo Calconi

26.10.07

Il mio primo incontro con le matrici H avvenne a pagina 167 del secondo libro di calcolo di Tom Apostol: appena mezza pagina in caratteri piccoli, con la definizione ed alcune nozioni elementari.

La cosa sarebbe potuta finire lì se undici pagine dopo il buon Apostol non avesse proposto tra gli esercizi due strane matrici quadrate, una di ordine 4 e una di ordine 6 composte soltanto da 1 e da -1, delle quali invitava a calcolare i determinanti.

Sembrava una provocazione escogitata a bella posta, perché il calcolo dei due determinanti era molto semplice e probabilmente non era il fine unico dell’esercizio, e così iniziai un ping-pong tra pagina 167 e pagina 178 perché qualcosa non mi tornava in merito all’ordine delle matrici...

Incontrare le matrici di Hadamard e decidere di volerne approfondire lo studio è come trovare il Vaso di Pandora e scoperchiarlo, con tutti i mali del mondo che ne fuoriescono e la speranza che rimane imprigionata sul fondo quando si decide di richiuderlo.

Matrici enormi, codici e crittografia, segnali binari e correzioni d’errori, design, telefonini, satelliti.

Una follia.

Un ambito in prima istanza apparentemente (e proditoriamente...) semplice che si accomuna in modo straordinario ad un altro ambito ingannevolmente modesto all’approccio: quello dei numeri primi, con una congettura di esistenza per ambedue non ancora dimostrata.

In questo lavoro ho quindi approfondito solo le nozioni elementari, cercando di assemblare un kit di sopravvivenza alle matrici H ed evitando accuratamente di farmi prendere la mano da una ricerca che altrimenti si sarebbe rivelata, senza alcun dubbio, al di sopra delle mie capacità.

Jacques Salomon Hadamard è nato nella seconda metà dell’800, nell’epoca della macchina a vapore, quando Charles Babbage aveva già progettato ma non realizzato il Difference Engine ed Herman Hollerith doveva ancora costruire la prima calcolatrice a schede perforate, ed è morto novantottenne nel 1963, sei anni prima dello sbarco sulla Luna e una dozzina di anni prima che Seymour Cray premesse per la prima volta il pulsante “Power On” dell’omonimo “One”.

La matematica allunga la vita?

Per i più curiosi, la biografia completa su http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Hadamard.html

Sommario

• 1. Definizione
• 2. Proprietà
• 3. Prodotto di Kronecker
• 4. Costruzione di Sylvester
• 5. Equivalenza
• 6. Ordine e congettura di Hadamard
• 7. Determinante
• 8. Diagonali
• 9. Costruzione di Paley
• 10. Costruzione di Williamson
• 11. Costruzione con matrici binarie
• 12. Codici sequenziali

Ho tratto questa illustrazione da:

Weisstein, Eric W. “Hadamard Matrix” From MathWorld--A Wolfram Web Resource.

http://mathworld.wolfram.com/HadamardMatrix.htm 1

Leonardo Calconi – Matrici di Hadamard

1 – Definizione

H X ( x )

Sia una matrice quadrata di ordine n ed un suo vettore-riga tale che per tutte le sue coordinate sia i, j = ± 1. Se è

(1.1) ► H^TH = nI

la matrice è di Hadamard. In base a questa definizione la matrice H è non singolare ed invertibile e quindi il prodotto (1.1) è commutativo.

Ad esempio, per la matrice simmetrica:

+ + + +
+ − + +
+ + − +
+ + + −

Notazione:

H = (matrice) di Hadamart

si ha:

H^TH = HH^T = 4I₄ =

4 0 0 0
0 4 0 0
0 0 4 0
0 0 0 4

= 4 =

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

2 – Proprietà

Le proprietà seguenti sono sempre verificate in una matrice H.

Il prodotto scalare di due vettori-riga è nullo, quindi essi sono ortogonali.

1. Il prodotto scalare di un vettore-riga per se stesso è uguale all’ordine della matrice, quindi la norma di tale vettore è data da √n.

2. n.

3. L’ordine di una matrice H può essere 1 o 2 o n ≡ 0 (mod 4).

3 – Prodotto di Kronecker

Date due matrici A_n,m, B_p,q si definisce prodotto di Kronecker:

C = A ⊗ B

C_ni+p,mj+q = a_i,jb_p,q

(3.1) ► la matrice C = A ⊗ B.

(2 5) ⊗ (1 6
7 4) =

2 12 5 30
14 8 35 20
−2 12 −9 54
−14 8 −63 36

Se le matrici A e B sono matrici H, la matrice C è una matrice H.

Il prodotto di Kronecker è fondamentale nello studio delle matrici H.

4 – Costruzione di Sylvester

Consideriamo la matrice seguente detta matrice normalizzata H di ordine 2 (per normalizzata si intende una matrice H di ordine qualunque con a_1,j = 1, a_i,1 = 1):

(4.1) ► H₂ =

+ +
+ −

Eseguiamo su di essa il prodotto di Kronecker per ottenere la matrice H normalizzata di ordine 4:

(4.2) ► H₄ = H₂ ⊗ H₂ =

+ + + +
+ − + −
+ + − −
+ − − +

Si vede subito che possiamo generare ricorsivamente la matrice normalizzata H di ordine 8 utilizzando la normalizzata di ordine 4:

(4.3) ► H₈ = H₄ ⊗ H₂ =

+ + + + + + + +
+ − + − + − + −
+ + − − + + − −
+ − − + + − − +
+ + + + − − − −
+ − + − − + − +
+ + − − − − + +
+ − − + − + + −

per cui in generale si ha la costruzione ricorsiva di Sylvester:

(4.4) ► H_s =

H_s−1 H_s−1
H_s−1 −H_s−1

= H_2^k, k = 0, 1, 2, 3...

e poiché la costruzione di Sylvester (1867), con la quale si possono ottenere matrici H di ordine 2^k, produce solo matrici simmetriche a traccia nulla, sembra plausibile chiamarle diversamente come matrici di Sylvester.

Possiamo naturalmente ottenere matrici H anche ricorrendo al prodotto di Kronecker tra matrici di indici diversi:

H₂ ⊗ H₄ = H₈

H₄ ⊗ H₈ = H₃₂

ma non tutte le matrici H, mancando quelle di ordine n ≡ 0 (mod 4) per le quali bisogna ricorrere a costruzioni diverse.

5 – Equivalenza e non equivalenza

Equivalenza di matrici M

Ricordiamo che su una matrice quadrata M possiamo eseguire le operazioni elementari sulle righe per trasformarla in una equivalente.

Operazioni elementari:

• Scambiare tra loro due righe.
• Sommare o sottrarre ad una riga un’altra riga.
• Moltiplicare una riga per uno scalare diverso da zero.

Operazioni elementari combinate:

• Sommare o sottrarre ad una riga un’altra riga moltiplicata per uno scalare diverso da zero.
• Sommare o sottrarre ad una riga la somma di due o più righe.

E poiché è det(M) = det(M^T) le stesse operazioni possono essere eseguite sulle colonne.

Equivalenza di matrici H

Sulle matrici H possiamo invece eseguire solo un numero limitato di queste operazioni per ottenere una matrice equivalente.

Operazioni consentite:

• Scambiare tra loro due righe o due colonne.
• Moltiplicare gli elementi di una riga o di una colonna per -1 (negazione di riga o di colonna).
• Effettuare una trasposizione (operazione che combina le due precedenti).

Se consideriamo la matrice utilizzata nel paragrafo 1 per la definizione ed operiamo su di essa delle operazioni consentite, otteniamo la matrice normalizzata costruita col metodo Sylvester:

H₄ =

− + + +
+ − + +
+ + − +
+ + + −

⇒ R₁R₂ e R₁:

+ + + +
+ − + −
+ + − −
+ − − +

Proponiamoci di quantificare il numero di matrici H equivalenti di ordine 2, per il quale ordine il lavoro da fare è molto semplice.

Le permutazioni distinte della matrice (4.1) (scambio di righe tra loro e di colonne tra loro) sono quattro:

(+ +
+ −), (+ +
− +), (+ −
+ +), (− +
+ +)

mentre le negazioni distinte su ciascuna permutazione sono otto.

Ma come si vede quattro di queste negazioni sono ripetizioni delle permutazioni:

(− −
− +), (− −
+ −), (+ −
− −), (− +
− −)

Inoltre per ciascuna permutazione le otto negazioni possibili sono sempre le stesse.

Pertanto si conclude che per l’ordine 2 le matrici H equivalenti sono otto, quattro dovute alle permutazioni e quattro dovute alle negazioni.

E’ possibile ottenere lo stesso risultato considerando una qualsiasi delle matrici equivalenti e la sua negazione totale e poi ruotarle ambedue per tre volte di 90°.

Per 4 ≤ n ≤ 12 non esistono metodi o formule per il calcolo del numero delle matrici equivalenti e stabilire l’equivalenza o meno di una matrice per n > 12 può essere un’impresa assai ardua.

Non equivalenza di matrici H