Matriu d'Hadamard

De Viquipèdia
Jump to navigation Jump to search

En matemàtiques, una matriu d'Hadamard, anomenada així en honor al matemàtic francès Jacques Hadamard, és una matriu quadrada amb elements iguals a +1 o -1 i files són mútuament ortogonals. En termes geomètrics, això significa que cada parell de files d'una matriu d'Hadamard representa dos vectors perpendiculars, mentre que en termes combinatoris, vol dir que en cada parell de files el nombre d'elements coincidents són exactament en la meitat de les seves columnes i les entrades no coincidents en les columnes restants. Com a conseqüència d'aquesta definició aquestes propietats les posseeixen tant les columnes com les files. El paralel·lòtop n-dimensional definit per les files d'una matriu d'Hadamard n × n té el volum n-dimensional màxim possible entre paralel·lòtop abastat pels vectors amb elements acotats en valor absolut igual 1. De forma equivalent, una matriu d'Hadamard té un determinant màxim entre les matrius amb elements amb valor absolut inferior o igual a 1 i per tant, és una solució extrema al problema del determinant màxim d'Hadamard.

Certes matrius d'Hadamard poden emprar-se gairebé de manera directa com un codi de correcció d'errors utilitzant un codi d'Hadamard (generalitzat en els codis Reed-Muller), i també s'utilitzen en la replicació repetida equilibrada (BRR), utilitzat pels estadístics per estimar la variància d'un estimador de paràmetres, així com en el disseny d'experiments.

Propietats[modifica]

Sigui H una matriu d'Hadamard d'ordre n. La transposada de H està relacionada amb la inversa segons:

on In és la matriu identitat n× n i HT és la trasposta de H. Per comprovar que això és cert cal tenir present que les files de H són totes elles vectors ortogonals en el camp dels nombres reals i cadascú d'ells té una longitud . Dividint H per aquesta longitud s'obté una matriu ortogonal : és tal que la seva trasposta és la seva inversa. Multiplicant per la longitud es torna a obtenir l'expressió anterior. Com a resultat:

on det(H) és el determinant de H.

Suposem que M és una matriu complexa d'ordre n, amb elements acotats per | Mij | ≤1, per a cada i, i j entre 1 i n. Llavors es compleix que el determinant:

La igualtat en aquesta expressió s'aconsegueix per una matriu real M si, i només si, M és una matriu d'Hadamard. L'ordre d'una matriu d'Hadamard ha de ser 1, 2, o un múltiple de 4.

Construcció de Sylvester[modifica]

Els primers exemples de matrius d'Hadamard van ser construïts per James Joseph Sylvester l'any 1867. Sigui H una matriu d'Hadamard d'ordre n. Llavors la matriu amb les particions:

és una matriu d'Hadamard d'ordre 2n. Això es pot aplicar repetidament i condueix a la següent seqüència de matrius, també anomenades matrius de Walsh:

i

per , on denota el producte de Kronecker. D'aquesta manera, Sylvester va construir matrius d'Hadamard d'ordre 2k per tot enter k no negatiu.[1]

Les matrius de Sylvester tenen una sèrie de propietats especials. Són simètriques i, quan k ≥ 1, la seva traça és igual a zero. Els elements de la primera columna i la primera fila són tots positius. Els elements en totes les altres files i columnes es divideixen per igual entre positius i negatius. Les matrius de Sylvester estan estretament relacionades amb les funcions de Walsh.

Construcció alternativa[modifica]

Si representem els elements de la matriu d'Hadamard utilitzant l'homomorfisme de grup, , podem descriure una construcció alternativa de la matriu d'Hadamard a la de Sylvester. Considerem en primer lloc la matriu, , les matrius tenen les columnes formades per tots els nombres de n bits disposats en ordre ascendent. Podem definir recursivament per:

Per inducció es pot demostrar que la imatge de la matriu d'Hadamard sota aquest homomorfisme està donada per

Aquesta construcció demostra que les files de la matriu d'Hadamard es poden considerar com un codi lineal de correcció d'errors de longitud de rang n i distància mínima amb la matriu generadora Aquest codi també es coneix com un codi de Walsh. El codi d'Hadamard, per contra, es construeix a partir de la matriu d'Hadamard per un procediment lleugerament diferent.

Conjectura d'Hadamard[modifica]

La qüestió més important de la teoria de matrius d'Hadamard és la seva pròpia existència. La conjectura d'Hadamard proposa que hi existeix una matriu d'Hadamard d'ordre 4k per a tot enter positiu k. La conjectura d'Hadamard també s'ha atribuït a Paley, tot i que es va considerar implícitament pels altres abans de l'obra de Paley.[2]

Una generalització de la construcció de Sylvester demostra que si i són matrius d'Hadamard d'ordre n i m respectivament, llavors és una matriu d'Hadamard d'ordre nm. Aquest resultat s'utilitza per construir matrius d'Hadamard d'ordre superior una vegada que les d'ordres inferiors són conegudes.

