Kombinatorické štruktúry

Martin Škoviera 5. júna 2003

Obsah

1 Usporiadané množiny 2 1.1 Základné pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Zväzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Distributívne zväzy . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Modulárne a polomodulárne zväzy . . . . . . . . . . . . . . . . . 16

2 Matroidy 17 2.1 Matroidové algoritmy . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Kombinatorické konfigurácie 18 3.1 Konfigurácie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Zapĺňanie priehradok a urnové schémy . . . . . . . . . . . . . . . 18 3.3 Latinské štvorce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Ortogonalita latinských štvorcov . . . . . . . . . . . . . . . . . . 18 3.5 (v, k, λ)-konfigurácie . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.6 Uplné diferenčné množiny . . . . . . . . . . . . . . . . . . . . . . 20 3.7 Hadamardove matice a konfigurácie . . . . . . . . . . . . . . . . . 20 3.8 Konečné projektívne roviny . . . . . . . . . . . . . . . . . . . . . 23 3.9 Ortogonálne latinské štvorce a projektívne roviny . . . . . . . . . 24 3.10 (b, v, r, k, λ)-konfigurácie . . . . . . . . . . . . . . . . . . . . . . . 24 3.11 Steinerove trojice . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Kapitola 1

Usporiadané množiny

1.1 Základné pojmy

Čiastočne usporiadaná množina (skrátene čum, angl. poset) (P, ≤) je množina s binárnou reláciou ≤ taká, že ∀x, y, z ∈ P:

1. x ≤ x reflexívnosť

2. x ≤ y & y ≤ z ⟹ x ≤ z tranzitívnosť

3. x ≤ y & y ≤ x ⟹ x = y antisymetria Príklad

1. (ℕ, ≤) obyčajné lineárne usporiadanie

2. (P(X), ⊆)

3. (ℕ, |) napríklad 3 | 6 ale 3 ∤ 7.

4. {0, 1}^{n} n-rozmerná kocka so zvyčajným usporiadaním.

5. Množina X a D(X) množina všetkých jej rozkladov. σ, τ ∈ D(X): σ ≤ τ, ak σ je zjemnením τ.

6. Eq(X) množina všetkých ekvivalencií na X s ⊆. Eq(X) ⊆ P(X × X) a usporiadanie je zdedené.

Nasleduje zopár ľahkých pojmov, ktoré sa do definície čumu nevošli.

• Ak (P, ≤) je čum a Q ⊆ P, tak na Q máme zdedené usporiadanie ≤_{Q}.

• Ak a ≤ b alebo b ≤ a, tak prvky a, b voláme porovnateľné, inak neporovnateľné.

• Ostrú nerovnosť definujeme ako a < b ⟺ a ≤ b & a ≠ b.

• Maximálne, minimálne, najväčšie, najmenšie prvky definujeme ako zvyčajne. Najmenší prvok značíme 0 a najväčší 1 (ak existujú). Všetky minimálne (resp. maximálne) prvky sú neporovnateľné. Najmenší (resp. najväčší) je porovnateľný so všetkými prvkami.

• Ak a ≤ b, tak [a, b] = {x ∈ P | a ≤ x ≤ b} voláme interval čumu.

• Ak A ⊆ P a v A sú každé dva prvky porovnateľné, tak A je reťazec. A je antireťazec, ak žiadne dva prvky nie sú porovnateľné.

• Hovoríme, že b pokrýva a, značíme a ⋖ b, ak a < x ≤ b ⟹ x = b, t.j. ak [a, b] = {a, b}. Prvky pokrývajúce 0 voláme atómy a prvky pokryté 1 koatómy.

• Dualita čumov: Ak P je čum, tak P^{∗} označuje tú istú množinu s duálnou reláciou ≤^{∗} = ≥. Samozrejme P^{∗∗} = P. Duálne pojmy:

≤  ≥
min  max
najmenší najväčší
0  1
atóm  koatóm

• Dĺžka reťazca C = # prvkov - 1 = # znakov nerovnosti ⋖

• Výška prvku h(a) = dĺžka najdlhšieho reťazca ukončeného prvkom a.

• Nezjemniteľný reťazec je taký, že medzi žiadne dva prvky nemožno vložiť tretí. Ekvivalentne povedané, každý prvok (okrem posledného) je pokrytý nasledujúcim.

• Existujú relácie podobajúce sa na usporiadanie, ale ním nie sú. Napríklad Q množina delení intervalu ⟨0, 1⟩ ako v určitom intergráli. Pre D_{1}, D_{2}, ∈ Q položíme D_{1} ⊴ D_{2} ⟺ ||D_{1}|| ≤ ||D_{2}||, kde || · || je norma delenia. Táto relácia je reflexívna a tranzitívna, ale nie je antisymetrická. Táketo čosi sa volá kváziusporiadanie. Ak (P, ⊴) je kváziusporiadanie a zavedieme na ňom ekvivalenciu x ∼ y ⟺ x ⊴ y & y ⊴ x, tak dostávame čum na P/ ∼.

Hovoríme, že (P, ≤) spĺňa podmienku klesajúcich reťazcov (DCC), ak neexistuje nekonečná ostro klesajúca postupnosť a_{1} > a_{2} > … (Ekvivalentne povedané, ak každá neostro klesajúca postupnosť a_{1} ≥ a_{2} ≥ … sa stabilizuje, t.j. ak existuje n také, že a_{n} = a_{n+1} = …) Duálne definujeme podmienku rastúcich reťazcov (ACC).

Tvrdenie 1 Nech P je čum. Nasledujúce podmienky sú ekvivalentné:

1. Každá neprázdna Q ⊆ P má minimálny (maximálny) prvok.

2. P spĺňa DCC (ACC).

1.2 Zväzy

Nech (P, ≤) je čum. Ak a, b ∈ P, tak ich horným ohraničením je každý prvok taký, že c ≥ a a c ≥ b. Najmenšie horné ohraničenie, ak existuje, sa nazýva spojením prvkov a, b, označuje sa a ∨ b, alebo tiež suprémom sup(a, b). Teda a ∨ b je taký prvok d, že:

1. d ≥ a, d ≥ b

2. ak nejaký prvok k spĺňa 1., tak k ≥ d.

Duálne definujeme priesek a ∧ b ako najväčšie dolné ohraničenie prvkov a, b; tiež ho nazývame infimum a označujeme inf(a, b). Analogicky definujeme tieto pojmy pre ľubovoľnú podmnožinu Q ⊆ P, značíme inf M = ⋀ M a supM = ⋁ M; nemusia však vo všeobecnosti existovať. Príklad

1. (P(X), ⊆), ∧ = ∩, ∨ = ∪ a každá podmnožina P(X) má suprémum aj infimum.

2. (ℕ, |), usporiadanie deliteľnosťou ∧ = nsd, ∨ = nsn

3. {0, 1}^{n}, ∧ = min, ∨ = max

Ak (P, ≤) je usporiadaná množina, v ktorej pre každú dvojicu a, b ∈ P existuje a ∨ b, tak P nazývame ∨-polozväz (horný, spojovací polozväz). Analogicky definujeme ∧-polozväz (dolný, priesekový polozväz) (angl. semilattice).

