W dniu 2013-05-14 12:10, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
>> przez kolumny A (jest a obrazie A, dość trywialny wniosek).
>> Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
>> i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
>> przecina (iloczynem skalarnym).
>>
>> Wiecej szczegółow.
>> http://www.math.ksu.edu/~dmaldona/math551/lights_out
.pdf
>>
>> *) tutaj macierz A budujemy tsak, by była symetryczna A^T=A,
>> więc kojądro i jądro (null space) to to samo.
>>
>> Ok, rozwiążemy równanie macierzowe w Z^2 (n*m)^3 ?
>
> To wygląda ciekawie:
>
> http://online.redwoods.edu/instruct/darnold/laproj/F
all2001/Emilia/emilia_paper.pdf

O, to jest genialne:)

Dla tych, co nie czytali:
Gwóźdź jest w rozdziale 4. Zamiast myśleć o równaniu na m*n
wspolczynnikow patrzymy na to jak na układ m rownań na n
wspolczynnikow (to jeszcze nic ciekawego), a dzieki odpowiedniej
strukturze naszej macierzy problem rozbija się na

m-1 rownań postaci:
kawałak rozwiązania = Maceirz_i (zapalenia, pierwszy kawałek rozwiązania)

oraz równanie

Macierz*pierwszy kawalek rozwiazania = macierze_1 (zapalenia).

Wszystkie macierze są n x n .

Cała siłowa cześć siedzi w ostatnim rownaniu (mamy taką intuicję,
że tylko ostatnia linijka się liczy. W rozwiązaniu Vaxa z tego
korzystaliśmy, ale nie wiedzialem, że da się w podejściu
algebraicznym do tego dojść). Zarówno rozwiązanie zadanych zapaleń,
jak i znalezienie wektorów zerowych wymaga rozłożenia tylko tej
ostatniej macierzy.
Za darmo dostajemy też to, co wcześniej trzeba bylo (prosto) sobie
udowodnić, że dim(ker(A)) <= n (jak wszędzie n<=m)

Zwłaszcza ogromną korzyść odnosimy, gdy m>>n:)

> www.m-hikari.com/ijcms-2010/29-32-2010/leeIJCMS29-32
-2010.pdf

> https://ida.mtholyoke.edu/xmlui/bitstream/handle/101
66/693/375.pdf?sequence=1
> http://www.unf.edu/~wkloster/fibonacci/switch.ps
> www.unf.edu/~wkloster/fibonacci/lama.pswww.unf.edu/~
wkloster/fibonacci/lama.ps

Jeszcze nie poczytałem...

pzdr
bartekltg