Grupa matic s 0 a 1
Úloha číslo: 4557
Čtvercová matice \(\boldsymbol A\in \{0{,}1\}^{n\times n}\) se nazývá permutační, pokud pro každé \(i\in \{1,\ldots, n\}\) platí \(\sum\limits_{j=1}^{n} a_{i,j} = 1\) a zároveň pro každé \(j\in \{1,\ldots, n\}\) platí \(\sum\limits_{i=1}^{n} a_{i,j} = 1\).
Vyjádřeno slovy, matice je tvořena pouze čísly 0 a 1 a jejich součet v každém řádku a sloupci je právě 1. Například matice \(\boldsymbol A=\begin{pmatrix} 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 \\ \end{pmatrix}\) je permutační.
Označme \(P_n\) množinu všech permutačních matic řádu \(n\). Rozhodněte, zda pro každé přirozené číslo \(n\) je \((P_n,\cdot)\) grupou, kde \(\cdot\) označuje obvyklý součin reálných matic.
Řešení
Každá permutační matice má v každém řádku i sloupci právě jednu 1, a ostatní prvky jsou rovny 0.
Nejprve ověříme, že standardní maticový součin je binární operací na množině \(P_n\).
Mějme dvě permutační matice \(\boldsymbol A, \boldsymbol B\) řádu \(n\). Součin \(\boldsymbol{AB}\) je čtvercová matice stejného řádu.
Pro každý řádek matice \(\boldsymbol A\) existuje právě jeden sloupec matice \(\boldsymbol B\) mající 1 na stejných pozicích. Formálně, pokud \(a_{i,j}=1\) potom \(\exists !k: b_{j,k}=1\), protože v \(j\)-tém řádku matice \(\boldsymbol B\) je právě jedna 1 a její sloupcový index je hledané \(k\). Z uvedeného vyplývá, že matice \(\boldsymbol{AB}\) má v každém řádku jednu 1 a jinak samé 0.
Analogický argument lze vyslovit i pro sloupce matice \(\boldsymbol{AB}\), a tudíž je uvedená matice permutační.
Součin permutačních matic je asociativní, protože jde o speciální případ asociativitu součinu reálných matic.
Jednotková matice \(\mathbf I_n\) je neutrální prvek pro maticový součin a je zároveň permutační, protože \(\mathbf I_n\in \{0{,}1\}^{n\times n}\) a řádkové i sloupcové součty má rovny jedné. Jde proto o neutrální prvek \((P_n,\cdot)\).
Ukážeme, že permutační matice řádu \(n\) splňují: \(\boldsymbol A^{-1}=\boldsymbol A^{\mathrm T}\in \{0{,}1\}^{n\times n}\). Pokud \(a_{i,j}=1\), pak \((\boldsymbol {AA}^{\mathrm T})_{i,i}=1\), protože \(i\)-tý sloupec \(\boldsymbol A^{\mathrm T}\) má 1 na stejné pozici. Ostatní sloupce tuto vlastnost nemají, a proto jsou zbývající prvky v \(i\)-tém řádku matice \(\boldsymbol {AA}^{\mathrm T}\) rovny 0. Z uvedeného vyplývá, že \(\boldsymbol {AA}^{\mathrm T}=\mathbf I_n\) a proto jsou permutační matice regulární a inverzní matice k permutačním maticícm jsou také permutační.
Tímto jsme ověřili, že \((P_n,\cdot)\) tvoří grupu.
Odpověď
Struktura \((P_n,\cdot)\) je grupou pro každé přirozené \(n\).Komentář
Každé permutační matici \(\boldsymbol A\) odpovídá permutace \(p\) daná vztahem \(a_{i,j}=1 \Leftrightarrow p(i)=j\). Grupa \((P_n,\cdot)\) je pak izomorfní grupě \((S_n,\circ)\) neboli maticový součin odpovídá skládání permutací.
