Algebra liniowaTrudneZadanie nr 1525

Niezerowe składniki wzoru permutacyjnego dla macierzy 7×7 trójdiagonalnej z narożnikami

Wyznaczniki Zadania konkursowePoziom pierwszego roku studiów

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?

+16 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

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
  1. 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).
  2. 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.
  3. 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).
  4. 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.
  5. 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\).
  6. 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.

Więcej zadań z algebry liniowej →

Podobne zadania