Grupa matic s 0 a 1

Ř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í.