Teorija dizajna i Hadamardova matrica

Hadamardova matrica je kvadratna matrica dimenzija n×n čiji su elementi +1 ili -1, a zadovoljavaju uvjet da je produkt bilo koje dvije različite vrstice jednak nuli.

Hadamardov dizajn je dizajn blokova s b blokova, v točaka i k blokova po točki, gdje je svaka dva bloka incidentna s λ točkama. Brojevi b, v, k i λ zadovoljavaju relacije bv=vk i λ(v-1)=k(k-1).

Hadamardova matrica se može koristiti za generiranje Hadamardovog dizajna. Svaka vrsta matrice predstavlja blok u dizajnu, a svaka kolona predstavlja točku. Element matrice na presjeku vrste i kolone je 1 ako je točka incidentna s blokom, a -1 ako nije.

Hadamardov dizajn može se koristiti za konstruiranje kodova za otkrivanje i ispravljanje pogrešaka. Kodovi temeljeni na Hadamardovim dizajnima su poznati po svojoj učinkovitosti u otkrivanju i ispravljanju pogrešaka u prijenosu podataka.

Hadamardove matrice se koriste u raznim znanstvenim i tehničkim područjima, kao što su kombinatorika, teorija kodova, dizajn eksperimenata i statistika.

Simetrični dizajn je vrsta blok dizajna gdje se svi blokovi mogu dobiti permutiranjem elemenata u bilo kojem od njih.

Rezidualni dizajn nastaje izbacivanjem jednog bloka i svih elemenata koji su u njemu iz simetričnog dizajna. Rezultirajući dizajn ima jedan blok manje i jedan element manje nego izvorni dizajn.

Derivirani dizajn se konstruira isključivo od blokova iz simetričnog dizajna koji sadrže jedan unaprijed odabrani element. Broj blokova u deriviranom dizajnu jednak je broju elemenata u izvornom dizajnu.

Bruck-Ryser-Chowla teorem je matematički rezultat koji daje nužne uvjete za postojanje simetričnog blok dizajna. Teorem kaže da ako postoji simetrični (v, k, λ) - blok dizajn, gdje je v broj elemenata, k broj elemenata u svakom bloku, a λ broj elemenata koje dijeli svaka dva bloka, tada mora biti ispunjen jedan od sljedećih uvjeta:

1. v je parno, a (k - λ) je kvadratni ostatak modulo v
2. v je neparno, i (k - λ) je kvadratni ostatak modulo v ili (k - λ) je kvadratni ostatak modulo v + 1

Simetrični (15, 7, 3) - blok dizajn je primjer simetričnog dizajna koji ima 15 elemenata, 7 elemenata u svakom bloku i 3 elementa koje dijeli svaka dva bloka.

Blok dizajn je matematička struktura koja se koristi za organiziranje kolekcije elemenata u podskupove zvane blokovi. Svaki blok sadrži isti broj elemenata, a svaki element se pojavljuje u istom broju blokova.

Kvadratna matrica reda n s unosa 0 i 1 u kojoj je svaka dva retka i svaka dva stupca ortogonalna (tj. njihov skalarni produkt je nula).

Ako je C simetrična konferencijska matrica reda m, tada je matrica H = [[C + Im, C - Im], [C - Im, -C - Im]] Hadamardova matrica reda 2m.

Dizajn je rješiv ako je skup blokova moguće podijeliti na klase, tako da svaki element dizajna pripada točno jednom bloku u svakoj klasi.

Afina ravnina je geometrijski objekt s točkama i linijama koji zadovoljava sljedeće uvjete: 1. Za svaki par različitih točaka postoji točno jedna linija koja prolazi kroz njih. 2. Postoje četiri točke, od kojih nijedna tri nisu kolinearne (ne leže na istoj liniji).

