algebra dawid: Trivial mógłbyś pomóc przy udowodnieniu wyznaczniku vandermonda ? Czyli jeżeli mamy: V_n = | 1 x₁ x₁² ... x₁^{n − 1} | | 1 x₂ x₂² ... x₂^{n − 1} | | ... ... ... ... | | 1 x_n x_n² ... x_n^{n − 1} | mamy wykazać, że V_n = ∏_{n ≥ k > l ≥ 1} (x_k − x_l)

Trivial: Trzeba wyeliminować Gaussem.

dawid: a jak to zrobić, tj.: są tutaj te kropki i to chyba trochę komplikuje

Trivial: Trzeba się trochę pomęczyć, ale w końcu wychodzi.

dawid: a robiłeś już coś takiego ?

dawid: jeszcze nie miałem eliminacji Gaussa, próbuje coś z tego wyczytać http://pl.wikipedia.org/wiki/Metoda_eliminacji_Gaussa ale mam problem otóż w przykładzie mamy napisane "odjęcia wielokrotności 1. wiersza od 2., 3. i 4. wiersza," na podstawie tego w ogóle nie zgadza mi się wiersz 3 możesz powiedzieć jak to ma wyglądać?

asdf: bo jest źle

Trivial: Pomijam kreski wyznacznika w zapisie. detA = 1 x₁ x₁² x₁³ ... x₁ⁿ⁻¹ 1 x₂ x₂² x₂³ ... x₂ⁿ⁻¹ 1 x₃ x₃² x₃³ ... x₃ⁿ⁻¹ 1 x₄ x₄² x₄³ ... x₄ⁿ⁻¹ ... ... ... ... ... ... 1 x_n x_n² x_n³ ... x_nⁿ⁻¹ = 1 x₁ x₁² x₁³ ... x₁ⁿ⁻¹ 0 x₂−x₁ x₂²−x₁² x₂³−x₁³ ... x₂ⁿ⁻¹−x₁ⁿ⁻¹ 0 x₃−x₁ x₃²−x₁² x₃³−x₁³ ... x₃ⁿ⁻¹−x₁ⁿ⁻¹ 0 x₄−x₁ x₄²−x₁² x₄³−x₁³ ... x₄ⁿ⁻¹−x₁ⁿ⁻¹ ... ... ... ... ... ... 0 x_n−x₁ x_n²−x₁² x_n³−x₁³ ... x_nⁿ⁻¹−x₁ⁿ⁻¹ = x₂−x₁ x₂²−x₁² x₂³−x₁³ ... x₂ⁿ⁻¹−x₁ⁿ⁻¹ x₃−x₁ x₃²−x₁² x₃³−x₁³ ... x₃ⁿ⁻¹−x₁ⁿ⁻¹ x₄−x₁ x₄²−x₁² x₄³−x₁³ ... x₄ⁿ⁻¹−x₁ⁿ⁻¹ ... ... ... ... ... x_n−x₁ x_n²−x₁² x_n³−x₁³ ... x_nⁿ⁻¹−x₁ⁿ⁻¹ Numerujemy wiersze i kolumny od dwójki (k = 2..n), (m = 2..n) Chcemy podzielić k−ty wiersz przez x_k−x₁ (wyznacznik trzeba pomnożyć przez x_k−x₁ dla każdego k = 2..n) Zauważmy, że wyraz o indeksie (k,m) to: x_k^m−1−x₁^m−1 Dzieląc taki element przez x_k−x₁ otrzymamy:

	xkm−1−x1m−1
		.
	xk−x1

Korzystając ze wzoru aⁿ−bⁿ = (a−b)(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+...+abⁿ⁻²+bⁿ⁻¹) Mamy

	xkm−1−x1m−1
ck,m =		= xkm−2+x1xkm−3+...+x1m−2
	xk−x1