Teoréma 2 Nech (P, ≤) je ∨-polozväz. Potom platia identity:

1. a ∨ a = a (idempotencia)

2. a ∨ b = b ∨ a (komutatívnosť)

3. (a ∨ b) ∨ c = a ∨ (b ∨ c) (asociatívnosť)

4. a ≤ b ⟺ a ∨ b = b

Obrátene, nech (M, ∘) je grupoid s vlastnosťami 1–3. Ak položíme a ⪯ b ⟺ a ∘ b = b, tak (M, ⪯) je usporiadaná množina, ktorá je vzhľadom na ⪯ horným polozväzom s operáciou spojenia sup(a, b) = a ∘ b. (Analogická veta platí pre ∧-polozväzy.)

Dôkaz. V prvej časti teorémy sa 1 až 4 overí priamo. Nech (M, ∘) je grupoid s vlastnosťami 1–3 a položme a ⪯ b ⟺ _{def} a ∘ b = b. Potom:

1. Idempotencia zaručuje reflexívnosť.

2. Nech a ⪯ b a b ⪯ a. Potom a ∘ b = b a b ∘ a = b. Z komutatívnosti máme a = b ∘ a = a ∘ b = b.

3. Nech a ⪯ b a b ⪯ c, chceme dokázať a ⪯ c. Vieme a ∘ b = b, b ∘ c = c, preto a ∘ c = a ∘ (b ∘ c) = (a ∘ b) ∘ c = b ∘ c = c. Teda a ⪯ c.

4. Treba ešte ukázať, že vzhľadom na ⪯ je sup(a, b) = a ∘ b. Predovšetkým, a ∘ b je horným ohraničením pre a aj b, lebo:

\begin{aligned}a ∘ (a ∘ b) & = & (a ∘ a) ∘ b & = & a ∘ b & & & ⟹ & a ⪯ a ∘ b \\ b ∘ (a ∘ b) & = & (a ∘ b) ∘ b & = & a ∘ (b ∘ b) & = & a ∘ b & ⟹ & b ⪯ a ∘ b \end{aligned}

Ešte treba ukázať, že a ∘ b je najmenšie horné ohraničenie. Nech d je horným ohraničením a aj b, čiže a ⪯ d, b ⪯ d. Ukážeme, že a ∘ b ⪯ d. Naozaj, máme a ∘ d = d, takže (a ∘ b) ∘ d = a ∘ (b ∘ d) = a ∘ d = d. Teda a ∘ b ⪯ d.

□

Dokázali sme, že existuje 1–1 korešpondecia medzi hornými polozväzmi a komutatívnymi pologrupami, v ktorých každý prvok je idempotentný.

Zväz (angl. lattice) je usporiadaná množina (P, ≤), v ktorej každá dvojica prvkov má aj priesek ∧ aj spojenie ∨. Ak v zväze naviac každá podmnožina A ⊆ P má ⋀ A aj ⋁ A, tak sa nazýva úplný zväz. Pritom definujeme, ako sa to tradične robí, ⋀ ∅ = ⋁ P = 1 (najväčší prvok) a ⋀ P = ⋁ ∅ = 0 (najmenší prvok).

Teoréma 3 Nech (P, ≤) je zväz. Potom platia identity:

1. a ∨ a  =  a  a ∧ a  =  a
2. a ∨ b  =  b ∨ a  a ∧ b  =  b ∧ a
3. (a ∨ b) ∨ c =  a ∨ (b ∨ c) (a ∧ b) ∧ c  =  a ∧ (b ∧ c)
4. (a ∨ b) ∧ b =  b  (a ∧ b) ∨ b  =  b ∧ (b ∧ c)
5. a ≤ b  ⟺ a ∨ b = b  ⟺  a ∧ b = a.

Obrátene, nech (P; ∨, ∧) je algebra splňajúca identity 1–4. Potom definovaním a ≤ b ⟺ a ∨ b = b vzniká usporiadaná množina, ktorá je zväzom, pričom sup(a, b) = a ∨ b a inf(a, b) = a ∧ b.

Dôkaz. Ľavú časť 1–3 a 5 sme ukázali v Teoréme 2, pravá vyplýva z duality. 4: a ∨ b ≥ b, preto (a ∨ b) ∧ b = b; pravá časť je duálna. Obrátene, ak máme 1–4, tak dôkazom Teóremy 2 dostávame usporiadanie, ktoré je horným polozväzom. Ukázali sme totiž, že a ∨ b = sup(a, b). Ostáva dokázať, že a ∧ b = inf(a, b). To urobíme takto. Najprv ukážeme, že a ∨ b = b ⟺ a ∧ b = a. ţ ⟹ �: Nech a ∨ b = b. Potom a ∧ b = a ∧ (a ∨ b) = (a ∨ b) ∧ a = (b ∨ a) ∧ a = a. ţ ⟸ �: Duálne. Teda nerovnosť definovaná pomocu ∧ je tá istá ako nerovnosť definovaná pomocou ∨ (ktorú sme prijali za základnú). Preto z toho, že a ∨ b = sup(a, b) a z princípu duality vyplýva, že a ∧ b = inf(a, b). □

Príklady zväzov

1. (P(X), ⊆), úplný zväz 2. (ℕ, |) = T , s operáciou deliteľnosti je úplný zväz

3. Zväz podgrúp, zväz normálnych podgrúp, zväz podpriestorov vektorového priestoru (pre priestory nad konečnými poľami má kombinatorický význam).

4. Zväz rozkladov danej množiny, zväz ekvivalencií na danej množine (v akom sú vzťahu). Má veľký význam pre kombinatoriku.

5. Príklad neuplného zväzu: Zväz otvorených množín na ℝ. (Otvorená množina je disjuktným zjednotením otvorených intervalov, aj nekonečného počtu.) Prienik nekonečného počtu otvorených množín nemusí byť otvorená.

Na každý zväz sa môžeme dívať z dvojakého hľadiska: ako na množinu s reláciou ≤, ale aj ako na množinu s dvoma binárnymi operáciami. Táto dvojznačnosť má svoje dôsledky pre porovnávanie zväzov pomocou morfizmov.

Morfizmus usporiadaných množín (P, ≤) a (Q, ≤) je izotónne zobrazenie f : P → Q, teda také, že a ≤ b v P implikuje f(a) ≤ f(b). Ak zobrazenie prevracia nerovnosti (a ≤ b ⟹ f(a) ≥ f(b)), tak sa nazýva antimónne. Ak f je izotónna bijekcia, ešte nemusí byť izomorfizmus! Izomorfizmus je morfizmus taký, že aj f^{−1} je morfizmus. No f : (ℕ, |) → (ℕ, ≤), x ↦ x je izotónna bijekcia, lebo a | b ⟹ a ≤ b, no f^{−1} nie je izotónne; teda f nie je izomorfizmus. Vo všeobecnosti, bijektívny morfizmus relačných štruktúr (takou je aj usporiadaná množina) nemusí byť izomorfizmom.

