szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 sty 2019, o 21:02 
Użytkownik
Avatar użytkownika

Posty: 3680
Lokalizacja: blisko
Chciałem zająć się w tym temacie macierzą zero-jedynkową, na którą działa grupa permutacji wierszy i kolumn. Będziemy liczyć, ile jest niezależnych ze względu na działanie grupy ustawień zer i jedynek w macierzy.

Celem tego wykładu jest przede wszystkim pokazanie jak wygląda mnożenie kartezjańskie cykli,
chcę pokazać jak wygląda grupa permutacji i jak liczymy liczbę niezależnych macierzy ze względu na permutacje.

Bierzemy dowolną macierz binarną, i przestawiamy w niej wiersze i kolumny (działamy na nią grupą permutacji wierszy i kolumn).

Pokażemy jeszcze, jak mnoży się indeksy cyklowe za pomocą iloczynu kartezjańskiego, podam wzór.

Grupa permutacji jako taka jest iloczynem kartezjańskim grupy permutacji wierszy i grupy permutacji kolumn. Policzymy i wypiszemy jej elementy.

G=S_{n} \times S_{m}

n - liczba wierszy, m - liczba kolumn.

|G|=n! \cdot m!

Żeby uprościć rozważania odwołamy się do konkretnego przykładu.

Prześledzimy na przykładzie macierzy 2 \times 3:

Dwa wiersze i trzy kolumny.

G=S_{2} \times S_{3}.

Wypiszmy elementy obu grup:

S_{2}=\left\{ \left( w_{1} \right) \left( w_{2} \right) , \left( w_{1}w_{2} \right) \right\}

S_{3}=\left\{ \left( k_{1} \right) \left( k_{2} \right) \left( k_{3} \right) , \left( k_{1}k_{2} \right) \left( k_{3} \right) , \left( k_{1}k_{3} \right) \left( k_{2} \right) , \left( k_{2}k_{3} \right) \left( k_{1} \right) , \left( k_{1}k_{2}k_{3} \right), \left( k_{1}k_{3}k_{2} \right) \right\}.

Zapiszmy teraz permutacje za pomocą indeksów cyklowych:

I_{S_{2}}=j_{1}^2+j_{2}

I_{S_{3}}=j_{1}^3+3j_{1}j_{2}+2j_{3}.

A teraz zgodnie z oczekiwaniem wymnożymy te indeksy cyklowe.

Najpierw podam wzór na: "rozdzielność iloczynu kartezjańskiego względem dodawania"

\left( j_{k_{1}}^{n_{1}}+j_{k_{2}}^{n_{2}}\right) \times \left( j_{l_{1}}^{m_{1}}+j_{l_{2}}^{m_{2}}\right)=\left( j_{k_{1}}^{n_{1}} \times j_{l_{1}}^{m_{1}} \right)+ \left( j_{k_{1}}^{n_{1}} \times j_{l_{2}}^{m_{2}} \right)+\left( j_{k_{2}}^{n_{2}} \times j_{l_{1}}^{m_{1}} \right)+\left( j_{k_{2}}^{n_{2}} \times j_{l_{2}}^{m_{2}} \right).

Oczywiście wzór ten można rozszerzyć na dowolną liczbę indeksów.

Napiszmy teraz podobny wzór na iloczyn kartezjański kilku cykli, w naszym przypadku dla dwóch, bo na więcej łatwo rozszerzyć:

niech: a^i,b^j,c^k,d^l cykle

a^i=\underbrace{(1,...,n)(1,...,n)...(1,...,n)}_{i} - łączenie cykli o tej samej długości


\left( a^ib^j\right) \times \left( c^kd^l\right)=\left( a^i \times c^k \right) \left( a^i \times d^l\right)\left( b^j \times c^k\right)\left( b^j \times d^l\right)


j_{n}=(1,2,...,n) - tu chodzi o długość cyklu.

Ważne, abyśmy mieli pojęcie czym jest indeks dolny i górny w zapisie cyklowym.

j_{k}^i - jest to złożenie i cykli o długości k.

Podam teraz najważniejszy wzór na bezpośredni iloczyn kartezjański dwóch grup cyklowych o tej samej długości:

j_{k}^n \times j_{l}^m=j_{\left\langle k,l \right\rangle}^{n \cdot m \cdot \left( k,l \right) }}

gdzie:

\left( k,l \right) =NWD \left( k,l \right),

\left\langle k,l \right\rangle=NWW \left( k,l \right),

j_{k}^1=j_{k}.

Uzbrojeni w powyższe wzory możemy pomnożyć indeksy cyklowe w naszym prostym przykładzie.