Teraz wykonujemy operację (wyznacznik się nie zmienia) c_k,m − x₁*c_k,m−1 = = x_k^m−2+x₁x_k^m−3+...+x₁^m−2 − x₁(x_k^m−3+x₁x_k^m−4+...+x₁^m−3) = x_k^m−2+x₁x_k^m−3+...+x₁^m−2 − (x₁x_k^m−3+x₁²x_k^m−4+...+x₁^m−2) = x_k^m−2 Kontynuując liczenie wyznacznika mamy: detA = (x₂−x₁)(x₃−x₁)(x₄−x₁)...(x_n−x₁) * 1 x₂ x₂² ... x₂ⁿ⁻² 1 x₃ x₃² ... x₃ⁿ⁻² 1 x₄ x₄² ... x₄ⁿ⁻² ... ... ... ... ... 1 x_n x_n² ... x_nⁿ⁻² Jest to analogiczna macierz co A, tylko że z pierwiastkami x₂..x_n i o rozmiarze (n−1)x(n−1). Zatem przez indukcję mamy: detA = (x₂−x₁)(x₃−x₁)(x₄−x₁)...(x_n−x₁) * (x₃−x₂)(x₄−x₂)...(x_n−x₂) * ... * (x_n−x_n−1) * 1

dawid: Wow, bardzo dziękuję ale żeby to zrozumieć muszę wpierw pojąć eliminację Gaussa, mógłbyś odpowiedzieć na moje pytanie z 17:19 ?

Trivial: Jest dobrze. w₂ ← w₂ − 2*w₁ w₃ ← w₃ + w₁ w₄ ← w₄ − 2*w₁

dawid: a czemu nie mnożymy przez 2 ?

Trivial: A czemu mamy mnożyć? Chcemy pozbyć się pierwszej kolumny (wyzerować wszystko pod elementem (1,1))

dawid: a mógłbyś napisać gdzie zniknęły u Ciebie 1 wiersz i 1 kolumna ?

Trivial: Rozwinięcie Laplace'a na elemencie (1,1). Wszystko oprócz tego mniejszego wyznacznika się zeruje.

dawid: ok to jeszcze dwa ostatnie pytania bo resztę chyba rozumiem a) "Chcemy podzielić k−ty wiersz przez x_k−x₁" − mógłbyś to jakoś wytłumaczyć w jakim celu? Po co to ? b) "Teraz wykonujemy operację (wyznacznik się nie zmienia)" − jaką operację i po co? Takie ogólne pytania, ponieważ wydaje się takie wyjęte z kontekstu

Trivial: Oba punkty są po to, aby doprowadzić tę macierz do analogicznej, tylko trochę mniejszej. a) Najpierw dzielimy każdy wiersz aby mieć jedynki zamiast x_k−x₁. b) Potem odejmujemy kolumny od końca, tzn. przedostatnią od ostatniej, 2 od końca od przedostatniej, itd przemnożone przez x₁ aż dojdziemy do pierwszej, od której nic nie odejmujemy. Symbolicznie: k_n ← k_n − x₁*k_n−1 k_n−1 ← k_n−1 − x₁*k_n−2 k_n−2 ← k_n−2 − x₁*k_n−3 .... k₃ ← k₃ − x₁*k₂ k₂ bez zmian k₁ nie ma, bo numerujemy kolumny i wiersze od dwójki (z czystej wygody zapisu).

dawid: na końcu wspominasz o indukcji nie trzeba tego jakoś rozwinąć ?

Trivial: Krok indukcyjny jest taki: det 1 x₁ x₁² ... x₁ⁿ⁻¹ 1 x₂ x₂² ... x₂ⁿ⁻¹ 1 x₃ x₃² ... x₃ⁿ⁻¹ ... ... ... ... ... 1 x_n x_n² ... x_nⁿ⁻¹ = (x₂−x₁)(x₃−x1)...(x_n−x₁) // Tutaj mamy różnice z x₁ * det 1 x₂ x₂² ... x₂ⁿ⁻² 1 x₃ x₃² ... x₃ⁿ⁻² 1 x₄ x₄² ... x₄ⁿ⁻² ... ... ... ... ... 1 x_n x_n² ... x_nⁿ⁻² = (x₂−x₁)(x₃−x₁)...(x_n−x₁) * (x₃−x₂)(x₄−x₂)...(x_n−x₂) // Tu z kolei różnice z x₂ * det 1 x₃ x₃² ... x₃ⁿ⁻³ 1 x₄ x₄² ... x₄ⁿ⁻³ 1 x₅ x₅² ... x₅ⁿ⁻³ ... ... ... ... ... 1 x_n x_n² ... x_nⁿ⁻³ = (x₂−x₁)(x₃−x₁)...(x_n−x₁) * (x₃−x₂)(x₄−x₂)...(x_n−x₂) * (x₄−x₃)(x₅−x₃)...(x_n−x₃) * ... * (x_n−x_n−1) * det(1) // Zredukowaliśmy problem do wyznacznika z macierzy jednowymiarowej = (x₂−x₁)(x₃−x₁)...(x_n−x₁) * (x₃−x₂)(x₄−x₂)...(x_n−x₂) * (x₄−x₃)(x₅−x₃)...(x_n−x₃) * ... * (x_n−x_n−1) Koniec.