No zväz (polozväz) je aj algebraický systém – špeciálny prípad univerzálnej algebry – s dvoma binárnymi operáciami ∧ a ∨. Homomorfizmus zväzov (P; ∧, ∨) a (Q; ∧, ∨) je zobrazenie f : P → Q také, že f(x ∧ y) = f(x) ∧ f(y) a f(x ∨ y) = f(x) ∨ f(y) , t.j. f zachováva operácie. Na to, aby f bolo izomorfizmom zväzov, stačí povedať, aby zachovávalo operácie a bolo bijektívne. Naozaj, nech f je bijektívny homorfizmus. Potom f(x∧x) = f(x)∧f(y) a f^{−1} existuje. Ukážeme, že aj f^{−1} zachováva operáciu ∧. Položme f(x) = a a f(y) = b, čiže f^{−1}(a) = x a f^{−1}(b) = y. (Pre ľubovoľné a, b, také x, y existujú.) Potom z rovnosti:

f(x ∧ y) = f(x) ∧ f(y) dostávame
f^{−1}(f(x ∧ y)) = f^{−1}(f(x) ∧ f(y)),
x ∧ y = f^{−1}(a ∧ b),
f^{−1}(a) ∧ f^{−1}(b) = f^{−1}(a ∧ b).

Záver Ak (P; ∧, ∨, ≤) a (Q; ∧, ∨, ≤) sú zväzy a f : P → Q, tak nasledujúce výroky sú ekivalentné:

1. f je izomorfizmus.

2. f je izotónna bijekcia taká, že aj f^{−1} je izotónne zobrazenie.

3. f je bijektívny homorfizmus vzhľadom na operácie ∧ a ∨.

Obr. 1.1: Zväzy P a Q

Nech (P; ∧, ∨) je zväz a nech Q ⊆ P. Potom Q nazývame podzväzom zväzu P, ak Q je zväz a pre ľubovoľné dva prvky a, b ∈ Q platí inf_{Q}(a, b) = inf_{P} (a, b) a sup_{Q}(a, b) = sup_{P} (a, b); teda výsledky operácií v zväze aj podzväze musia byť tie isté.

Može sa stať, že Q ⊆ P s indukovaným usporiadaním dáva zväz, nie však podzväz zväzu P. Napríklad:

Tvrdenie 4 V každom zväze (P; ∧, ∨) ľubovoľná jednoprvková množina a prázdna množina tvoria podzväz. Ak a, b ∈ P, tak interval [a, b] je tiež podzväz. Prienik podzväzov je podzväz. □

Nech (P, ≤_{P}) a (Q, ≤_{Q}) sú usporiadané množiny. Definujeme priamy súčin ako usporiadanú mnyožinu (P ×Q, ≤_{P Q}), kde (a, b) ≤_{P Q} (c, d) práve vtedy, keď a ≤_{P} c a b ≤_{Q} d.

Tvrdenie 5 Ak (P, ≤_{P}) a (Q, ≤_{Q}) sú zväzy, tak aj (P × Q, ≤_{P Q}) je zväz. □

Dôsledok Priamy súčin reťazcov je zväz. Dôkaz. Každý reťazec je triviálne zväz. □

Pri štúdiu kombinatorických štruktúr si často všímame zobrazenia f, g : N → R, pričom porovnávame zobrazenia pomocu obrazov, ignorujúc podstatu prvkov množiny N (za ktoré berieme napr. N = {0, 1, …, n} ak študujeme napr. variácie k-tej triedy). Na takéto zobrazenia je niekedy výhodné sa dívať ako na multimnožiny, kde každý prvok množiny R sa môže opakovať potrebný počet krát (toľkokrát, koľkokrát je obrazom). Takto vzniká zväz multimnožín M(R) nad R. Pre dve multimnožiny k = (b^{k_{b}}; b ∈ R) a l = (b^{l_{b}}; b ∈ R) (k_{b}, l_{b} sú násobnosti prvku b v k resp. v l) položíme

k ∧ l = (b^{min (k_{b},l_{b})}; b ∈ R),
k ∨ l = (b^{max (k_{b},l_{b})}; b ∈ R).

Je to úplný zväz.

Platí:

1. Ak |R| = n a ℕ_{0} je množina nezáporných celých čísel lineárne usporiadaných podľa veľkosti, tak M(R) ≅ \underbrace{ℕ_{0} × ℕ_{0} × ⋯ × ℕ_{0}}_{r}

Dôkaz. Zobrazenie φ : M(R) → (ℕ_{0})^{r}, k = (b^{k_{b}}; b ∈ R) ↦ (…, k_{b}, …) je hľadaný izomorfizmus. □

2. Ak R je nekonečná spočítateľná množina, tak M(R) ≅ (ℕ, |) = T , kde vpravo je zväz prirodzených čísel usporiadaných deliteľnosťou.

Dôkaz. Nech R = {r_{1}, r_{2}, … }. Potom každú multimnožinu vieme zapísať v tvare k = r_{1}^{k_{1}}r_{2}^{k_{2}} … Nech p_{1}, p_{2}, … je postupnosť prvočísel v rastúcom poradí. Potom dostávame izomorfizmus φ : k = r_{1}^{k_{1}}r_{2}^{k_{2}} … ↦ p_{1}^{k_{1}}p_{2}^{k_{2}} … □

3. Nech C(n) je reťazec dĺžky n (a teda mohutnosti n + 1), t.j. C(n) = {0 < 1 < 2 < ⋯ < n}. Skúmajme interval [1, 360] zväzu deliteľnosti T . Keďže 360 = 2^{3} · 3^{2} · 5, ľahko sa nahliadne, že [1, 360] ≅ C(3) × C(2) × C(1).

4. Zväz rozkladov D(n). Nech D(n) je napríklad množina všetkých rozkladov n-prvkovej množiny {1, 2, …, n}. Nech π ∈ D(n) a nech (π) označuje reláciu ekvivalencia odpovedajúcu π. Potom priesek a spojenie sa ľahko opíše. Potom pre ľubovoľné dva prvky a, b

a(π ∧ σ)b ⟺ a(π)b a a(σ)b
a(π ∨ σ)b ⟺ ∃ postupnosť a = u_{1}, u_{2}, …, u_{t} = b taká, že
pre každé i ∃τ ∈ {π, σ} : u_{i}(τ)u_{i+1}

Napr. pre n = 11:

π = {{1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}},
σ = {{1, 3, 4}, {2, 5}, {6, 7, 11}, {8}, {9, 10}}.

Potom

π ∧ σ = {{1}, {2}, {3, 4}, {5}, {6, 7}, {8}, {9, 10}, {11}},
π ∨ σ = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10, 11}}.

Tieto zväzy sú v kombinatorike aj v teórii zväzov veľmi dôležité. Dlhé roky bol otvorený problém štruktúry podzväzov zväzu D(n). Whitman (1946) vyslovil hypotézu, že každý zväz možno vložiť ako podzväz nejakého zväzu D(n). Túto hypotézu dokázali P. Pudlák a J. Tůma (1977). S týmto zväzom sa čoskoro stretneme.

Obr. 1.2: D(3)

Obr. 1.3: Youngov zväz

