Hadamardmatrix

Een hadamardmatrix is een vierkante en orthogonale matrix, waarvan de elementen +1 dan wel −1 zijn. Orthogonaal wil zeggen dat ieder tweetal van elkaar verschillende kolommen in een hadamardmatrix twee vectoren zijn, die loodrecht op elkaar staan. Hadamardmatrices zijn naar de Franse wiskundige Jacques Hadamard genoemd.

Dergelijke matrices zijn vrijwel ongewijzigd bruikbaar als een foutcorrigerende code en de Reed-Muller-codes zijn daar een generalisatie van. Hadamardmatrices worden ook toegepast in 'balanced repeated replication', toegepast door statistici om de variantie van een parameter-schatter vast te stellen. De hadamardmatrix is in een aantal computertalen voor kwantumcomputers een logische kwantumpoort, die een indivuele qubit omzet in een superpositie van twee basisvectoren, zoals de kolomvectoren | 0 > en | 1 >.

Eigenschappen

• Uit de definitie volgt dat voor een hadamardmatrix ${\displaystyle H}$ van orde ${\displaystyle n}$ geldt dat

${\displaystyle H^{\mathrm {T} }H=nI_{n}\ }$

waarbij ${\displaystyle I_{n}}$ de n×n-eenheidsmatrix is. Dus is ${\displaystyle \det H=\pm n^{n/2}}$.

• Wanneer twee kolommen of twee rijen met elkaar worden vergeleken, blijkt dat de helft van de elementen daarin hetzelfde is en de andere helft tegengesteld van teken. Dat volgt eruit dat iedere hadamardmatrix een orthogonale matrix is en alle elementen in een hadamardmatrix 1 of −1 zijn.

• Neem aan dat ${\displaystyle M}$ een complexe matrix is van de orde ${\displaystyle n}$, waarvan de elementen worden begrensd door ${\displaystyle |M_{ij}|\leq 1}$, voor alle ${\displaystyle i,j}$ tussen 1 en ${\displaystyle n}$. Dan stelt de ongelijkheid van Hadamard dat

${\displaystyle |\operatorname {det} (M)|\leq n^{n/2}}$.

Gelijkheid wordt in deze vergelijking bereikt voor een reële matrix ${\displaystyle M}$ dan en slechts dan als ${\displaystyle M}$ een hadamardmatrix is.

• De matrix ${\displaystyle H_{1}={\begin{bmatrix}1\end{bmatrix}}}$ met alleen het element 1 wordt als hadamardmatrix meegerekend. De orde van een hadamardmatrix is altijd 1, 2 of een veelvoud van 4.

Sylvesters constructie

Voorbeelden van hadamardmatrices werden als eerste geconstrueerd door James Joseph Sylvester in 1867. Zij ${\displaystyle H}$ een hadamardmatrix van orde ${\displaystyle n}$. Dan is de matrix

${\displaystyle {\begin{bmatrix}H&H\\H&-H\end{bmatrix}}}$

een hadamardmatrix van de orde ${\displaystyle 2n}$. Deze constatering kan worden herhaald, waardoor een rij matrices ontstaat, bekend onder de naam Walsh-matrices.

${\displaystyle H_{1}={\begin{bmatrix}1\end{bmatrix}},}$

${\displaystyle H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},}$

en

${\displaystyle H_{2^{k}}={\begin{bmatrix}H_{2^{k-1}}&H_{2^{k-1}}\\H_{2^{k-1}}&-H_{2^{k-1}}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1}},}$

voor ${\displaystyle 2\leq k\in N}$, waarbij ${\displaystyle \otimes }$ staat voor het kronecker-product.

Op deze manier construeerde Sylvester voor alle niet-negatieve gehele getallen ${\displaystyle k}$ een hadamardmatrix van de orde ${\displaystyle 2^{k}}$. ^[1] Zo gemaakte matrices worden Sylvester matrix genoemd.

Sylvesters matrices bezitten een aantal speciale eigenschappen. Ze zijn symmetrisch en hebben een spoor gelijk aan nul. De elementen in de eerste kolom en de eerste rij zijn allemaal positief. Van de elementen in alle andere rijen en kolommen zijn er evenveel positief als negatief. Sylvesters matrices zijn nauw gerelateerd aan walshfuncties.

Deze eigenschappen gelden niet voor alle hadamardmatrices. Er is een 12×12 hadarmardmatrix mogelijk met in de eerste kolom alleen 1-en en in eerste de rij behalve op de eerste plaats alleen −1.^[2]