Przeskocz do treści

Delta mi!

Loading

Konkurs prac uczniowskich

O prawdopodobieństwie, wyznacznikach i pokryciach cyklowych

Wojciech Nadara

o artykule ...

  • Publikacja w Delcie: marzec 2012
  • Publikacja elektroniczna: 2 marca 2012
  • Autor: Wojciech Nadara
    Afiliacja: XIV LO im. Stanisława Staszica, Warszawa
  • Wersja do druku [application/pdf]: (120 KB)
  • Artykuł jest skrótem pracy uczniowskiej nagrodzonej złotym medalem w XXXIII Konkursie Prac Uczniowskich z Matematyki w 2011 roku (Łódź).

W tym artykule będziemy się zajmowali obliczaniem wyznaczników macierzy w dowolnym skończonym ciele math Będziemy także badali, jakie jest prawdopodobieństwo, że taki wyznacznik dla macierzy z losowo wpisanymi elementami z ciała math jest różny od math oraz jakie jest prawdopodobieństwo, że w losowym grafie skierowanym jest nieparzyście wiele pokryć cyklowych.

Jeżeli mamy daną macierz kwadratową z wpisanymi w nią elementami ciała math to ciężko na pierwszy rzut oka stwierdzić, czy jej wyznacznik jest zerowy, czy nie. Sprawa okazuje się dużo prostsza, gdy mamy do czynienia z macierzą w postaci schodkowej (tzn. z taką, która ma zera poniżej głównej przekątnej). Wyznacznik takiej macierzy jest zerowy wtedy i tylko wtedy, gdy na jej głównej przekątnej znajduje się co najmniej jedno math Aby sprowadzić naszą macierz do postaci schodkowej, użyjemy metody eliminacji Gaussa. Będziemy wykonywać dwa rodzaje operacji. Pierwszym będzie zamiana dwóch wierszy miejscami, a drugim będzie dodanie do ustalonego wiersza innego wiersza pomnożonego przez stałą. Jak wiadomo, operacja drugiego rodzaju nie zmienia wyznacznika macierzy, operacja pierwszego rodzaju natomiast zmienia jego znak, a więc nie zmienia tego, czy wyznacznik jest zerowy, czy nie.

Sprowadzając macierz do postaci schodkowej, najpierw musimy zadbać o to, aby w górnym lewym rogu naszej macierzy znalazł się jakiś niezerowy element. Jeżeli w pierwszej kolumnie są same zera, to przerywamy nasz algorytm, gdyż wyznacznik naszej macierzy na pewno jest równy math W przeciwnym przypadku, jeżeli w górnym lewym rogu jest już niezerowy element, to nic nie robimy, a jeśli nie, to zamieniamy pierwszy wiersz z którymś, w którym w pierwszej kolumnie znajduje się niezerowy element. Następnie musimy zadbać o to, aby w tej kolumnie nie było więcej niezerowych elementów, zatem jeżeli w górnym lewym rogu znajduje się element math a w innym wierszu w pierwszej kolumnie znajduje się element math to musimy do tego wiersza dodać pierwszy wiersz pomnożony przez math Zatem zrobiliśmy już wszystko, co mieliśmy zrobić z pierwszym wierszem i pierwszą kolumną, i dalej ograniczamy się do reszty naszej macierzy, dla której powtarzamy to postępowanie. Kończymy je w momencie, gdy w macierzy, która nam pozostała, w pierwszej kolumnie są same zera (wtedy wyznacznik równa się math) lub gdy szczęśliwie dojdziemy do końca (wtedy wyznacznik jest niezerowy).

Jak ta metoda może nam pomóc w obliczeniu prawdopodobieństwa, że dla kwadratowej macierzy math  rozmiaru math  w której każde pole jest wpisany z równym prawdopodobieństwem jakiś element ciała math jej wyznacznik jest niezerowy? Oznaczmy liczbę elementów ciała math przez math Zastanówmy się najpierw, jakie jest prawdopodobieństwo tego, że będziemy mogli wykonać pierwszą fazę algorytmu, czyli że w pierwszej kolumnie znajdzie się jakiś niezerowy element. Abyśmy nie mogli jej wykonać, w każdym z math pól pierwszej kolumny musi znaleźć się math a znajduje się ono w każdym polu z prawdopodobieństwem math Zatem prawdopodobieństwo tego, że będziemy mogli wykonać pierwszą fazę algorytmu, wynosi math Nietrudno przekonać się o tym, że nie tylko w pierwszej, ale w dowolnej, math-tej fazie algorytmu, rozkład prawdopodobieństwa wartości znajdujących się w polach math-tej kolumny, jest jednostajny. Stosując analogiczną argumentację wnioskujemy, iż prawdopodobieństwo tego, że będziemy mogli wykonać math-tą fazę, o ile będziemy mogli wykonać pierwsze math faz, jest równe

