Lineare Algebra I, WS 2020/21

Inhalt

9.3 Die Cramersche Regel

Wir lernen in diesem Abschnitt mit dem Entwicklungssatz von Laplace eine Möglichkeit kennen, die Determinante einer Matrix \(A\) in Termen von Determinanten von »Untermatrizen« von \(A\) auszudrücken. Das führt dann auch auf die Cramersche Regel, mit der wir eine Formel für die inverse Matrix einer invertierbaren Matrix erhalten (die zwar für konkrete Berechnungen viel zu aufwändig ist, aber einen theoretischen Nutzen hat).

Sei \(A = (a_{ij})_{i,j}\in M_{n\times n}(K)\) eine quadratische Matrix über dem Körper \(K\). Für \(i,j\in \{ 1,\dots , n\} \) bezeichnen wir mit \(A_{ij}\in M_{n\times n}\) die Matrix, die aus \(A\) durch Ersetzen der \(i\)-ten Zeile durch den \(j\)-ten Standard-Zeilenvektor \(e_j^t = (0,\dots , 0,1,0\dots , 0)\) (\(1\) an der \(j\)-ten Stelle) und der \(j\)-ten Spalte durch den \(i\)-ten Standardbasisvektor \(e_i\) entsteht,

\[ A_{ij} = \begin{pmatrix} a_{11} & \cdots & a_{1,j-1} & 0 & a_{1, j+1} & \cdots & a_{1n} \\ \vdots & & \vdots & \vdots & \vdots & & \vdots \\ a_{i-1,1} & \cdots & a_{i-1,j-1} & 0 & a_{i-1, j+1} & \cdots & a_{i-1,n} \\ 0 & \cdots & 0 & 1 & 0 & \cdots & 0 \\ a_{i+1,1} & \cdots & a_{i+1,j-1} & 0 & a_{i+1, j+1} & \cdots & a_{i+1,n} \\ \vdots & & \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & \cdots & a_{n,j-1} & 0 & a_{n, j+1} & \cdots & a_{nn} \\ \end{pmatrix}. \]

Ferner bezeichnen wir mit \(A_{ij}^\prime \in M_{(n-1)\times (n-1)}(K)\) die Matrix, die aus \(A\) (oder äquivalent aus \(A_{ij}\)) durch Streichen der \(i\)-ten Zeile und der \(j\)-ten Spalte hervorgeht,

\[ A_{ij}^\prime = \begin{pmatrix} a_{11} & \cdots & a_{1,j-1} & a_{1, j+1} & \cdots & a_{1n} \\ \vdots & & \vdots & \vdots & & \vdots \\ a_{i-1,1} & \cdots & a_{i-1,j-1} & a_{i-1, j+1} & \cdots & a_{i-1,n} \\ a_{i+1,1} & \cdots & a_{i+1,j-1} & a_{i+1, j+1} & \cdots & a_{i+1,n} \\ \vdots & & \vdots & \vdots & & \vdots \\ a_{n1} & \cdots & a_{n,j-1} & a_{n, j+1} & \cdots & a_{nn} \\ \end{pmatrix}. \]

Es gilt dann

\[ \det A_{ij} = (-1)^{i+j} \det \begin{pmatrix} 1 & 0 & \cdots & \cdots & \cdots & \cdots & 0 \\ 0 & a_{11} & \cdots & a_{1,j-1} & a_{1, j+1} & \cdots & a_{1n} \\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ 0 & a_{i-1,1} & \cdots & a_{i-1,j-1} & a_{i-1, j+1} & \cdots & a_{i-1,n} \\ 0 & a_{i+1,1} & \cdots & a_{i+1,j-1} & a_{i+1, j+1} & \cdots & a_{i+1,n} \\ \vdots & \vdots & & \vdots & \vdots & & \vdots \\ 0 & a_{n1} & \cdots & a_{n,j-1} & a_{n, j+1} & \cdots & a_{nn} \\ \end{pmatrix} = (-1)^{i+j} \det A_{ij}^\prime . \]

wobei wir für die erste Gleichheit die \(j\)-te Spalte mit \(j-1\) Vertauschungen in die erste Spalte bringen, und die \(i\)-te Zeile mit \(i-1\) Vertauschungen in die erste Zeile bringen. Das bewirkt die Änderung des Vorzeichens um \((-1)^{j-1 + i-1} = (-1)^{i+j}\). Für die zweite Gleichheit können wir Beispiel 9.13 benutzen.

Damit können wir den Laplaceschen Entwicklungssatz formulieren (und der Beweis benötigt weniger Platz, als wir für die Erklärung der Notation verwendet haben).

Satz 9.29 Laplacescher Entwicklungssatz

Mit den obigen Notationen gilt für alle \(i\) die »Entwicklung von \(\det A\) nach der \(i\)-ten Zeile«:

