Determinante effizient berechnen

Question

Ich soll folgende Determinante bestimmen, weiß aber nicht, wie man das geschickt anstellen kann.

1	1	0	0	...	.	.	0
-1	1	4	0	...	.	.	0
0	-1	1	9	...	.	.	0
...	.	.	.	...	.	.	0
0	0	0	0	...	-1	1	(n-1)^2
0	0	0	0	...	0	-1	1

Habt ihr einen Tipp für mich?

Comments

Hast du schon probiert die Matrix auf Zeilenstufenform zu bringen? Der Reihe nach zu jeder Zeile (ab Zeile 2) die jeweils darüber liegende addieren.

Dann könnte man die Determinante wohl schon mal mit dem Produktzeichen schreiben.

Answer 1

Aloha :)

Ich hoffe, dass ich den Aufbau der Determinante richtig verstanden habe. Um die Idee zu verdeutlichen, schreibe ich die ersten 4 Fälle einfach mal auf:

Bei $n=1$ ist nicht viel zu tun:$$D_1=\left|\begin{array}{c}1\end{array}\right|=1$$

Bei $n=2$ addiere ich Zeile 1 zu Zeile 2 und ziehe danach aus Zeile 2 den Faktor vor die Determinante:$$D_2=\left|\begin{array}{c}1 & 1\\-1 & 1\end{array}\right|=\left|\begin{array}{c}1 & 1\\0 & 2\end{array}\right|=2\cdot\left|\begin{array}{c}1 & 1\\0 & 1\end{array}\right|=2$$

Bei $n=3$ addiere ich Zeile 1 zu Zeile 2 und ziehe danach aus Zeile 2 den Faktor vor die Determinante:$$D_3=\left|\begin{array}{c}1 & 1 & 0\\-1 & 1 & 4\\0 & -1 & 1\end{array}\right|=\left|\begin{array}{c}1 & 1 & 0\\0 & 2 & 4\\0 & -1 & 1\end{array}\right|=2\cdot\left|\begin{array}{c}1 & 1 & 0\\0 & 1 & 2\\0 & -1 & 1\end{array}\right|$$Jetzt addiere ich weiter Zeile 2 zu Zeile 3 und ziehe aus Zeile 3 den Faktor vor:$$\phantom{D_3}=2\cdot\left|\begin{array}{c}1 & 1 & 0\\0 & 1 & 2\\0 & 0 & 3\end{array}\right|=2\cdot3\cdot\left|\begin{array}{c}1 & 1 & 0\\0 & 1 & 2\\0 & 0 & 1\end{array}\right|=6$$

Bei $n=4$ wiederhole ich zunächst alle Schritte vom Fall $n=3$:

$$D_4=\left|\begin{array}{c}1 & 1 & 0 & 0\\-1 & 1 & 4 & 0\\0 & -1 & 1 & 9\\0 & 0 & -1 & 1\end{array}\right|=\left|\begin{array}{c}1 & 1 & 0 & 0\\0 & 2 & 4 & 0\\0 & -1 & 1 & 9\\0 & 0 & -1 & 1\end{array}\right|=2\cdot\left|\begin{array}{c}1 & 1 & 0 & 0\\0 & 1 & 2 & 0\\0 & -1 & 1 & 9\\0 & 0 & -1 & 1\end{array}\right|$$$$\phantom{D_4}=2\cdot\left|\begin{array}{c}1 & 1 & 0 & 0\\0 & 1 & 2 & 0\\0 & 0 & 3 & 9\\0 & 0 & -1 & 1\end{array}\right|=2\cdot3\cdot\left|\begin{array}{c}\underline1 & \underline1 & \underline0 & 0\\\underline0 & \underline1 & \underline2 & 0\\\underline0 & \underline0 & \underline1 & 3\\0 & 0 & -1 & 1\end{array}\right|$$Man erkennt die letzte Determinante aus der Berechnung von $D_3$ wieder (unterstrichene Einträge), nur sind jetzt noch die 3 Elemente in der rechten unteren Ecke dazu gekommen, alle anderen zusätzlichen Einträge sind 0. Wir können daher noch einen weiteren Schritt (Addition der vorletzten Zeile zur letzten und Faktor herausziehen) durchführen:$$\phantom{D_4}=2\cdot3\cdot\left|\begin{array}{c}1 & 1 & 0 & 0\\0 & 1 & 2 & 0\\0 & 0 & 1 & 3\\0 & 0 & 0 & 4\end{array}\right|=2\cdot3\cdot4\cdot\left|\begin{array}{c}1 & 1 & 0 & 0\\0 & 1 & 2 & 0\\0 & 0 & 1 & 3\\0 & 0 & 0 & 1\end{array}\right|=24$$