Projektivna ravnina je geometrijski objekt s točkama i linijama koji zadovoljava sljedeće uvjete: 1. Za svaki par različitih točaka postoji točno jedna linija koja prolazi kroz njih. 2. Za svaka dva različita pravca postoji točno jedna točka koja leži na oba. 3. Postoje četiri točke, od kojih nijedna tri nisu kolinearne.

Konstrukcija koja se koristi za stvaranje Šternerovog sistema trojki (STS) za svaki broj elemenata koji je kongruentan s 3 modulo 6 (tj. v = 6t + 3, gdje je t ≥ 1). Osnovna ideja je upotrijebiti simetričnu idempotentnu kvazigrupu neparnog reda (2t + 1) i definirati blokove na temelju elemenata te grupe.

Šternerov sistem trojki (STS) je skup od v elemenata (točaka) i skup od blokova, gdje svaki blok sadrži tri točke, te se svaki par točaka pojavljuje u točno jednom bloku. Boseova konstrukcija je jedna od metoda za izgradnju STS-a za određene vrijednosti v.

Simetrična kvazigrupa je binarna operacija gdje je x ◦ y = y ◦ x za sve x i y. Osim toga, kvazigrupa je idempotentna ako je x ◦ x = x za sve x.

Skolemova konstrukcija se koristi za stvaranje STS-a kada je broj elemenata v paran i kongruentan s 2 modulo 6 (tj. v = 6t + 2, gdje je t ≥ 0). Ona se temelji na Boseovoj konstrukciji, ali umjesto simetrične idempotentne kvazigrupe koristi se simetrična poluidempotentna kvazigrupa parnog reda.

Simetrična kvazigrupa parnog reda koja je poluidempotentna je kvazigrupa koja zadovoljava svojstvo x ◦ x = y za neke x i y. Drugim riječima, nije idempotentna, što je ključna razlika u odnosu na Boseovu konstrukciju.

U Skolemovoj konstrukciji, u blokovima se koriste elementi simetrične poluidempotentne kvazigrupe parnog reda umjesto elemenata simetrične idempotentne kvazigrupe, što je glavna razlika u odnosu na Boseovu konstrukciju.

Konstrukcija STS-a koristi se za stvaranje Šternerovih sistema trojki (STS) za određene vrijednosti broja elemenata (v). Specifično, Boseova konstrukcija se koristi za neparne vrijednosti v, dok se Skolemova konstrukcija koristi za parne vrijednosti v.

Heffterov problem razlika proučava postojanje skupa diferencijskih trojki u konačnom polju. Rješenje problema ovisi o modularnosti veličine polja (v).

Diferencijska trojka je skup od tri elementa (x, y, z) u konačnom polju, gdje je z jednak razlici x i y modulo v.

Heffterov problem razlika ima rješenje modulo v ako postoji Steinerov sustav trojki (STS) s v elemenata.

Peltesohnov teorem navodi da za svaki prirodan broj v, koji je kongruentan s 1 ili 3 modulo 6 i veći od 6 (osim za 9), postoji i rješenje Heffterovog problema razlika modulo v, a i odgovarajući STS(v)

Dva latinska kvadrata su ortogonalna ako se svaka kombinacija elemenata pojavljuje jedino jednom. Ovo je važno za konstruiranje dizajna.

Direktni produkt latinskih kvadrata omogućava konstruiranje većih latinskih kvadrata (i dizajna) iz manjih.

Particioniranje skupa na podskupove s jednakom veličinom.

Steinov sustav trojki (STS) je dizajn blokova s v točaka i v(v-1)/6 blokova, pri čemu svaki blok sadrži tri točke, a svaka dva bloka imaju točno jednu zajedničku točku.

Ciklički Steinov sustav trojki je Steinov sustav trojki u kojem se svi blokovi mogu dobiti translacijom jednog baznog bloka.

Konstrukcija cikličkog STS(v) za sve v ≥ 7, v ≠ 9, temelji se na rješenju Heffterovog problema razlika.

Bazni blok je blok koji se koristi za generiranje ostalih blokova u cikličkom dizajnu translacijom.