\[ \det A = \sum _{j=1}^n (-1)^{i+j} a_{ij} \det A_{ij}^\prime \]

und für alle \(j\) die »Entwicklung von \(\det A\) nach der \(j\)-ten Spalte«:

\[ \det A = \sum _{i=1}^n (-1)^{i+j} a_{ij} \det A_{ij}^\prime . \]

Beweis

Wir beweisen die Entwicklung nach der \(i\)-ten Zeile in der Form

\[ \det A = \sum _{j=1}^n a_{ij} \det A_{ij}. \]

Nach der obigen Diskussion ist klar, dass diese Behauptung zur Formulierung im Satz äquivalent ist. Die Entwicklung nach einer Spalte erhält man durch ein analoges Argument, oder indem man die Entwicklung nach einer Zeile auf die transponierte Matrix anwendet und Satz 9.17 benutzt.

Die zu beweisende Formel erhalten wir direkt aus der Leibniz-Formel, indem wir die dort auftretende Summe über \(\sigma \in S_n\) nach dem Wert \(\sigma (i)\) sortieren:

\begin{align*} \det (A) & = \sum _{j=1}^n \sum _{\sigma \in S_n, \sigma (i)=j} \operatorname{sgn}(\sigma ) a_{ij} \prod _{l\ne j} a_{l,\sigma (l)}\\ & = \sum _{j=1}^n a_{ij} \det (A_{ij}). \end{align*}

Im zweiten Schritt benutzen wir, dass der Summand zu einer Permutation \(\sigma \) in der Leibniz-Formel für \(A_{ij}\) im Fall \(\sigma (i) = j\) gleich \(\prod _{l\ne j} a_{l,\sigma (l)}\) ist, und im Fall \(\sigma (i)\ne j\) verschwindet.

Es ist auch möglich (und nicht schwieriger), den Satz ohne Verwendung der Leibniz-Formel zu beweisen, indem man ausnutzt, dass die Determinante alternierend und multilinear ist. Siehe Bemerkung 9.42.

Bemerkung 9.30

Zur praktischen Berechnung von Determinanten sollte man den Entwicklungssatz (oder gar die Leibniz-Formel) nach Möglichkeit vermeiden. Stattdessen ist es fast immer besser, Zeilen- und Spaltenumformungen vorzunehmen, um die Matrix in eine einfachere Form (vorzugsweise natürlich in eine Dreiecksmatrix) umzuformen. Nur wenn die betrachtete Matrix Zeilen oder Spalten hat, in denen nur ein einziger Eintrag vorkommt oder wenn komplizierte Fallunterscheidungen/Divisionen erforderlich sind (weil in der Matrix Variablen oder Funktionen o.ä. auftreten), ist der Entwicklungssatz eine sinnvolle Alternative.

Definition 9.31

Wir definieren die Komplementärmatrix \(A^{\mathrm ad}\) zu \(A\) durch

\[ (A^{\text{ad}})_{i,j} = (-1)^{i+j} \det A^\prime _{ji}. \]

In der Literatur wird \(A^{\rm ad}\) manchmal als die adjungierte Matrix bezeichnet; daher auch die Notation. Wir vermeiden diese Sprechweise aber, weil der Begriff der adjungierten Abbildung bzw. adjungierten Matrix in der Linearen Algebra 2 bei der Behandlung von Bilinearformen mit einer völlig anderen Bedeutung auftritt.

Wenn wir den Entwicklungssatz für alle Spalten bzw. alle Zeilen »zusammenfassen«, erhalten wir die nach Gabriel Cramer (1704–1752) benannte Regel. Genau genommen gab es damals weder den Begriff der Determinante noch den der Matrix in der heutigen Form, so dass die Formulierung im folgenden Satz als eine Verallgemeinerung/Umformulierung zu verstehen ist. Cramer ging es seinerzeit um eine Lösungsformel für eindeutig lösbare lineare Gleichungssysteme, vergleiche Korollar 9.34.

Satz 9.32 Cramersche Regel

Es gilt

\[ AA^{\text{ad}} = A^{\text{ad}}A = \det (A) E_n. \]

Ist \(A\) invertierbar, so gilt

\[ A^{-1} = \det (A)^{-1} A^{\text{ad}}. \]

Beweis

Die zweite Aussage folgt direkt aus der ersten. Für die erste Aussage betrachten wir den Eintrag in Zeile \(i\) und Spalte \(j\) des Produkts \(AA^{\text{ad}}\), den wir nach Definition des Matrizenprodukts und der Matrix \(A^{\text{ad}}\) wie folgt ausdrücken können:

\[ \sum _{l=1}^n a_{il}\cdot (-1)^{l+j} \det A^\prime _{jl} \]

Ist \(i=j\), so ist dies die Entwicklung von \(\det (A)\) nach der \(i\)-ten Zeile von \(A\) und wir erhalten nach dem Laplaceschen Satz

