Autor Wątek: Rozwiązanie układu równań dla macierzy rzadkiej w Z2  (Przeczytany 550 razy)

Offline Zombiak

  • Użytkownik

# Listopad 11, 2009, 15:58:28
Mam taki problem, z którym chyba nie potrafię sobie sam poradzić ;) Mam sobie listę N wektorów gdzie każdy ma P współrzędnych w zbiorze Z2. Muszę wybrać z tej listy wszystkie albo przynajmniej część kombinacji gdzie suma (mod 2) wektorów będzie wektorem zerowym.  Oczywiście, jeżeli ułożę te wektory w macierz to mogę całość sprowadzić do problemu znalezienia wektora V, który po pomnożeniu przez tą macierz da wektor zerowy. Zawsze N > P, ale po takim ułożeniu macierzy jak wspomniałem to ilość kolumn > wierszy i dodatkowo jest w niej pełno zer. Chciałem użyć eliminacji Gaussa żeby to rozwiązać (wcześniej nie widziałem na oczy tego algo.), ale wydaje mi się, że z w/w powodów się tu nie nadaje. Może ktoś coś doradzić?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline frea

  • Użytkownik

# Listopad 11, 2009, 22:45:13
Dosyc prosto mozna sobie tutaj ulatwic :
Idziesz tak jak zwykla eliminacja gasua, to gdy eliminujesz za pomoca wiersza i wiersze j > i + 1 to zwroc uwage, ze jezeli w danej kolumnie w wierszu i-tym masz 0, to cala kolumna sie nie zmienia. Jezeli natomiast jest 1 w kolumnie to zmienia sie wartosc na przeciwna w calej kolumnie w dol.
Stosujac gausa odrazu zmieniasz wartosc calej kolumny, a tutaj mozesz byc sprytny i zapamietac, czy kolumna jest zamieniona, czy nie (eliminowana dwukrotnie za pomoca 1 nie zmienia sie). Na koniec w zaleznosci czy kolumna ma zapamietane ,ze jest zamioniona badz to zmienaisz 0 na 1 i 1 na 0. To ci zadziala dla wierszy > P. Dla wierszy <= P musisz wczesniej dokonac zapisania.