5. Usporiadaným analógom multimnožiny je multireťazec. Ak f : N → R je zobrazenie, kde N je reťazec, povedzme N = {1, 2, …, m, … }, R je usporiadaná množina a f je izotónne, tak f(N) je reťazec v R, presnejšie multireťazec, ak zoberieme do úvahy aj usporiadanie v R. Budú nás zaujímať konečné multireťazce a = a_{1}a_{2} … a_{k}, pričom sa dohodneme, že členy budeme zapisovať v nerastúcom poriadku, teda a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{k}. Kvôli porovnávaniu multireťazcovje vhodné zaviesť nový prvok do množiny R̂ = R ∪ {0}, s tým, že 0 < b pre každé b ∈ R. Multireťazec a_{1}a_{2} … a_{k} potom môžeme reprezentovať nekonečným vektorom (a_{1}, a_{2}, …, a_{k+1} , …), kde a_{k+1} = a_{k+2} = ⋯ = 0.

Máme nasledujúce tvrdenie:

Tvrdenie 6 Množina všetkých konečných multireťazcov čiastočne usporiadanej množiny R je usporiadaná reláciou usporiadania po súradniciach (a ≤ b ⟺ a_{i} ≤ b_{i}, i ∈ ℕ). Ak je R zväz (špeciálne, ak je R reťazec), tak táto usporiadaná množina tvorí zväz, ktorý je podzväzom súčinu ∏_{i=1}^{∞} R_{i}, kde R_{i} = R̂ pre každé i.

Dôkaz. Stačí overiť, že priesek a spojenie monotónne klesajúcich slov je tiež také slovo. □

Osobitne sú zaujímavé špeciálne prípady tvrdenia 6. Nech R = ℕ a teda R̂ = ℕ_{0}. Potom vzniknutý zväz sa nazýva Youngovým zväzom a označuje sa Y. Jeho prvky sú nerastúce reťazce prirodzených čísel, kde od istého miesta sú samé nuly.

Je tu ešte jedna dôležitá interpretácia. Nech n = n_{1} + n_{2} + ⋯ + n_{k} je partícia čísla n na k neusporiadaných kladných čísel, k-partícia. Kedže sú neusporiadané, môžeme prepokladať, že n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{k}. Potom

(n_{1}, n_{2}, …, n_{k}, 0, …) ↔ n_{1} + n_{2} + ⋯ + n_{k}

definuje izomorfizmus Youngovho zväzu so zväzom všetkých neusporiadaných partícií. Nulou tohto zväzu je prázdne slovo 0.

6. Partície čísla n. Uvažujem zväz D(n) rozkladov n-prvkovej množiny {1, 2, …, n}. Potom každému rozkladu π = A_{1} ⊎ A_{2} ⊎ ⋯ ⊎ A_{k} prislúcha partícia z(π) čísla n: z(π) = n_{1} + n_{2} + ⋯ + n_{k}, kde n_{i} = |A_{i}| pre i = 1, 2, …, k. Relácia usporiadania na D(n) daná zjemnením rozkladu indukuje usporiadanie na

Obr. 1.4: Diagram zväzu N (7) partícií čísla 7

množine N (n) neusporiadaných partícií čísla n:

∑ n_{i} ≤ ∑ m_{j} ⟺ existujú π, σ ∈ D(n)

také, že π ≤ σ az(π) = ∑ n_{i} a z(σ) = ∑ m_{j}.

Dá sa nahliadnuť, že toto naozaj definuje reláciu usporiadania na N (n) a toto usporiadanie je ekvivalentné s nasledujúcim:

∑_{i=1}^{k}n_{i} ⋖ ∑_{j=1}^{l}m_{j} ⟺ l = k − 1 a všetky m_{j} sú totožné s n_{i}

okrem jednej dvojice ďalej nečitateľné .

Zobrazenie z : D(n) → N (n) je morfizmus usporiadaných množín. Je aj morfizmus zväzov? (Nie, v príklade č. 4 vyššie z(π) ⋗ z(σ), takže z(π) ∧ z(σ) = z(σ) > z(π ∧ σ).) Vo všeobecnosti platí:

Tvrdenie 7 Nech (P; ∧, ∨) a (Q; ∧, ∨) sú zväzy. Potom každý homomorfizmus zväzov je aj morfizmus usporiadania. Obrátene to neplatí. Platí však, že každý izomorfizmus usporiadania je izomorfizmus. □

Príklad Zrejme φ je morfizmus usporiadania, ale φ(a ∨ b) = 1 ≠ m =

a′ ∨ b′ = φ(a) ∨ φ(b). φ nie je ani ∨-homorfizmom ani ∧-homorfizmom.

Na záver tejto časti dokážeme zaujímavé tvrdenie o úplných zväzoch.

Teoréma 8 (Knaster–Tarského o pevnom bode) Nech (P, ≤) je úplný zväz a φ : P → P je izotónne zobrazenie. Potom φ má pevný bod, t.j. existuje x ∈ P také, že φ(x) = x.

Dôkaz. Nech M = {x ∈ P; x ≤ φ(x)}. Zrejme M ≠ ∅, lebo 0 ≤ φ(0). Nech c = supM. Keďže pre každé x ∈ M platí x ≤ c, z izotónnsoti vyplýva x ≤ φ(x) ≤ φ(c). Odtiaľ c = supM ≤ φ(c). Teda

c ≤ φ(c).

Aplikovanín φ dostávame φ(c) ≤ φ(φ(c)), z čoho vyplýva, že φ(c) ∈ M. No potom φ(c) ≤ supM = c, čiže

φ(c) ≤ c.

Z týchto nerovností máme φ(c) = c. □

Príklad Cantor-Bernsteinova teoréma: Nech A, B sú množiny. Ak existujú injekcia φ : A → B a injekcia ψ : B → A, tak exituje bijekcia A → B. Idea dokôzu: Nech X ⊆ A. Skonštujme postupne

X ↦ φ(X) ↦ B − φ(X) ↦ ψ(B − φ(X)) ↦ A − ψ(B − φ(X)).

Uvažujme zobrazenie Ψ : P(A) → P(A),

X ↦ A − ψ(B − φ(X)).

Ľahko sa overí (s použitím známych inklúzií), že Ψ je izotónne. Keďže P(A) je uplný zväz, Ψ má pevný bod – nejakú C ⊆ A. Pomocou tejto množiny sa už ľahko nadefinuje bijekcia.

1.3 Distributívne zväzy

Na úvod pripomenieme nasledovné tvrdenie.

Tvrdenie 9 Nech (P, ≤) je ľubovoľný zväz. Potom sú pravdivé tieto tvrdenia:

1. (izotónnosť ∨) x ≤ y ⟹ x ∨ z ≤ y ∨ z (izotónnosť ∧) x ≤ y ⟹ x ∧ z ≤ y ∧ z

2. (všeobecná izotónnosť) x ≤ z & z ≤ t ⟹ x ∧ z ≤ y ∧ t, podobne pre ∨

3. (distributívne nerovnosti)

x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z) x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z)

4. (modulárna nerovnosť) x ≤ z ⟹ x ∨ (y ∧ z) ≤ (x ∨ y) ∧ z

Dôkaz.

1. Izotónnosť ∧: Ak x ≤ y a z ∈ P, tak x∧z ≤ x ≤ y a zároveň x∧z ≤ z. Teda x ∧ z je dolným ohraničením pre {y, z}. Odtiaľ x ∧ z ≤ y ∧ z. Izotónnosť ∨ sa dokáže podobne.

