1996. április 11.

2^{n} × 2^{n} méretű Hadamard-mátrix közvetlen konstrukciója:

\begin{matrix}H_{n} : 2^{[n]} × 2^{[n]} & → \{ −1, 1 \} \\ (I, J) & ↦ (−1)^{|I∩J|}. \end{matrix}

Lemma: H_{n} egy Hadamard-mátrix.

Bizonyítás: Közvetlen számolás, végen kombinatorikus okokskodással.

Kitérő: bijektív bizonyítással belátjuk, hogy egy nemüres halmaznak ugyanannyi páros elemszámú részhalmaza van mint páratlan.

⋆

Hadamard-mátrixok és blokkrendszerek kapcsolata.

H 4n × 4n méretű Hadamard-mátrix normálalakra hozatala (az első sor és oszlopba 1-esek hozatala esetleges előjel váltásokkal), majd az utolsó 4n − 1 sor és oszlop által adott mátrixban a −1-esek 0-vá változtatásával egy B_{H} halmazrendszerhez jutunk.

Tétel: B_{H} egy (4n − 1, 2n − 1, n − 1) paraméterű blokkrendszer.

Bizonyítás: v = b = 4n − 1 a definíció alapján. k = 2n − 1 könnyen adódik, hogy normálalakban az első (csupa 1) oszlopon kívül minden oszlopban 2n darab 1-es van. λ = n − 1 könnyen adódik már korábbi meggondolások alapján.

Következmény: Ha létezik 4n×4n méretű Hadamard-mátrix, akkor létezik (4n−1, 2n−1, n−1) paraméterű blokkrendszer is.

A fenti konstrukció meg fordítható. Ezt a megfordított konstrukciót nem írjuk le, de az érdeklődő hallgatók maguk is megtehetik. Ugyanez vonatkozik a következő tétel eddig nem bizonyított irányára.

Tétel: Akkor és csak akkor létezik 4n × 4n méretű Hadamard-mátrix, ha létezik (4n − 1, 2n − 1, n − 1) paraméterű blokkrendszer. ⋄

⋆

Ismétlés a kvadratikus maradékokról.

q = { 0 } ˙∪Q ˙∪Q̄

, ahol |Q| = |Q̄| = \frac{q−1}{2}.

Tétel: Legyen n olyan, hogy 4n − 1 prímhatvány. Ekkor létezik (4n − 1, 2n − 1, n − 1) blokkrendszer, azaz létezik 4n × 4n-es Hadamard-mátrix.

Bizonyítás: Legyen q = 4n − 1. A konstruálandó blokkrendszer alaphalmaza _{q}. Minden a ∈ _{q}-hoz tartozik egy B_{a} blokk:

B_{a} = { a + i^{2} : i ∈ _{q}^{∗} } = { a + m : m ∈ Q }.

A blokkok elemszáma közös, a kvadratikus maradékok száma, |Q|, \frac{q−1}{2} = 2n − 1. (x^{2} = α egyenletnek kettő vagy nulla megoldása van, ha α ≠ 0 ( _{q} karakterisztikája nem 2) és egy, ha α = 0.) Két adott, α ≠ β ∈ _{q} elemen áthaladó blokkok száma a

\{ \begin{matrix}a + m_{1} = α \\ a + m_{2} = β \\ m_{1}, m_{2} ∈ Q \end{matrix}

egyenletrendszer (a, x, y) megoldásainak száma. Ez ugyanaz, mint a

\{ \begin{matrix}m_{1} − m_{2} = α − β \\ m_{1}, m_{2} ∈ Q \end{matrix}

egyenletrendszer megoldásainak száma. Legyen a megoldás halmaz M(α − β).

Lemma: (i) Ha γ ∈ Q, akkor |M(γ)| = |M(1)|, (ii) Ha γ ∈ Q̄, akkor |M(γ)| = |M(−1)|,

(iii) |M(1) = |M(−1)|. ♢

Következmény: Minden γ ≠ 0 esetén

|M(γ)| = \frac{\frac{q−1}{2} · \frac{q−1}{2} − \frac{q−1}{2}}{q − 1} = \frac{q − 3}{4}.

Egy másik befejezés: Egy (4n−1, 2n−1, λ) blokkrendszerhez jutottunk. A blokkok száma 4n−1, ebből λ számolható. ♢ Ebből adódik az állítás.