Damit ist klar, dass: $D_n=n!$

Dieses Vorgehen kannst du, wenn verlangt, noch in einen sauberen Induktionsbeweis packen. Die Beweisidee sollte zumindest jetzt klar sein ;)

Comments

Alles verstanden... sehr verständlich und anschaulich erklärt.

Vielen Dank dafür. Ich habe das als Induktionsbeweis übernommen.

Answer 2

Du kannst auch die Determinante aus den beiden Elementen der letzten Spalte berechnen. Sei $A_n$ die Matrix aus der Aufgabenstellung, so ist$$\begin{aligned} \det A_{n+1}&= \left| \begin{array}{r}1& 1& 0& \dots& 0& 0& 0\\ -1& 1& 4& \dots& 0& 0& 0\\ 0& -1& 1& \dots& 0& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots& \vdots\\ 0& 0& 0& \dots& 1& (n-1)^2& 0\\ 0& 0& 0& \dots& -1& 1& n^2\\ 0& 0& 0& \dots& 0& -1& 1\end{array} \right| \\ &= \left| \begin{array}{r}1& 1& 0& \dots& 0& 0\\ -1& 1& 4& \dots& 0& 0\\ 0& -1& 1& \dots& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& 0& \dots& 1& (n-1)^2\\ 0& 0& 0& \dots& -1& 1\end{array}\right| - n^2 \left| \begin{array}{r}1& 1& 0& \dots& 0& 0\\ -1& 1& 4& \dots& 0& 0\\ 0& -1& 1& \dots& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& 0& \dots& 1& (n-1)^2\\ 0& 0& 0& \dots& 0& -1\end{array}\right| \\ &= \det A_n + n^2 \cdot \det A_{n-1}\end{aligned}$$Weiter gilt natürlich $$\det A_1 = 1 \\ \det A_2 = 2$$Setzt man das in die Rekursion oben ein, so ergibt sich die Folge$$\det A_i = \{ 1,\, 2,\, 6,\, 24,\, 120 ,\, \dots\}$$was den Verdacht nährt, dass $$\det A_n = n!$$ist. Für die ersten $n$ ist das korrekt (s.o.) und für $n+1$:$$\begin{aligned} \det A_{n+1} &= \det A_n + n^2 \cdot \det A_{n-1} \\ &= n! + n^2 (n-1)! \\ &= (n-1)!\cdot (n + n^2) \\&= (n-1)!\cdot n \cdot (n+1) \\ &= (n+1)!\end{aligned}$$ebenso! Also gilt für alle $n \in \mathbb{N}$$$\det A_n = n!$$

Comments

Hmm, erstmal Danke für deine Lösung.

Ich verstehe, dass du in der letzten Spalte $n^2$ in $0+n^2$ aufteilst und daraus 2 Determinanten machst. Aber dann werden ja alle sonstigen Einträge mit kopiert. Also steht unter dem $n^2$ eine 1 und vor dieser 1 eine -1. Beim Rausziehen von $n^2$ als Faktor müsste es doch $+n^2$ heißen und aus der 1 wird doch dann $1/n^2$ oder?

Ich muss mir das nochmal in Ruhe aufschreiben, um es zu verstehen.

---

Ich verstehe, dass du in der letzten Spalte n2 in 0+n2 aufteilst ...

Öh - nein gar nicht! Ich hatte angenommen, Du wüsstest grundsätzlich wie man eine Determinante berechnet. Siehe Laplace'scher Entwicklungssatz. Was anderes habe ich nicht gemacht.

Aber dann werden ja alle sonstigen Einträge mit kopiert.

und kopiert wird da auch nichts!?