Kit di sopravvivenza alle matrici di Hadamard

H

operazioni consentite, otteniamo la matrice normalizzata costruita col metodo Sylvester:

4

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

       

       

+ − + + + − + + + − + + + − + −  

H H

= − − =

H R R C  

+ +

2 2

⇒ R R

R

       

+ + − + + + − + + + − + + + − − H H

4 1 1 4 4  

        + −

2 2

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

       

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 3

Leonardo Calconi – Matrici di Hadamard

)( )( )( )

( + + + + − + + −

, , ,

+ − − + + + + +

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°.

≤ ≤ non esistono metodi o formule per il calcolo del numero delle matrici equivalenti e

Per 4 n 12 >

stabilire l’equivalenza o meno di una matrice per può essere un’impresa assai ardua.

n 12

→Non equivalenza di matrici H

Per tutti gli ordini successivi al 12 fino ad ora esplorati le matrici H non sono più uniche, nel senso

che per ciascuno di questi ordini esistono più matrici H non equivalenti tra loro.

Ad esempio esistono 5 matrici H non equivalenti di ordine 16 che differiscono tra loro solo per

alcune righe ++++++++++++++++

++++++++++++++++

++++++++++++++++

++++++++++++++++

++++++++++++++++ +-+-+-+-++++----

+-+-+-+-+-+-+-+-

+-+-+-+-+-+-+-+-

+-+-+-+-+-+-+-+-

+-+-+-+-+-+-+-+- ++--++--++--++--

++--++--++--++--

++--++--++--++--

++--++--++--++--

++--++--++--++-- +--++--++-+-+-+-

+--++--++--++--+

+--++--++--++--+

+--++--++--++--+

+--++--++--++--+ ++++----++----++

++++----++++----

++++----++++----

++++----++++----

++++----++++---- +-+--+-++--++--+

+-+--+-++-+--+-+

+-+--+-++-+--+-+

+-+--+-++-+--+-+

+-+--+-++-+--+-+ ++----+++--+-++-

++----++++----++

++----++++----++

++----++++----++

++----++++----++ +--+-++-+-+--+-+

+--+-++-+--+-++-

+--+-++-+--+-++-

+--+-++-+--+-++-

+--+-++-+--+-++- ++++++++--------

++++++++--------

++++++++--------

++++++++--------

++++++++-------- +-+-+-+-----++++

+++-+------+-+++

++++--------++++

+-+-+--+-+-+-++-

+-+-+-+--+-+-+-+ ++--++----++--++

++-+---+--+-+++-

++--+-+---++-+-+

++--++----++--++

++--++----++--++ +--++--+-+-+-+-+

++---++---+++--+

++---+-+--+++-+-

+--++-+--++--+-+

+--++--+-++--++- ++++------++++--

+-++-+---+--+-++

+-+-+--+-+-+-++-

++++--------++++

++++--------++++ +-+--+-+-++--++-

+-+---++-+-+++--

+-+--++--+-++--+

+-+--++--+-++--+

+-+--+-+-+-++-+- ++----++-++-+--+

+--++-+--++--+-+

+--+++---++---++

++----++--++++--

++----++--++++-- +--+-++--+-++-+-

+---++-+-+++--+-

+--+--++-++-++--

+--+-+-+-++-+-+-

+--+-++--++-+--+

e per gli ordini successivi ne abbiamo Le cinque matrici di ordine 16 le ho prelevate da:

3 di ordine 20 http://www.uow.edu.au/~jennie/hadamard.html

60 di ordine 24

487 di ordine 28.

Per ordini ancora successivi non è possibile sapere quante siano le matrici H non equivalenti e si è

certi della loro esistenza solo fino all’ordine 428.

6 – Ordine e congettura di Hadamard

Mostriamo che l’ordine delle matrici H può essere solo , o .

1 2 4k

a) Ordine 1 ( ) ( )

+ −

La matrice H di ordine 1 esiste con due equivalenti: .

,

b) Ordine 2

Abbiamo visto che anche la matrice H di ordine 2 esiste, con otto equivalenti.

.

c) Ordine 4k

Poiché la matrice H è ortogonale, il prodotto di due righe o due colonne deve essere zero essendo i

due vettori-riga o i due vettori-colonna ortogonali. Ciò può verificarsi solo se la metà degli elementi

corrispondenti per colonne o per righe ha lo stesso segno e l’altra metà segno opposto.

( )

+ + + + + + − − − − − − ⋅

( )

+ − + − + − + − + − + − = 0 4

Leonardo Calconi – Matrici di Hadamard H

Questa condizione è necessaria e dimostra che l’ordine di una matrice non può essere dispari ma,

H

in ogni caso, non è sufficiente perchè la matrice sia , come si vede da queste due righe

appartenenti ad una matrice di ordine 10:

( )

+ + + + + − − − − − ⋅

( )

+ − + − + + − + − + = 0

non ritenere necessaria la condizione per la quale perchè il prodotto di due