2. Všeobecná izotónnosť sa dokáže dvojnásobným použitím 1.

3. Distributívnosť ∨: Zrejme y ∧ z, takže z izotónnosti pre ∨ dostávame x ∨ (y ∧ z) ≤ x ∨ z. Analogicky y ∧ z ≤ z, takže x ∨ (y ∧ z) ≤ x ∨ z. Teda x ∨ (y ∧ z) je spoločným dolným ohraničením pre {x ∨ y, x ∨ z}, odkiaľ x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z). Distributívnosť ∧ podobne.

4. Modulárna nerovnosť: Z distributívnej nerovnosti a predpokladu x ≤ z máme x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z) = (x ∨ z) ∧ z.

□

Zväz sa nazýva distributívny, ak v ňom namiesto distributívnych nerovností platí rovnosť, teda ak pre každé x, y, z:

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z),
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).

Zväz sa nazýva modulárny (Dedekindov), ak v ňom namiesto modulárnej nerovnosti platí rovnosť, t.j. ak pre x ≤ z platí x ∨ (y ∧ z) = (x ∨ y) ∧ z. Modulárnymi zväzmi sa budeme zaoberať neskôr, teraz len distributívnymi.

Každá z distributívnych nerovností implikuje druhú. (Ak platí prvá, počítajme z pravej strany druhú: \underbrace{(x ∧ y)} t ∨ (x ∧ z) = t ∨ (x ∧ z), použijeme druhú

rovnosť, využijeme bežné identity a máme.)

Naviac platia aj (konečné !) zovšeobecnené rovnosti

(⋀_{i} x_{i}) ∨ (⋀_{j} y_{j}) = ⋀_{i,j}(x_{i} ∨ y_{j}),

(⋁_{i} x_{i}) ∧ (⋁_{j} y_{j}) = ⋁_{i,j}(x_{i} ∧ y_{j}).

Keďže definujúce rovnosti sú navzájom duálne, tak duál distributívneho zväzu je distributívny. Príklady

1. Zväzy rádu ≤ 4 sú všetky distrinutívne. Medzi 5-prvkovými (je ich 5) sú dva nedistributívne, jeden dokonca nemodulárny:

2. {0, 1}^{n} = P(X) je distributívny.

3. Každý reťazec je distributívny zväz.

4. Súčin distributívnych zväzov je distributívny (aj nekonečný súčin funguje).

5. Podzväz distributívneho zväzu je distributívny zväz. Vyplýva to z toho, že operácie ∧, ∨ sú totožné s operácia v celom zväze.

6. Z ??? vyplýva, že Youngov zväz všetkých partícií (ako podzväz súčinu ∏^{∞} ℕ_{0}) a zväz (ℕ, nsd, nsn) = T (ako podzväz ∏^{∞} ℕ_{0}) sú distributívne.

7. Zväz ??? grupy S_{3} permutácií 2-prvkovej množiny nie je distributívny.

Prvok p (?distributívneho) zväzu L sa nazýva ireducibilný (presnejšie ∨- ireducibilný), ak pre ľubovoľné x, y ∈ L zo vzťahu p = x ∨ y vyplýva p = x alebo p = y. Výraz a = p_{1} ∨ p_{2} ∨ … ∨ p_{k}, v ktorom všetky p_{i} sú ireducibilné sa nazýva rozkladom prvku a na ireducibilné prvky. Rozklad je neskrátiteľný (iredundantný), ak a ≠ p_{1} ∨ p_{2} ∨ … p_{i−1} ∨ p_{i+1} ∨ … ∨ p_{k}, pre každé i. (Atómy a 0 sú zjavne ireducibilné prvky.)

Je zrejmé, že v ľubovoľnom rozklade sú vštetky prvky neporovnateľné, teda tvoria antireťazec. Našim cieľom je ukázať, že štruktúra zväzu je jednoznačne určená množinou jeho ireducibilných prvkov. Lema Nech p je ireducibilný prvok distribitívneho zväzu. Potom z nerovnosti p ≤ a_{1} ∨ … ∨ a_{k} vyplýva, že existuje i také, že p ≤ a_{i}. Dôkaz. Nech p ≤ ⋁_{i} a_{i}. Potom p = p ∧ (⋁_{i} a_{i}) = ⋁_{i} p ∧ a_{i}. Z ireducibility prvku p teraz vyplýva, že existuje i také, že p = p ∧ a_{i}, čiže p ≤ a_{i}. □

Prijmime teraz všeobecný a trvalý predpoklad o tom, že sa budeme zaoberať len usporiadanými množinami spĺňajúcimi podmienku:

(F) Medzi ľubovoľnými dvoma prvkami je každý reťazec konečný.

(Všetky množiny kombinatorického pôvodu túto podmienku splňajú.)

