Filtr seznamu úloh?
Škály
Štítky
«
«
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í.