Fisherova nerovnost

Úkol: Nechť $ B$ je systém $ k$-prvkových podmnožin $ n$-prvkové množiny $ A$ ($ 2\le k<n$). Nechť každá dvouprvková podmnožina $ A$ je obsažena v právě $ \lambda\ge 1$ množinách systému $ B$. Označme $ b=\vert B\vert$ a $ E$ matici typu $ n\times b$ takovou, že $ E_{ij}=1$ právě tehdy když $ i$-tý prvek množiny $ A$ je obsažen v $ j$-té množině systému $ B$, jinak $ E_{ij}=0$ (tedy sloupce $ E$ popisují jednotlivé množiny systému). Ukažte, že $ EE^T=\left(\frac{kb}{n}-\lambda\right)\mathbbm{1}+ \lambda J$, kde $ J$ je matice samých jedniček. Odtud dokažte, že $ b\ge n$; tato nerovnost se nazývá Fisherova nerovnost. Návod: užijte dvojí počítání.


Řešení: Dle definice matice $ E$ je hodnota prvku matice $ EE^T$ o souřadnicích $ (i,j)$ ($ i\not=j$) počet množin systému $ B$, ve kterých je $ i$-tý a $ j$-tý prvek množiny $ A$ zároveň. Jeho hodnota je tedy $ \lambda$. Součet kvadrátů prvků v $ i$-tém řádku matice $ E$ (označme jej $ n_i$) je $ i$-tý prvek na diagonále $ EE^T$ a udává počet množin systému $ B$, které obsahují $ i$-tý prvek množiny $ A$.

Každý prvek množiny $ A$ je obsažen v $ n-1$ různých dvojicích prvků (množiny $ A$). Každá množina systému $ B$, která tento prvek obsahuje, obsahuje $ k-1$ různých dvojic s tímto prvkem. Zafixujme si jeden prvek $ a_i\in A$. Spočítejme, kolikrát se v množinách $ B$ vyskytuje nějaká dvojice s $ a_i$. Na jednu stranu víme, že každá dvojice z $ A$ se v systému $ B$ vyskytuje právě $ \lambda$-krát. Dvojic v $ A$ obsahujících $ a_i$ je $ n-1$, tedy v $ B$ napočítáme takových dvojic $ \lambda(n-1)$. Na druhou stranu je v každé množině $ B$, která obsahuje $ a_i$, celkem $ k-1$ dvojic s $ a_i$. Tedy je v množinách $ B$ celkem $ n_i(k-1)$ dvojic s $ a_i$. Určili jsme takto $ n_i=\lambda(n-1)/(k-1)$ pomocí postupu zvaného dvojí počítání.

Matici $ EE^T$ lze tedy zapsat ve tvaru $ (\lambda\frac{n-1}{k-1}-\lambda)\mathbbm{1}+\lambda J$. Podle příkladu 9.3 má taková matice jednonásobné vlastní číslo $ \lambda\frac{n-1}{k-1}-\lambda+n\lambda=
\lambda(n-1)\frac{k}{k-1}\not=0$ a $ (n-1)$-násobné vlastní číslo $ \lambda\frac{n-1}{k-1}-\lambda\not=0$ (nenulovost plyne z $ n>k$). Matice $ EE^T$ je tedy regulární, a tedy hodnost matice $ E$ musí být alespoň $ n$ ( $ h(AB)\le\min\{h(A),h(B)\}$). Potom ale nutně musí platit $ b\ge n$.

Jiným dvojím počítáním zjistíme, že každý prvek $ A$ je obsažen v  $ \frac{kb}{n}$ množinách systému $ B$. Označme tento neznámý počet opět $ n_i$ (víme ale již, že $ n_i$ je pro všechny prvky, tedy $ i$, stejné) a vytvořme množinu $ BB$ sjednocením všech množin systému $ B$, přičemž prvky $ BB$ se opakují, podle počtu výskytu v množinách z $ B$. Počet prvků $ BB$ je roven jednak $ n_in$ (každý prvek se $ n_i$-krát opakuje), ale taky $ kb$ ($ B$ obsahuje $ b$ množin po $ k$ prvcích). Srovnáním těchto výrazů máme $ n_i=kb/n$. Tedy vskutku platí také vyjádření $ EE^T=\left(\frac{kb}{n}-\lambda\right)\mathbbm{1}+ \lambda J$.

$ \ast$DK$ \ast$