Z tohto predpokladu nám hneď vyplýva, že element zväzu s 0 má rozklad na ireducibilné prvky, a teda aj iredudantný rozklad. Ak {p_{1}, p_{2}, … } je nejaká množina atómov, tak p_{1} < p_{1} ∨ p_{2} < p_{1} ∨ p_{2} ∨ p_{3} tvoria rast[cu postupnosť – to vyplýva z faktu, že atómy sú ireducibilné z lemy. Ak toto aplikujeme na atómy intervalu dostávame, že interval má konečný počet atómov, a teda, indukciou, je aj sám konečný.

Teoréma 10 Nech L je distributívny zväz (spĺňajúci podmienku (F)) a nech P ⊆ L množina jeho nenulových ireducibilných prvkov. Potom každý prvok a má jednoznačný iredundantný rozklad a = p_{1} ∨ p_{2} ∨ … ∨ p_{k} na ireducibilné prvky, čo zapisujeme P (a) = {p_{1}, p_{2}, …, p_{k}}, pričom P (0) = ∅.

Dôkaz. Existencia rozkladu je zrejmá (existuje 0 a platí (F), čo zabezpečuje, že množina všetkých ireducibilných prvkov ≠ 0 pod a ∈ L; potom treba zobrať všetky také). Jednoznačnosť: Nech

a = p_{1} ∨ p_{2} ∨ … ∨ p_{k} = q_{1} ∨ q_{2} ∨ … ∨ q_{ℓ}

sú dva jednoznačné rozklady. Pre každé p_{i} máme p_{i} ≤ q_{1} ∨ q_{2} ∨ … ∨ q_{ℓ}, odtiaľ p_{i} ≤ q_{j} pre nejaké j. Keďže ireducibilné prvky sú neporovnateľné, dostávame p_{i} = q_{j}. Zopakovaním tejto úvahy potrebný počet krát dostávame, že k ≤ ℓ a analogicky aj ℓ ≤ k. Teda ℓ = k a možiny {p_{1}, p_{2}, …, p_{k}} a {q_{1}, q_{2}, …, q_{ℓ}} sú totožné. □

Podmožina I usporiadanej množiny P je ideál, ak pre ∀x, y : x ∈ I & y ≤ x ⟹ y ∈ I. Hlavný ideál je ideál tvaru {x ∈ P; x ≤ a}, (a môže byť aj mimo množiny P, z nejakej nadmnožiny).

Zjednotenie aj prienik ideálov sú ideály. Teda systém I(P) všetkých ideálov množiny P tvorí podzväz zväzu P(P). Teda I(P) je distrinutívny zväz. V ňom 0 a hlavné ideály sú očividne iredicibilné prvky. Iný dôležitý podzväz je zväz konečných hlavných ideálov I_{f}(P). Teraz ukážeme, že každý distributívny zväz spĺňajúci podmienku (F) je tohto tvaru.

Teoréma 11 Nech L je distributívny zväz s 0 (spĺňajúci (F)) a nech P je množina všetkých jeho iredibilných prvkov ≠ 0. Potom L ≅ I_{f}(P) a izomorfizmus je daný vzťahom φ : a ↦ I(a) = {x ∈ P; x ≤ a}, a ∈ L. Obrátene zväz I_{f}(P) je distributívny a množina jeho ireducibilných prvkov je izomorfná s P. Ak L je konečný, tak L ≅ I(P).

Dôkaz. Keďže každý prvok zväzu L je určený ireducibilnými prvkami, ktoré majorizuje, zobrazenie φ : L → I_{f}(P) je injektívne. Na dôkaz surjektívnosti stačí ukázať, že každý konečný ideál je hlavný. Nech I = {p_{1}, p_{2}, …, p_{r}. Nech b = p_{1} ∨ p_{2} ∨ …, p_{r}. Potom b ∈ L. Uvažujme hlavný ideál I(b). Zrejme I ⊆ I(b).

Obrátene, nech p ∈ I(B). Je to ireducibilný prvok a p ≤ b = p_{1}∨p_{2}∨…∨p_{r}. Z lemy vyplýva, že p = p_{i} ∈ I. Teda I(B) ⊆ I, čiže I = I(b). Teda každý ideál je hlavný, odkiaľ vyplýva, že φ je bijekcia.

Ak a ≤ b, a, b ∈ L, tak I(a) ⊆ I(B). Obrátene I(a) ⊆ I(b) implikuje a = supI(a) ≤ supI(b) = b (???) izomorfizmus a teda izomorfizmus zväzov. □

Dôsledok Dva distributívne zväzy sú izomorfné, ak sú izomorfné usporiadané množiny ich ireducibilných prvkov.

Poznámka: Analogickú konštrukciu možno urobiť pomocou ∧-ireducibilných prvkov a duálneho pojmu filtra. Keďže výsledky musia byť izomorfné, dostávame, že usporiadaná množina ∧-ireducibilných prvkov musí byť v distributívnom zväze izomorfná s usporiadanou množinou ∨-ireducibilných prvkov.

V teoréme 11 sme zistili, že distributívny zväz L s 0 je izomorfný s I_{f}(P), kde P je množina jeho ireducibilných prvkov. Keďže usporiadanie v I_{f}(P) je obyčajná inklúzia, dostávame, že každý distributívny zväz (s podmienkou (F), ako obyčajne) je izomorfný s podzväzom booleovského podzväzu P(X). Keďže P(X) je súčin reťazcov, dokázali sme

Teoréma 12 Každý distributívny zväz s 0 je izomorfný s nejakým podzväzom booleovksého zväzu P(X), a teda aj s podzväzom súčinu reťazcov. Obrátene, každý podzväz súčinu reťazcov je distributívny. □

Charakterizačná teoréma 12, kladie takúto prirodzenú otázku: Koľko je pre daný distributívny zväz L nevyhnutné zobrať reťazcov C_{i} na to, aby L bol podzväzom súčinu ∏_{i} C_{i}?

Budeme predpokladať, že C_{i} = {0 < 1 < ⋯ < c_{i}}. Vnorenie L → ∏_{i=1}^{d} C_{i} nazývame kódovaním zväzu, číslo d dimenziou zväzu. Booleovský zväz P(X) má kódovanie P(X) → {0, 1}^{X} v súčine |X| reťazcov. Je možné tento počet znížiť za cenu predĺženie reťazcov? Z nasledujúcej teorémy vyplynie, že v tomto prípade nie.

Teoréma 13 Nech L je distributívny zväz s 0 a nech P je usporiadaná množina jeho nenulových ireducibilných prvkov. Nech P = ⨄_{i} P_{i} je ľubovoľný rozklad usporiadanej množiny P na reťazce. Položme C_{i} = {0}∪P_{i}, pre všetky i. Potom existuje izomorfizmus φ : L → ∏_{i} C_{i} na podzväz zväzu ∏_{i} C_{i}.

Dôkaz. Pre ľubovoľné x ∈ L a index i položme

x_{i} = sup{z ∈ C_{i}; z ≤ x}.

Na množine indexov zavedieme úplné usporiadanie a položíme

φ : L → ∏_{i} C_{i},
x ↦ (x_{i})_{i}.

(Poznamenávame, že pre skoro všetky indexy (okrem konečného počtu) je x_{i} = 0. To vyplýva z podiemky (F), ktorá implikuje, že interval distributívneho zväzu má iba konečne veľa atómov a teda je konečný.)

Zobrazenie φ je injektívne, lebo keby φ(x) = φ(y), tak x_{i} = y_{i} pre všetky i, a teda I(x) = I(y), odkiaľ x = y.

Okrem toho, podľa lemy o ireducibilných prvkoch máme (x ∨ y)_{i} = sup{z ∈ C_{i}; z ≤ x ∨ y} = sup{z ∈ C_{i}; z ≤ x alebo z ≤ y} = x_{i} ∨ y_{i}. Podobne ∧. □

Keďže podľa teorémy 13, každý rozklad množiny P indukuje kódovanie, problém dimenzie usporiadanej množiny sa redukuje na čisto kombinatorickú úlohu nájsť pre ľubovoľnú usporiadanú množinu P rozklad na minimálny počet d(P) reťazcov. Číslo d(P) sa nazýva Dilworthovým číslom usporiadanej množiny. Je zrejmé, že

d(P) ≥ min_{A je antireťazec} |A|.

V skutočnosti platí rovnosť – to je jeden z fundamentálnych výsledkov kombinatoriky. Príklad d(P({1, 2, …, n})) = n, s využitím vyššie uvedenej nerovnosti.

Teoréma 14 (Dilworth, 1950) Nech P je konečná usporiadaná množina. Potom minimálny počet reťazcov, ktorých zjednotením je P sa rovná maximálnej mohutnosti antireťazca v P.

Dôkaz. Ostáva nám dokázať, že ak v P existuje antireťazec mohutnosti n, tak P sa dá pokryť n reťazcacmi. Maximálnu mohutnosť antireťazca nazveme šírkou usporiadanej množiny P.

Budeme postupovaťindukciou vzhľadom na |P |. Ak |P | = 1, tak výsledok je triviálny. Predpokladajme, že trvdenie platí pre |P | < k a uvažujme množinu |P | = k. Môžeme predpokldať, že šírka n množiny P je > 1.

Zvoľme nejaký maximálny prvok x ∈ P a k nemu zoberme minimálny prvok y taký, že y ≤ x. (Kedže P je konečná, toto sa vždy dá.) Nech Q = P − {x, y} s indukovaným usporiadaním. Ak šírka množiny Q je menšia ako n, tak podľa indukčného predpokladu sa Q dá rozložiť na menej ako n reťazcov, čo spolu s reťazcom {x, y} vytvára rozklad na (nanajvýš) n reťazcov. Takže môžeme prepokladať, že Q má šírku n. Odtiaľ vyplýva, že y < x.

V tejto situácii si vyberieme antireťazec A = {a_{1}, a_{2}, …, a_{n}}. Nech H = {z ∈ P; ∃i : z ≥ a_{i}} (horná množina) a nech D = {z ∈ P; ∃i : z ≤ a_{i}}. Potom H ∪ D = P (inak by existoval širší antireťazec), D ∩ D = A (očividné) a keďže odtránením {x, y} z P sa šírka nezúžila, máme x ∈ H − D, zatiaľ čo y ∈ D − H. Podľa indučného predpokladu existujú rozklady na H = C′_{1} ∪ C′_{2} ⋯ ∪ C′_{n} a D = C′′_{1} ∪ C′′_{2} ⋯ ∪ C′′_{n}. Rozklady možeme očíslovať tak, že a_{i} ∈ C_{i}′ ∩ C′′_{i} pre i = 1, 2, …, n. Potom C_{i} = C_{i}′ ∪ C′′_{i} je reťazec a požadovaný rozklad je P = C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{n}. □

Dôsledok Ak L je konečný distributívny zväz a P je jeho množina nenulových ireducibilných prvkov, tak dim(L) = d(P).

Teraz prejdeme k ďalšiemu aspektu distributívnosti – k poriadkovej (rangovej) funkcii. Poriadková (rangová) funckia na zväze L je funkcia r : X → ℕ_{0} spĺňajúca podmienky

1. r(0) = 0,

2. ak a ⋖ b, tak r(b) = r(a) + 1.

1.4 Modulárne a polomodulárne zväzy

Kapitola 2

Matroidy

2.1 Matroidové algoritmy

Kapitola 3

Kombinatorické konfigurácie

3.1 Konfigurácie 3.2 Zapĺňanie priehradok a urnové schémy 3.3 Latinské štvorce 3.4 Ortogonalita latinských štvorcov 3.5 (v, k, λ)-konfigurácie

Daná je množina X = {x_{1}, x_{2}, …, x_{v}}. Systém X_{1}, X_{2}, …, X_{v} jej podmonožín množiny X tvorí (v, k, λ)-konfiguráciu, ak

1. |X_{i}| = k pre všetky i,

2. |X_{i} ∩ X_{j}| = λ pre všetky i ≠ j,

3. 0 < λ < k < v − 1.

Množiny X_{i} sa nazývajú bloky. Matica incidencie (v, k, λ)-konfigurácie je 0, 1-matica definovaná nasledovne

A = (a_{ij}), i, j = 1, 2, …, v,
a_{ij} = \begin{cases}1 & x_{j} ∈ X_{i}, \\ 0 & inak. \end{cases}

Označme I jednotkovú maticu rádu v, J maticu pozostávajúcu zo samých jednotiek.

KAPITOLA 3. KOMBINATORICKÉ KONFIGURÁCIE 19

1. Pretože |X_{i}| = k je ∑_{j=1}^{v} a_{ij} = k, odtiaľ AJ = kJ.

2. Keďže

c_{ij} = ∑_{q=1}^{v}a_{iq}a_{jq} = |X_{i} ∩ X_{j}| = \begin{cases}k & i = j \\ λ & i ≠ j \end{cases} ,

AA^{T} = (\begin{matrix}k & λ & … & λ \\ λ & k & … & λ \\ ⋮ & & ... & ⋮ \\ λ & λ & … & k \end{matrix}) = λJ + (k − λ)I

3. Matica A je regulárna, lebo

det(AA^{T}) = det(A)^{2}

= |\begin{matrix}k & λ & … & λ \\ λ & k & … & λ \\ ⋮ & & ... & ⋮ \\ λ & λ & … & k \end{matrix}|

= |\begin{matrix}k & λ − k & λ − k & … & λ − k \\ λ & k − λ & 0 & … & 0 \\ ⋮ & 0 & k − λ & ... & ⋮ \\ λ & ⋮ & ... & ... & 0 \\ λ & 0 & … & 0 & k − λ \end{matrix}|

= |\begin{matrix}λ(v − 1) + k & 0 & … & 0 & 0 \\ λ & k − λ & ... & ⋮ & 0 \\ ⋮ & 0 & ... & 0 & ⋮ \\ λ & ⋮ & ... & k − λ & 0 \\ λ & 0 & … & 0 & k − λ \end{matrix}|

= [k + λ(v − 1)](k − λ)^{v−1}

4. Pre každú (v, k, λ)-konfiguráciu platí

k(k − 1) = λ(v − 1).

Vychádzame z rovnosti AA^{T} = λJ + (k − λ)I, potom

AA^{T} J = λJ^{2} + (k − λ)J = λvJ + (k − λ)J = (k + λ(v − 1))J.

Pretože 0 < λ < k je matica A podľa predchádzajúcej vlastnosti regulárna a platí

A^{−1}J = \frac{1}{k} J.

Z toho dostávame

A^{T} J = (k + λ(v − 1))A^{−1}J = \frac{k + λ(v − 1)}{k} J,

trasponovaním

(A^{T} J)^{T} = \frac{k + λ(v − 1)}{k} J^{T} ,
JA = \frac{k + λ(v − 1)}{k} J,
JAJ = \frac{v}{k} (k + λ(v − 1))J.

Vieme, že AJ = kJ, čiže JAJ = kJ^{2} = vkJ, porovnaním dostaneme

vkJ = \frac{v}{k} (k + λ(v − 1))J,
k = \frac{k + λ(v − 1)}{k} ,
k^{2} − k = (λ(v − 1)),
k(k − 1) = (λ(v − 1)).

3.6 Uplné diferenčné množiny

3.7 Hadamardove matice a konfigurácie

Štvorcová matica H rádu n sa nazýva Hadamardova, ak

1. a_{ij} = ±1

2. HH^{T} = nI (I je jednotková matica)

Jednoduché dôsledky definície: Ak H_{i}, H_{j} sú riadkové vektory Hadamardovej matice, tak pre ich skalárny súčin platí:

(H_{i}, H_{j}) = \begin{cases}n & i = j, \\ 0 & i ≠ j. \end{cases}

Čiže riadky sú na seba kolmé. Každá Hadamardova matica je regulárna, lebo det(H)^{2} = det(HH^{T}) = n^{n}. Navyše Hadarmadove matice sú zrejme normálne, lebo

H^{T} H = H^{−1}HH^{T} H = H^{−1}nIH = nIH^{−1}H = nI = HH^{T} .

Ak H je Hadamardova, tak aj (−1)H je Hadamardova. Preusporiadním riadkov a stĺpcov dostaneme opäť Hadamardovu maticu. Rovnako môžeme vynásobiť riadok alebo stĺpec (−1). Naozaj, je zrejmé, že vlastnosť

(H_{i}, H_{j}) = \begin{cases}n & i = j, \\ 0 & i ≠ j, \end{cases}

je ekvivalentná podmienke

∑_{k=0}^{n}h_{ik}h_{jk} \begin{cases}n & i = j, \\ 0 & i ≠ j. \end{cases}

A táto rovnosť je invariantná voči uvedeným operáciám. Preto možno každú Hadamardovu maticu uviesť do tvaru, v ktorom prvý riadok a prvý stĺpec obsahujú kladné jednotky (normalizované).

Veta 15 Ak n je rád Hadamardovej matice, tak n = 1, 2 alebo n ≡ 0 (mod 4).

Dôkaz. Pre n = 1, 2 majú normalizované Hadamardove matice tvar:

(1)  (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix})

Nech je daná Hadamardova matica rádu n ≥ 3, prepokladajmu ju normalizovanú. Stĺpce prvých troch riadkov tejto matice majú jeden z nasledujúcich tvarov

(\begin{matrix}1 \\ 1 \\ 1 \end{matrix})  (\begin{matrix}1 \\ 1 \\ −1 \end{matrix})  (\begin{matrix}1 \\ −1 \\ 1 \end{matrix})  (\begin{matrix}1 \\ −1 \\ −1 \end{matrix}) .

Nech počet stĺpcov prvé typu je x, druhého y, tretieho z a štvrtého w. Pretože ich je spolu n, platí x + y + z + w = n. Nech v množine I_{j} sú tie indexy stĺpcov našej matice, ktorého sú typu j (j = 1, 2, 3, 4). Teda máme |I_{1}| = x, |I_{2}| = y, |I_{3}| = z, |I_{4}| = w. Pretože riadky H_{1}, H_{2} sú na seba kolmé, máme h_{11}h_{21} + h_{12}h_{22} + ⋯ + h_{1n}h_{2n} = 0.

Ak i ∈ I_{1}, tak h_{1i} · h_{2i} = 1 · 1 = 1,
i ∈ I_{2}, tak h_{1i} · h_{2i} = 1 · 1 = 1,
i ∈ I_{3}, tak h_{1i} · h_{2i} = 1 · (−1) = −1,
i ∈ I_{4}, tak h_{1i} · h_{2i} = 1 · (−1) = 1.

Odtiaľ 0 = (H_{1}, H_{2}) = ∑_{i=1}^{n} h_{1i}h_{2i} = ∑_{j=1}^{4} ∑_{i∈I_{j}} h_{1i}2i = x + y − z − w. Analogicky z ortogonality H_{1} a H_{3} dostávame x − y + z − w = 0, a ortogonality H_{2} a H_{3} dostávame x − y − z + w = 0.

Máme teda systém rovníc

x + y + z + w = n,
x + y − z − w = 0,
x − y + z − w = 0,
x − y − z + w = 0.

Vyriešením dostávame x = y = z = w = n/4. Keďže x, y, z, w sú celé čísla, je n ≡ 0 (mod 4). □

Kroneckerovým súčinom matíc A ⊗ B matíc typu n × n a m × m rozumieme maticu typu mn × mn typu

(\begin{matrix}a_{11}B & a_{12}B & ⋯ & a_{1n}B \\ a_{21}B & a_{22}B & ⋯ & a_{2n}B \\ ⋮ & ⋮ & ... & ⋮ \\ a_{n1}B & a_{n2}B & ⋯ & a_{nn}B \end{matrix}) .

Ľahko sa možno presvedčiť, že tatko definovaný súčin má nasledovné tri vlastnosti:

(A ⊗ B)^{T} = A^{T} ⊗ B^{T}
(A + B) ⊗ C = A ⊗ C + B ⊗ C
(AB) ⊗ (CD) = (A ⊗ C)(B ⊗ D)

Kroneckerov súčin Hadamardových matíc je opäť Hadamarodva matica. Naozaj:

(H⊗H′)(H⊗H′)^{T} = (H⊗H′)(H^{T} ⊗H^{′T}) = HH^{T} ⊗H′H^{′T} = nI_{n}⊗mI_{m} = mnI_{mn}.

Veta 16 Pre n = 2^{k} existuje Hadamardova matica.

Dôkaz. Zoberme maticu

H_{2} = (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix})