display-math

Stąd otrzymujemy końcowy wynik, że prawdopodobieństwo wykonania całego algorytmu, czyli prawdopodobieństwo tego, że wyznacznik macierzy będzie różny od math jest równe

display-math

Zajmijmy się teraz następującym problemem. Rozważmy graf skierowany o math wierzchołkach, w którym dla każdej uporządkowanej pary liczb math takiej że math krawędź skierowana od wierzchołka math do wierzchołka math występuje z prawdopodobieństwem math (w szczególności, w tym grafie mogą występować pętle). Jakie jest prawdopodobieństwo tego, że w tym grafie jest nieparzysta liczba pokryć cyklowych?

obrazek

A czym właściwie są pokrycia cyklowe? Otóż pokrycie cyklowe to taki zbiór math krawędzi grafu, że z każdego wierzchołka wychodzi dokładnie jedna krawędź i do każdego wierzchołka wchodzi dokładnie jedna krawędź z tego zbioru. Przedstawia się ono jako zbiór rozłącznych cykli o łącznej długości math Każde pokrycie cyklowe możemy utożsamiać z math-elementową permutacją math w której math jest numerem wierzchołka, do którego wchodzi krawędź wychodząca z wierzchołka o numerze math Permutacja math reprezentuje pokrycie cyklowe, jeżeli dla każdego math istnieje krawędź z wierzchołka math do wierzchołka math

Zapiszmy nasz graf w postaci macierzy sąsiedztwa math  czyli macierzy kwadratowej o wymiarach math w której w polu math jest math jeżeli istnieje krawędź od wierzchołka math do wierzchołka math a w przeciwnym przypadku jest tam math A jak na tę macierz przenoszą się pokrycia cyklowe? Rozpatrzmy pewne pokrycie cyklowe i zaznaczmy w naszej macierzy pola odpowiadające krawędziom należącym do pokrycia. Będzie to math takich pól, że żadne dwa pola nie znajdują się w tym samym wierszu ani w tej samej kolumnie i, w dodatku, wszystkie te pola mają wartość math Zatem iloczyn liczb w tych polach będzie równy math A co dzieje się z permutacjami, którym nie odpowiadają pokrycia cyklowe? Jeżeli zaznaczymy w analogiczny sposób w naszej macierzy pola odpowiadające potencjalnym krawędziom z tej permutacji, to skoro nie reprezentowała ona pokrycia cyklowego, to w co najmniej jednym zaznaczonym polu znajdzie się math W takim razie iloczyn liczb w tych polach będzie równy math Możemy zatem wysunąć wniosek, że liczba pokryć cyklowych w tym grafie jest równa

display-math

gdzie math to zbiór wszystkich math-elementowych permutacji, a math to wartość pola math w macierzy sąsiedztwa. Powyższą liczbę nazywa się też permanentem macierzy math  Przypatrzmy się teraz wzorowi permutacyjnemu na wyznacznik macierzy:

display-math

gdzie math jest liczbą inwersji w permutacji math ale dla nas istotne będzie to, że math może przyjmować tylko wartości math i math a skoro te dwie liczby są tej samej parzystości, zatem permanent i wyznacznik macierzy całkowitoliczbowej są tej samej parzystości. Zauważmy jeszcze, że to, czy wyznacznik takiej macierzy sąsiedztwa jest parzysty, to po prostu pytanie, czy wyznacznik tej macierzy jest zerowy, jeżeli potraktujemy macierz sąsiedztwa jako macierz nad ciałem math W dodatku, sposób, w jaki losowaliśmy krawędzie grafu, odpowiada sposobowi, w jaki losowaliśmy elementy macierzy we wcześniejszej części artykułu. Z połączenia tych faktów otrzymujemy wniosek, że prawdopodobieństwo tego, że liczba pokryć cyklowych naszego grafu jest nieparzysta, jest równe

display-math