Si faccia attenzione a

H ciascuna

righe di una matrice sia nullo le due righe debbano avere metà degli elementi di un

segno e metà del segno opposto, condizione ben diversa dalla precedente.

Confrontare a tal proposito la matrice (9.11).

n k H

Possiamo dimostrare l’assunto = 4 con un sistema generato, ad esempio, da una matrice 4

normalizzata: + + + =

 a b c d n

+ + + +

   + − − =

a b c d 0



 

+ + − −

= ⇒

H

(6.1)► 

 

+ − + −

4 − + − =

a b c d 0

  

+ − − +

   − − + =

a b c d 0

 ≠ H

), la matrice è .

Poiché i quattro vettori-riga danno luogo ad un insieme L.I. ( det( H ) 0

4

= ⇒ ≡

a n n .

Sommando le quattro equazioni si ottiene 4 0(mod 4)

H deve avere ordine multiplo di 4 non abbiamo affatto

Avendo dimostrato che una matrice H ogni ordine

dimostrato che esiste almeno una matrice per multiplo di 4.

congettura di Hadamard

Questa è infatti la che come tale attualmente è stata verificata (ma non

dimostrata come teorema...) solo per ordini fino a 428.

7 – Determinante

H problema del massimo determinante disuguaglianza di

Una matrice è soluzione del , nel quale la ≤

Hadamard C n c

afferma che se è una matrice quadrata complessa di ordine con 1 si ha

n i , j

n

≤

C n

det( )

(7.1)► 2

C H

è una matrice allora vale il segno di uguaglianza.

Se

Ma non è vero il contrario ! M

Infatti se consideriamo la matrice (6.1) come matrice reale allora su di essa possiamo eseguire

H

non solo le operazioni consentite su righe e su colonne di ma tutte le operazioni elementari su

righe e su colonne, trasformandola in una matrice equivalente a blocchi

     

0 0 2 2 0 0 2 2 0 0 2 2

     

− − − − −

1 1 1 1 1 1 1 1 0 0 2 2

⇒ = − ⇒ = − ⇒

R

R : I I II R : II IV R : II II III

     

− − − − − −

1 1 1 1 1 1 1 1 1 1 1 1

     

     

− − − − − −

1 1 1 1 1 1 1 1 1 1 1 1

−

2 2 1 1 n 2

= = ⋅ = =

da cui abbiamo M n

det( ) 8 2 16

−

2 2 1 1

e pertanto non è vero che se nella disuguaglianza di Hadamard vale il segno di uguaglianza allora la

H H

matrice è . Ecco i determinanti delle matrici uniche:

1 2

= =

det( H ) 1 1

1 1

= =

det( H ) 2 2

2 2

= =

det( H ) 4 16

4 4

= =

det( H ) 8 4096

8 6

= =

det( H ) 12 2985984

12 5

Leonardo Calconi – Matrici di Hadamard

8 – Diagonali

Cos’è una matrice H diagonale ? + =

T

H H I

Una matrice H è diagonale se 2

La più semplice di esse è una delle matrici equivalenti di ordine 2

( )( ) ( )

+ − + + 1 0

+ = 2

+ + − + 0 1

Ed eccone una di ordine 8:

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

     

1 0 0 0 0 0 0 0

     

− + + + − + − − + + − − + − + + 0 1 0 0 0 0 0 0

     

− − + + + − + − + + + − − + − + 0 0 1 0 0 0 0 0

     

− − − + + + − + + + + + − − + − 0 0 0 1 0 0 0 0

+ = 2

     

− + − − + + + − + − + + + − − + 0 0 0 0 1 0 0 0

     

− − + − − + + + + + − + + + − − 0 0 0 0 0 1 0 0

 

   

− + − + − − + + + − + − + + + − 0 0 0 0 0 0 1 0

 

   

− + + − + − − + + − − + − + + + 0 0 0 0 0 0 0 1

 

   

E’ evidente che una matrice H diagonale deve avere la diagonale interamente positiva.

9 – Costruzione di Paley

Esistono diversi altri metodi per la costruzione di matrici H che, non utilizzando la ricorsività,

permettono di ottenerne con ordini non previsti dalla costruzione di Sylvester.

Il più noto e il più accessibile è la costruzione di Paley, per la quale sono necessarie alcune

cognizioni che non diamo per acquisite e che riassumiamo brevemente.

→

Teoremi di Paley

sull’esistenza delle matrici H (1933). k

≡ = +

k

1. Esiste una matrice H di ordine n se n 0(mod 4) ed è della forma n ( p 1) con p

1

≡ = +

potenza prima: 12 0(mod 4) e 12 11 1 . k k

+ ≡

= +

k ( p 1) 2(mod 4) con p

2. Esiste una matrice H di ordine n se è della forma n 2( p 1) e

1

= + ≡

12 2(5 1) e 6 2(mod 4) .

potenza prima: con la costruzione di Paley ma non con la Sylvester.

Possiamo ottenere H 12