Definujme

H_{2^{k}} = \underbrace{H_{2} ⊗ H_{2} ⊗ ⋯ ⊗ H_{2}}_{k-krát}.

Podľa vyššie popísaných vlastností je to Hadamardova matica rádu 2^{k}. □

Veta 17 Normalizovaná Hadamardova matica rádu m = 4μ je ekvivaletná (v, k, λ)-konfigurácii s parametrami

v = 4μ − 1, k = 2μ − 1, λ = μ − 1.

Dôkaz. Z normalizovanej Hadamardovej matice vyškrtneme prvý riadok a prvý stĺpec a −1 zmeníme na 0. Keďže ľubovoľný riadok rôzny od prvého je naň komý, tak platí ∑_{i=1}^{n} h_{1i}h_{ji} = 0 (j > 1), ale h_{1i} = 1 pre všetky i, preto ∑_{i=1}^{n} h_{j}i = 0, čiže počet kladných jednotiek sa rovná počtu záporných jednotiek, teda počet kladných (záporných) jednotiek je 2μ.

Pretože pre i ≠ j, i, j > 1 sú riadky na seba kolmé a každý má po 2μ kladných jednotiek, majú na (práve) μ miestach kladné jednotky v rovnakých stĺpcoch.

Z toho plynie, že v našej 0, 1-matici rádu 4μ − 1 je súčet riadku rovný 2μ − 1 a dva riadky majú μ − 1 jednotiek v rovnakých stĺpoch. To svedčí o tom, že naša 0, 1-matica je maticou incidencie (v, kλ)-konfigurácie s vyššie udanými parametrami. Táto konfigurácia na nazýva Hadamardova konfigurácia. V obrátenom postupe možno každej Hadamardovej konfigurácii priradiť normalizovanú Hadamardovu maticu rádu 4μ. □

3.8 Konečné projektívne roviny

Konečnou projektívnou rovinou rádu n sa rozumie (v, k, λ)-konfigurácia s parametrami

v = n^{2} + n + 1, k = n + 1, λ = 1.

Bloky X_{i}, i = 1, 2, …, n^{2} +n+1 sa nazývajú priamkami a prvky blokov bodmi. Vzťah x_{i} ∈ X_{j} znamená, že bod x_{i} leží na priamke X_{j} a vzťah x_{i} ∈ X_{j} ∩ X_{k}, že priamky X_{j}, X_{k} sa pretínajú v bode x_{i}. Príklad (v, k, λ)-konfigurácia určená úplnou diferenčnou množinou 1, 2, 4 ⊂ ℤ_{7} je projektívnou rovinou, ktorú možno nasledovne znázorniť.

Čo sa týka existencie konečných projektívnych rovín, tak platí veta (dôsledok vety Buck-Ryser).

Veta 18 Na existenciu konečnej projektívnej roviny rádu n je nutné, aby pri n ≡ 1, 2 (mod 4) existovali celé čísla a, b spĺňajúce rovnosť n = a^{2} + b^{2}.

Z tejto vety vyplýva neexistencia konečných projektívnych rovín rádov napr. 6, 14, 21, 22.

KAPITOLA 3. KOMBINATORICKÉ KONFIGURÁCIE 24

3.9 Ortogonálne latinské štvorce a projektívne

roviny 3.10 Blokové konfigurácie: (b, v, r, k, λ)-konfigurácie 3.11 Steinerove trojice