Algebra liniowaTrudneZadanie nr 1525
Niezerowe składniki wzoru permutacyjnego dla macierzy 7×7 trójdiagonalnej z narożnikami
Wyznacznik macierzy \(A = [a_{ij}]\) stopnia 7 to suma \(7! = 5040\) składników \(\operatorname{sgn}\sigma \cdot a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{7\sigma(7)}\) po wszystkich permutacjach \(\sigma\) zbioru \(\{1, \dots, 7\}\).
Wyraz \(a_{ij}\) jest różny od zera wtedy i tylko wtedy, gdy \(|i - j| \le 1\) albo \(\{i, j\} = \{1, 7\}\) (przekątna, miejsca tuż nad i tuż pod nią oraz dwa narożniki). Ile spośród 5040 składników jest różnych od zera?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Niezerowy składnik odpowiada permutacji, która przesuwa każdy numer o \(-1\), \(0\) lub \(+1\) „po okręgu” \(1, 2, \dots, 7, 1\). Zbadaj, co się dzieje, gdy \(\sigma(i) = i + 1\).
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Składnik jest niezerowy dokładnie wtedy, gdy \(\sigma(i) \in \{i-1, i, i+1\}\) dla każdego \(i\), z numeracją po okręgu (po 7 następuje 1).
- Niech \(\sigma(i) = i+1\). Wtedy \(\sigma(i+1) \in \{i, i+2\}\), bo \(i+1\) jest już zajęte. Jeśli \(\sigma(i+1) = i+2\), to podobnie \(\sigma(i+2) = i+3\) (bo \(i+1\) i \(i+2\) są zajęte) itd. — łańcuch zamyka się dopiero po obejściu całego okręgu.
- Zatem \(\sigma\) jest jednym z dwóch pełnych obrotów (\(i \mapsto i+1\) lub \(i \mapsto i-1\) dla wszystkich \(i\)) albo złożeniem rozłącznych transpozycji sąsiadów na okręgu (punkty stałe na pozostałych miejscach).
- Permutacje drugiego typu odpowiadają zbiorom rozłącznych krawędzi 7-kąta. Dla ścieżki o \(n\) wierzchołkach takich zbiorów jest \(F_{n+1}\) (liczby Fibonacciego \(1, 1, 2, 3, 5, 8, 13, 21, \dots\)), bo ostatni wierzchołek jest wolny albo połączony z poprzednim.
- Dla 7-kąta: krawędź \(\{7, 1\}\) nie jest użyta — ścieżka o 7 wierzchołkach, \(F_8 = 21\) zbiorów; jest użyta — zostaje ścieżka \(2, \dots, 6\), \(F_6 = 8\) zbiorów. Razem \(29\).
- Wszystkich niezerowych składników jest \(29 + 2 = 31\).
Odpowiedź: \(31\)
Czego warto się nauczyć?
Algebra liniowa to język geometrii i fizyki kwantowej: wektory, macierze i przekształcenia. W zadaniach mnożysz macierze, liczysz wyznaczniki i wartości własne, rozwiązujesz układy równań i opisujesz obroty, rzuty i symetrie.
Podobne zadania
- Wyznacznik macierzy 6×6 złożonej z cyklicznych przesunięć ciągu 1, 2, …, 6
- Cykliczny układ z sumami trzech sąsiednich niewiadomych: dla ilu n rozwiązanie jest jedyne
- Ranking pięciu szachistów wektorem Perrona przy dwóch remisach w tabeli punktowej
- Ile baz ortonormalnych R⁴ składa się wyłącznie z wektorów postaci (±1, ±1, ±1, ±1)/2