Mnożenie macierzy a permutacje

[arek1357]

Podam przykłady, żeby łatwiej zdefiniować o co mi biega:

\(\displaystyle{ \left[\begin{array}{cccc}1&0&0\\0&0&1\\0&1&0\end{array}\right] \cdot \left[\begin{array} {cccc}a&b&c&d\\e&f&g&h\\i&j&k&l\end{array}\right]=\left[\begin{array} {cccc}a&b&c&d\\i&j&k&l\\e&f&g&h\end{array}\right]}\)


\(\displaystyle{ \left[\begin{array} {cccc}a&b&c&d\\e&f&g&h\\i&j&k&l\end{array}\right] \cdot \left[\begin{array}{cccc}0&0&1&0\\0&1&0&0\\1&0&0&0\\0&0&0&1\end{array}\right]=\left[\begin{array} {cccc}c&b&a&d\\g&f&e&h\\k&j&i&l\end{array}\right]}\)

Jak widać mnożenie macierzy dowolnej przez macierze zero jedynkowe ( z prawej lub z lewej) powodują permutację odpowiednio wierszy i kolumn tejże macierzy.

I teraz zadanie wyznaczyć wszystkie macierze (zero jedynkowe) z lewej i z prawej ,
które wyznaczają grupy permutacji oczywiście chodzi mi o dowolną macierz:

\(\displaystyle{ [a_{i,j}]_{w \times k}}\)

\(\displaystyle{ S_{k}}\) i \(\displaystyle{ S_{w}}\)

czyli grupę permutacji wierszy i grupę permutacji kolumn..

No i czy zawsze są takowe macierze odpowiadające każdej permutacji...

Jeśli by tak było macierze też powinny tworzyć grupę...
W sumie sam znalazłem już rozwiązanie ale może jeszcze ktoś pokaże swoje...

Myślałem, że jest to trudne zadanie ale jest ono niestety banalne...

[szw1710]

Bo jest banalne, albowiem grupę permutacji generują transpozycje. Czyli chodzi o takie macierze, w których dwa ustalone wiersze (odpowiednio dwie ustalone kolumny) są przestawione.

Mało tego: pierwszy wiersz można ustawić na \(\displaystyle{ n}\) miejscach, drugi już na \(\displaystyle{ n-1}\) miejscach itd., więc w ten sposób wygenerujemy wszystkie macierze permutacji przez... właśnie permutacje wierszy (odpowiednio kolumn).

Macierze permutacji są punktami ekstremalnymi w zbiorze macierzy podwójnie stochastycznych. Te są ważne w teorii majoryzacji (Marshall, Olkin, Inequalities: Theory of majorization and its applications). Stąd prosta droga np. do statystyki. Na majoryzacji oparty jest współczynnik koncentracji Giniego i jego interpretacja.

Oznacza to, że zbiór macierzy podwójnie stochastycznych jest otoczką wypukłą zbioru macierzy permutacji.

[arek1357]

Dokładnie tak jest , z początku wydawało mi się trudne lecz szybciutko zauważyłem że to banał, ale stwierdziłem, że warto to zostawić na forum w celu dydaktycznym.
W sumie nawet tym sposobem w zbiorze macierzy:\(\displaystyle{ n \times n}\) wygenerowała się fajna podgrupa...