\[ \sum _{l=1}^n a_{il}\cdot (-1)^{l+i} \det A^\prime _{il} = \det (A). \]

Ist andererseits \(i\ne j\), so können wir den Ausdruck – wieder nach dem Entwicklungssatz – als die Determinante der Matrix verstehen, die aus \(A\) dadurch entsteht, dass wir die \(j\)-te Zeile durch die \(i\)-te Zeile ersetzen (die Matrizen \(A^\prime _{jl}\) ändern sich durch diese Ersetzung nicht, weil dort die \(j\)-te Zeile von \(A\) gestrichen wurde). Da diese Matrix zwei gleiche Zeilen hat, ist ihre Determinante gleich \(0\). Insgesamt haben wir damit bewiesen, dass \(AA^{\text{ad}} =\det (A) E_n\) gilt.

Um \(A^{\text{ad}}A = \det (A) E_n\) zu zeigen, argumentiert man analog mit der Entwicklung nach einer Spalte oder überlegt sich, dass \((A^t)^{\text{ad}} = (A^{\text{ad}})^t\) gilt und wendet die vorherige Überlegung auf \(A^t\) an.

Korollar 9.33

Sei \(A\in GL_n(\mathbb Q)\). Wir nehmen an, dass alle Einträge von \(A\) in \(\mathbb Z\) liegen. Genau dann liegen auch alle Einträge von \(A^{-1}\) in \(\mathbb Z\), wenn \(\det (A)\in \{ 1,-1\} \).

Beweis

Weil alle Einträge von \(A\) in \(\mathbb Z\) liegen, gilt auch \(\det (A)\in \mathbb Z\). Das sehen wir beispielsweise aus der Leibniz-Formel. Es ist auch klar, dass \(\det (A)\in \{ 1,-1\} \) folgt, wenn auch alle Einträge von \(A^{-1}\) in \(\mathbb Z\) sind. Denn nach dem Produktsatz gilt \(\det (A)\det (A^{-1}) = 1\), und beide Faktoren sind ganze Zahlen.

Die umgekehrte, schwierigere Implikation folgt nun aus der Cramerschen Regel. Denn die Einträge der Komplementärmatrix \(A^{\text{ad}}\) sind polynomielle Ausdrücke in den Einträgen von \(A\), sind also wegen unserer Voraussetzung an \(A\) sämtlich ganze Zahlen. Wenn \(\det (A)\in \{ 1, -1\} \) ist, folgt, dass auch die Matrix \(A^{-1} = \det (A)^{-1} A^{\text{ad}}\) nur ganzzahlige Einträge hat.

Wir erhalten aus der obigen abstrakten Form der Cramerschen Regel auch die oben schon erwähnte »Lösungsformel« für lineare Gleichungssysteme. Um ein konkret gegebenes Gleichungssystem zu lösen, ist der Gauß-Algorithmus in aller Regel besser geeignet, aber manchmal ist die Formel nützlich.

Korollar 9.34

Sei \(Ax = b\) ein lineares Gleichungssystem mit \(n\) Unbestimmten und \(n\) Gleichungen (d.h. die Koeffizientenmatrix \(A\) ist eine quadratische Matrix der Größe \(n\times n\)), das genau eine Lösung besitzt (d.h. \(A\) ist invertierbar).

Für \(i=1, \dots , n\) sei \(A_i\) die Matrix, die aus \(A\) entsteht, indem die \(i\)-te Spalte von \(A\) durch den Vektor \(b\) ersetzt wird. Dann ist die eindeutig bestimmte Lösung des obigen linearen Gleichungssystems gegeben durch den Vektor mit den Einträgen

\[ \left(\frac{\det (A_1)}{\det (A)}, \dots , \frac{\det (A_n)}{\det (A)}\right)^t. \]

Beweis

Da \(A\) invertierbar ist, ist \(\det (A)\ne 0\), so dass wir durch \(\det (A)\) teilen können. Die eindeutige Lösung des gegebenen linearen Gleichungssystems ist

\[ A^{-1}b = \frac{1}{\det (A)} A^{\text{ad}} b, \]

wobei wir die Cramersche Regel in der Form von Satz 9.32 benutzt haben.

Der \(i\)-te Eintrag des Vektors \(A^{\text{ad}} b\) ist mit den obigen Bezeichnungen

\[ \sum _{j=1}^n (-1)^{i+j}\det (A^\prime _{ji}) b_j = \det (A_i), \]

wobei wir den Laplaceschen Entwicklungssatz für die Matrix \(A_i\) benutzen (und dass \((A_i)_{ji}^\prime = A^\prime _{ji}\) gilt, weil für die Bildung dieser Matrix die \(i\)-te Spalte ohnehin gestrichen wird).