Filtr seznamu úloh?

Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.

Škály

Obtížnost

Štítky

Typ úlohy
«
«
«

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í.
Obtížnost: Středně těžká úloha
Úloha řešená úvahou
Úloha na dokazování, ověřování
	Zaslat komentář k úloze