La construcció de Sylvester, de 1867, produeix matrius d'Hadamard d'ordre 1, 2, 4, 8, 16, 32, etc. Les matrius d'Hadamard d'ordre 12 i 20 van ser posteriorment construïdes pel mateix Hadamard l'any 1893.[3] El 1933, Raymond Paley va descobrir el procediment de Paley, que produeix una matriu d'Hadamard d'ordre q + 1 quan q és qualsevol potència primera que és congruent amb 3 mòdul 4 i que produeix una matriu d'Hadamard d'ordre 2 (q + 1) quan q és una potència primera que és congruent amb 1 mòdul 4.[4] El seu mètode utilitza els cossos finits.

L'ordre més petit que no pot ser construït per una combinació dels procediments de Sylvester i de Paley és 92. Una matriu d'Hadamard d'aquest ordre va ser trobada utilitzant un ordinador per L. Baumert, S. W. Golomb, i M. Hall el 1962 al Jet Propulsion Laboratory (JPL).[5] Van utilitzar un procediment, descrit per J. Williamson, que ha donat molts altres ordres addicionals.[6] Avui en dia es coneixen altres mètodes per construir matrius d'Hadamard.

El 2005, Hadi Kharaghani i Behruz Tayfeh-Rezaie van publicar la seu procediment per a la construcció d'una matriu d'Hadamard d'ordre 428.[7] Com a resultat, l'ordre més petit per al qual no es coneix la matriu d'Hadamard és actualment 668.

A partir de 2008, hi ha 13 múltiples de 4 menors o iguals a 2000 per als que no es coneix la matriu d'Hadamard.[8] Són els següents :. 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, i 1964.

Matrius d'Hadamard equivalents[modifica]

Dues matrius d'Hadamard es consideren equivalents si una es pot obtenir de l'altra mitjançant l'anul·lació de files o columnes, o l'intercanvi de files o columnes. A banda de l'equivalència, hi ha una matriu d'Hadamard única pels ordres 1, 2, 4, 8 i 12. Hi ha 5 matrius equivalents d'ordre 16, 3 d'ordre 20, 60 d'ordre 24 i 487 d'ordre 28. Per les matrius d'ordres de 32, 36 i 40 es coneixen milions de matrius equivalents. Emprant una definició més ampla de l'equivalència que també inclogui la transposició, hi ha 4 matrius no equivalents d'ordre 16, 3 d'ordre 20, 36 d'ordre 24 i 294 d'ordre 28.[9]

Generalització i casos especials[modifica]

S'han investigat moltes generalitzacions i casos especials de les matrius d'Hadamard. Una generalització bàsica és la matriu de ponderació, una matriu quadrada en la qual les entrades també poden ser zero i que satisfà : per a alguns w, els seus pesos. Una matriu de ponderació amb el seu pes igual al seu ordre és també una matriu d'Hadamard.

Una altra generalització defineix una matriu d'Hadamard complexa com una matriu en la qual els elements són nombres complexos de mòdul unitat i que satisfà HH* = n In On H* és la conjugada trasposta dH. Les matrius d'Hadamard complexes apareixen en l'estudi d'àlgebra d'operadors i la teoria de la computació quàntica. Les matrius d'Hadamard tipus Butson són matrius d'Hadamard complexes en què els elements són les q-èsimes arrels de la unitat. El terme "matriu d'Hadamard complexa" ha estat utilitzat per alguns autors per referir-se específicament al cas q = 4.

Les matrius d'Hadamard regulars són matrius reals d'Hadamard tals que les sumes de les files i les columnes són totes elles iguals. Una condició necessària de l'existència d'una matriu regular n × n d'Hadamard és que n sigui un quadrat perfecte. Una matriu circulant és òbviament regular i per tant l'ordre d'una matriu d'Hadamard circulant ha de ser un quadrat perfecte. D'altra banda, si existeix una matriu circulant d'Hadamard n × n amb n > 1 llavors n necessàriament ha de ser de la forma 4u2 essent u senar.[10][11]

La conjectura de la matriu circulant d'Hadamard, però, afirma que, a més dels coneguts exemples 1 × 1 i 4 × 4, no existeixen tals matrius. Això ha estat verificat pels 26 valors de u inferiors a 104.[12]

Aplicacions[modifica]

  • Olivia MFSK:- Un protocol digital de radioaficionats dissenyat per treballar en condicions difícils (baixa relació senyal-soroll més la propagació multitrajecte) en bandes d'ona curta.
  • Replicació repetida i equilibrada (BRR): Una tècnica emprada pels estadístics per estimar la variància d'un estimador estadístic.
  • Espectrometria d'obertura codificada: Un instrument per mesurar l'espectre de la llum. L'element de màscara utilitzada en un espectròmetre d'obertura codificada és sovint una variant d'una matriu d'Hadamard.
  • Xarxes amb retroalimentació retardada: Dispositius de reverberació digital que utilitzen matrius d'Hadamard per combinar valors de la mostra.
  • Dissenys de Plackett-Burman: Un tipus de dissenys d'experiments per investigar la dependència d'algunes quantitats mesurades respecte a un cert nombre de variables independents.
  • Dissenys de paràmetres robustos per a investigar els efectes del factor de soroll sobre les respostes.