I_{G}=I_{S_{2}} \times I_{S_{3}}=\left( j_{1}^2+j_{2}\right) \times \left( j_{1}^3+3j_{1}j_{2}+2j_{3}\right)=

\left( j_{1}^2\right) \times\left( j_{1}^3 \right)+3 \left( j_{1}^2\right) \times\left( j_{1}j_{2} \right)+2\left( j_{1}^2\right) \times\left( j_{3}\right)+\left( j_{2}\right) \times\left( j_{1}^3 \right)+3 \left( j_{2}\right) \times\left( j_{1}j_{2} \right)+2\left( j_{2}\right) \times\left( j_{3}\right).

Zgodnie z ostatnim wzorem:

j_{1}^2 j_{1}^3=j_{1}^6

3 \left( j_{1}^2\right) \times\left( j_{1}j_{2} \right)=3\left( j_{1}^2 \times j_{1} \right)\left( j_{1}^2 \times j_{2} \right)=3\left( j_{1}^2\right)\left( j_{2}^2 \right)

2\left( j_{1}^2\right) \times\left( j_{3}\right)=2\left( j_{3}^2\right)

j_{2}\right \times j_{1}^3 =j_{2}^3

3 \left( j_{2}\right) \times\left( j_{1}j_{2} \right)=3\left( j_{2} \times j_{1} \right) \left( j_{2} \times j_{2} \right)=3\left( j_{2}^1\right)\left( j_{2}^2\right)

2\left( j_{2}\right) \times\left( j_{3}\right)=2j_{6}.

Dodając otrzymamy sumę indeksów cyklowych dla iloczynu kartezjańskiego obu grup, lub jak kto woli już jednej:

I_{G}=j_{1}^6+3\left( j_{1}^2\right)\left( j_{2}^2 \right)+2\left( j_{3}^2\right)+j_{2}^3+3\left( j_{2}^1\right)\left( j_{2}^2\right)+2j_{6}.

Stworzymy teraz na bazie indeksów cyklowych wielomian charakterystyczny, to znaczy przyporządkujmy każdemu indeksowi cyklowemu wielomian na zasadzie:

j_{k}^n  \rightarrow  (1+x^k)^n.

Zatem nasz wielomian będzie wyglądał następująco:

w \left( x \right) =\\= \frac{1}{2} \cdot \frac{1}{6} \left[ \left( 1+x \right) ^6+3 \left( 1+x \right) ^2 \left( 1+x^2 \right) ^2+2 \left( 1+x^3 \right) ^2+ \left( 1+x^2 \right) ^3+3 \left( 1+x^2 \right) \left( 1+x^2 \right) ^2+2 \left( 1+x^6 \right) \right]

lub po uproszczeniu otrzymamy:

w \left( x \right) =x^6+x^5+3x^4+3x^3+3x^2+x+1

Ten wielomian jest wynikiem naszych obliczeń, z tego wielomianu możemy odczytać np., że:

1. jest jedna macierz, w której liczba jedynek wynosi 6;

2. jest jedna macierz, w której liczba jedynek wynosi 5;

3. są trzy macierze, w których liczba jedynek wynosi 4;

itd...

Oczywiście z dokładnością do permutacji wierszy i kolumn.

Na poniższym rysunku widać istotnie różne macierze ze względu na działanie naszej grupy permutacji.

Z tą drobną różnicą, że zamiast jedynek zapisanych w poszczególnych komórkach dałem czerwone kwadraciki, natomiast zera symbolizują białe kwadraciki.

Doświadczenie zgadza się z naszymi obliczeniami, ponieważ dla jednej jedynki i pięciu zer mamy tylko jedną macierz, a dla 2 i 3 jedynek mamy po trzy niezależne macierze.

Obrazek

Jest jak widać jedna, trzy i trzy możliwości, natomiast dla czterech pięciu i sześciu jedynek (u nas czerwonych kwadratów) sytuacja staje się symetryczna.

Jak widać jest to dość pracochłonne i mozolne zliczanie, efektywniej pewnie byłoby napisać jakiś programik komputerowy dla zliczania w przypadku większej ilości wierszy i kolumn, ilość obliczeń wzrasta lawinowo.

Dziękuję za uwagę...
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rząd macierzy w zależności od parametru - zadanie 4  Akiro  1
 Wyznacznik macierzy metodą laplace'a w C  anka8787  2
 [Scilab]-zerowanie macierzy  misia12345  0
 Mnożenie logarytmów - zadanie 12  Dovv90  10
 Kongruencja macierzy  binaj  0
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl