Doplňování systému sudých podmnožin se sudými průniky

Úkol: Dokažte, že každý systém $ B$ podmnožin množiny $ A$ z předchozího příkladu lze rozšířit na systém $ B'$ splňující podmínky příkladu 3.6, jehož mohutnost je $ 2^{\lfloor\frac{n}{2}\rfloor}$.


Řešení: Označme $ C$ matici, která jako řádky obsahuje charakteristické vektory množin systému $ B$; definice charakteristického vektoru množiny je uvedena v řešení příkladu 3.6. Nejprve ukážeme, že bez újmy na obecnosti lze předpokládat, že libovolný vektor z lineárního obalu řádků matice $ C$ je zároveň jejím řádkem. Nechť tomu tak není a $ \vec{w}$ je vektor, který není řádkem matice $ C$ a přitom zároveň náleží do lineárního obalu jejích řádků. Tento vektor leží v jádru matice zobrazení odpovídajícího matici $ C$ (viz příklad 3.6). Tedy jeho složkový součin7 s libovolným z řádků $ C$ je nula, a protože je prvkem lineárního obalu řádků matice $ C$, je jeho složkový součin se sebou samým taktéž nula (pracujeme stále nad {\bb Z}$ _2$). Tedy počet prvků množiny odpovídající vektoru $ \vec{w}$ je sudý a velikost průniku s libovolnou množinou ze systému $ B$ je taktéž sudá. Tedy množinu odpovídající vektoru $ \vec{w}$ lze do systému přidat a takto lze postupovat, dokud všechny prvky lineárního obalu řádků matice $ C$ nejsou přímo jejími řádky.

Nechť tedy všechny prvky lineárního obalu řádků matice $ C$ jsou jejími řádky. Pokud je hodnost této matice $ \lfloor\frac{n}{2}\rfloor$, odpovídající systém množin má $ 2^{\lfloor\frac{n}{2}\rfloor}$ prvků. Nechť je tedy hodnost této matice menší než $ \lfloor\frac{n}{2}\rfloor$. Ukážeme, že existuje množina, kterou lze do tohoto systému přidat tak, aby byly nadále splněny všechny podmínky, které na něj klademe. K matici $ C$ přidejme řádek obsahující samé jedničky. Hodnost matice $ C$ tím vzroste nejvýše o jedna a tedy bude nejvýše $ \lfloor\frac{n}{2}\rfloor$. Jádro zobrazení odpovídajícího takto upravené matici nadále obsahuje charakteristické vektory všech množin uvažovaného systému a dle věty o dimenzi jádra a obrazu zobrazení je jeho dimenze alespoň $ \lceil\frac{n}{2}\rceil$; obsahuje tedy alespoň jeden nenulový vektor $ \vec{w}$, který není charakteristickým vektorem žádné z množin systému $ B$ (lineární obal charakteristických vektorů tohoto systému má dimenzi menší než $ \lfloor\frac{n}{2}\rfloor$). Množinu odpovídající vektoru $ \vec{w}$ lze k systému $ B$ přidat, aniž bychom porušili některou z podmínek, které má systém $ B$ splňovat. Takto rozšířený systém množin lze pak ,,lineárně uzavřít'' postupem popsaným v minulém odstavci, a tento postup případně několikrát zopakovat, dokud hodnost matice $ C$ nebude $ \lfloor\frac{n}{2}\rfloor$ a odpovídající systém množin nebude mít $ 2^{\lfloor\frac{n}{2}\rfloor}$ prvků.

$ \ast$DK$ \ast$