Referències[modifica]

  1. Sylvester, J. J «Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers». Philosophical Magazine, 34, 1867, pàg. 431 - 475.
  2. Hedayat, A.; Wallis, W. D «Hadamard matrices and their applications». Annals of Statistics, 6, (6), 1978, pàg. 1184 - 1238. DOI: 10.1214/aos/1176344370. JSTOR: 2958712.
  3. Hadamard, J «Résolution d'une question relative aux déterminants». Bulletin des Sciences Mathématiques, 17, 1893, pàg. 240 - 246.
  4. Paley, R. E. A. C «On orthogonal matrices». Journal of Mathematics and Physics, 12, 1933, pàg. 311 - 320.
  5. Baumert, L.; Golomb, S. W.; Hall, M. Jr «Discovery of an Hadamard Matrix of Order 92». Bulletin of the American Mathematical Society, 68, (3), 1962, pàg. 237 - 238. DOI: 10.1090/S0002-9904-1962-10761-7.
  6. Williamson, J «Hadamard's determinant theorem and the sum of four squares». Duke Mathematical Journal, 11, (1), 1944, pàg. 65 - 81. DOI: 10.1215/S0012-7094-44-01108-7.
  7. Kharaghani, H.; Tayfeh-Rezaie, B «A Hadamard matrix of order 428». Journal of Combinatorial Designs, 13, (6), 2005, pàg. 435 - 440. DOI: 10.1002/jcd.20043.
  8. Đoković, D. Z «Hadamard matrices of order 764 exist». Combinatorica, 28, (4), 2008, pàg. 487 - 489. DOI: 10.1007/s00493-008-2384-z.
  9. Wanless, I. M «Permanents of matrices of signed ones». Linear and Multilinear Algebra, 53, 2005, pàg. 427 433. DOI: 10.1080/03081080500093990.
  10. Turyn, R. J «Character sums and difference sets». Pacific Journal of Mathematics, 15, (1), 1965, pàg. 319 - 346. DOI: 10.2140/pjm.1965.15.319.
  11. Turyn, R. J. «Sequences with small correlation». A: Mann H. B. Error Correcting Codes (en anglès). New York (NY): Wiley, 1969, p. 195 - 228. 
  12. Schmidt, B «Cyclotomic integers and finite geometry». Journal of the American Mathematical Society, 12, (4), 1999, pàg. 929 - 952. DOI: 10.1090/S0894-0347-99-00298-2. JSTOR: 2646093.

Bibliografia[modifica]

  • Baumert, L. D.; Hall, Marshall (1965). "Hadamard matrices of the Williamson type". Math. Comp. 19 (91): 442-447. MR 0179093, doi:10.1090/S0025-5718-1965-0179093-2
  • Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Hadamard matrices, orthogonal designs and construction algorithms". Designs 2002: Further computational and constructive design theory. Boston: Kluwer. pp. 133-205,ISBN 1-4020-7599-5
  • Goethals, J. M.; Seidel, J. J. (1970). "A skew Hadamard matrix of order 36". J. Austral. math. Soc. 11 (3): 343-344. doi:10.1017/S144678870000673X
  • Kimura, Hiroshi (1989). "New Hadamard matrix of order 24". Graphs and Combinatorics 5 (1): 235-242. DOI: doi:10.1007/BF01788676
  • Mood, Alexander M. (1964). "On Hotelling's Weighing Problem". Annals of Mathematical Statistics 17 (4): 432-446. DOI: doi:10.1214/aoms/1177730883
  • Reid, K. B.; Brown, E. (1972). "Doubly regular tournaments are equivalent to skew Hadamard matrices". J. Combin. Theory Ser. A 12 (3): 332-338. DOI: doi:10.1016/0097-3165(72)90098-2.
  • Seberry Wallis, Jennifer (1976). "On the existence of Hadamard matrices". J. Combinat. Theory A 21 (2): 188-195. DOI: doi:10.1016/0097-3165(76)90062-5.
  • Seberry, Jennifer (1980). "A construction for generalized hadamard matrices". J. Statist. Plann. Infer. 4 (4): 365-368. DOI: doi:10.1016/0378-3758(80)90021-X
  • Seberry, J.; Wysocki, B.; Wysocki, T. (2005). "On some applications of Hadamard matrices". Metrika 62 (2-3): 221-239. DOI: doi:10.1007/s00184-005-0415-y
  • Spence, Edward (1995). "Classification of hadamard matrices of order 24 and 28". Discr. Math. 140 (1-3): 185-242. doi:10.1016/0012-365X(93)E0169-5
  • Yarlagadda, R. K.; Hershey, J. E. (1997). Hadamard Matrix Analysis and Synthesis. Boston: Kluwer. ISBN 0-7923-9826-2

Enllaços externs[modifica]