dawid: Wow skąd ty to wszystko wiesz ?

Trivial: Ten wzór powtarza się ciągle. Rozwiązanie dużego problemu zależy od rozwiązań takiego samego problemu, tylko mniejszego. Taktyka znana jako Divide and Conquer (dziel i zwyciężaj).

dawid: Bardziej chodziło mi o to, że radzisz sobie z każdym zadaniem na dowodzenie

Trivial: Zazwyczaj próbuję różnych sposobów zanim wyjdzie. I bez przesady, z każdym na pewno bym sobie nie poradził.

dawid: Brałeś udział w Olimpiadach Matematycznych ? Od kiedy tak dobrze sobie radzisz z matematyką Jeżeli można spytać.

Trivial: Nie licząc jakichś szkolnych konkursów nie brałem udziału w żadnych olimpiadach. Z matmą zawsze miałem dość lekko (tzn. wystarczyło że się skupiłem i przeczytałem coś 2−3 razy ze zrozumieniem).

dawid: Podziwiam Cię Mam jeszcze coś takiego: Wykaż, że wyznacznik A jest równy b₁b₂...b_n. A = | 1 a₁ a₂ ... a_n | | 1 a₁ + b₁ a₂ ... a_n | | 1 a₁ a₂ + b₂ ... a_n | | ... ... .... ... ... | | 1 a₁ a₂ ... a_n + b_n |

Trivial: To zadanie jest dużo dużo prostsze niż poprzednie. Możesz sam zrobić. Podejście podobne, tylko zadanie samo się rozwiązuje po eliminacji pierwszej kolumny.

dawid: no wtedy otrzymam: 1 a₁ a₂ ... a_n 0 b₁ 0 ... 0 0 0 b₂ ... 0 ... ... ... ... ... 0 0 0 ... b_n i co dalej?

Trivial: Masz wyznacznik jak na dłoni. Wyznacznik macierzy trójkątnej to iloczyn diagonali. 1*b₁*b₂*...*b_n

dawid: no ale co z tymi a₁, ... itp.?

Trivial: nic.

dawid: a można to jakoś fachowo obliczyć ? (la pleacem ?)

Trivial: Możesz rozwijać, ale naprawdę nie ma po co. Wyznacznik macierzy trójkątnej można policzyć nawet z definicji (istnieje tylko jeden niezerowy iloczyn elementów).

dawid: To może ostatnie na dzisiaj: Przyjmijmy założenie, że AB = I_n dla macierzy A i B rozmiarów m x n. a) Wykaż, że układ Bx^→ = 0^→ ma tylko jedno rozwiązanie, które jest wektorem zerowym. b) Wykaż, że dla dowolnego b^→ o liczbie współrzędnych równych n, układ Ax^→ = b^→ ma rozwiązanie.

dawid:

Trivial: Mi na dziś już wystarczy.

dawid: ok

dawid: może dzisiaj

Trivial: Dzisiaj również raczej nie − muszę skończyć projekt. Ale jeśli już jestem to: a) Bx = 0 ⇔ ABx = A*0 ⇔ I*x = 0 ⇔ x = 0 b) Ax = b ⇔ Ax = I*b ⇔ Ax = ABb ⇔ x =^m.in. Bb

Vizer: Trivial znowu na ostatni czas projekt?

Trivial: Tym razem nie! Ale i tak chce jak najszybciej skończyć.

Trivial: W ogóle ten projekt jest dużo trudniejszy niż myślałem.

dawid: a można wiedzieć co to za projekt ? tak z czystej ciekawości

Trivial: Kompilator prostego języka programowania.