Determinantenberechnung

Das Rechenverfahren an die Matrixgröße anpassen

Aus der Definition der Determinante folgen mehrere Rechenverfahren. $Direkte Formeln$ genügen für kleine Matrizen. Bei großen dichten Matrizen führen die Elimination oder eine $\mathrm{LU}$ -Zerlegung zur Dreiecksform und vermeiden das faktorielle Wachstum einer rekursiven Kofaktorentwicklung.

Grundlegender Fall einer Matrix erster Ordnung

Für Matrizen der Größe $1 \times 1$ ist die Determinante sehr einfach. Wenn $A \in \mathbb{R}^{1 \times 1}$ mit $A = (a_{11})$ , dann:

\det A = a_{11}

Bei einer $1\times1$ -Matrix ist die Determinante gleich ihrem $einzigen Eintrag$ . Größere Matrizen werden durch Entwicklung oder Elimination auf kleinere Fälle zurückgeführt.

Konzept der Submatrix

Vor der Kofaktorentwicklung benötigen wir den Begriff der $Untermatrix$ . Für $A \in \mathbb{R}^{n \times n}$ und $i, j \in \{1, 2, \ldots, n\}$ entsteht die Untermatrix $A_{ij}$ der Größe $(n-1) \times (n-1)$ , indem Zeile $i$ und Spalte $j$ aus $A$ entfernt werden.

Betrachten wir ein Beispiel für eine $3 \times 3$ -Matrix. Angenommen, wir haben:

A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

Um die Submatrix $A_{12}$ zu erhalten, entfernen wir Zeile $1$ und Spalte $2$ :

A_{12} = \begin{pmatrix} \cancel{a_{11}} & \cancel{a_{12}} & \cancel{a_{13}} \\ a_{21} & \cancel{a_{22}} & a_{23} \\ a_{31} & \cancel{a_{32}} & a_{33} \end{pmatrix}

Für die Submatrix $A_{23}$ entfernen wir Zeile $2$ und Spalte $3$ :

A_{23} = \begin{pmatrix} a_{11} & a_{12} & \cancel{a_{13}} \\ \cancel{a_{21}} & \cancel{a_{22}} & \cancel{a_{23}} \\ a_{31} & a_{32} & \cancel{a_{33}} \end{pmatrix}

Dieser Vorgang gilt für alle Kombinationen von Zeilen und Spalten, die entfernt werden.

Kofaktorentwicklung

Die Kofaktorentwicklung berechnet die Determinante aus kleineren Minoren. Wir können nach einer beliebigen festen Zeile $i$ entwickeln:

\det A = \sum_{j=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Alternativ können wir nach einer beliebigen festen Spalte $j$ entwickeln:

\det A = \sum_{i=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Der Term $(-1)^{i+j}\det A_{ij}$ ist der $Kofaktor$ von $a_{ij}$ . Der Faktor $(-1)^{i+j}$ erzeugt das abwechselnde Schachbrettmuster der Vorzeichen. Eine Zeile oder Spalte mit vielen Nullen verringert die Anzahl der zu berechnenden Minoren.

Kofaktorentwicklung für eine Matrix dritter Ordnung

Für eine $3 \times 3$ -Matrix sieht die Kofaktorentwicklung beispielsweise so aus:

A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 1 \\ 1 & 2 & 0 \end{pmatrix}

Wir wählen die $erste Zeile$ zur Erweiterung:

\begin{aligned} \det A &= 2 \cdot (-1)^{1+1} \det A_{11} \\ &\quad{}+ 1 \cdot (-1)^{1+2} \det A_{12} \\ &\quad{}+ 3 \cdot (-1)^{1+3} \det A_{13} \end{aligned}

Die Entwicklung kann nach jeder Zeile oder Spalte erfolgen. Jeder Nulleintrag setzt einen Kofaktorterm auf null, sodass bei einer Zeile oder Spalte mit vielen Nullen weniger Terme berechnet werden müssen.

Dreieckige und diagonale Matrizen

Für einige spezielle Matrizentypen wird die Determinantenberechnung sehr einfach. Die Form der Matrix entfernt die meisten Terme, bevor du überhaupt entwickelst, sodass nur $ein einziges Produkt$ übrig bleibt. Wer die Form zuerst erkennt, spart sich den größten Teil der Rechnung.

Für eine obere Dreiecksmatrix $R$ :

R = \begin{pmatrix} r_{11} & * & \cdots & * \\ 0 & r_{22} & \cdots & * \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}

Ihre Determinante ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Für die untere Dreiecksmatrix $L$ :

L = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ * & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ * & * & \cdots & l_{nn} \end{pmatrix}

Ihre Determinante ist:

\det L = l_{11} \cdot l_{22} \cdot \ldots \cdot l_{nn}

Für eine Diagonalmatrix $D$ :

D = \begin{pmatrix} d_{11} & 0 & \cdots & 0 \\ 0 & d_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{nn} \end{pmatrix}

Ihre Determinante ist:

\det D = d_{11} \cdot d_{22} \cdot \ldots \cdot d_{nn}

Für alle drei Matrizentypen ist die Determinante gleich $dem Produkt aller Hauptdiagonalelemente$ .

Elementarmatrizen

Elementarmatrizen sind Matrizen, die aus der Identitätsmatrix mit einer elementaren Zeilenoperation erhalten werden. Die Determinanten elementarer Matrizen haben leicht zu berechnende Werte:

$Zeilenskalierungsmatrix$ $S_i(\lambda)$ , mit $\lambda \neq 0$ , die Zeile $i$ mit $\lambda$ multipliziert:

$\det S_i(\lambda) = \lambda$
$Zeilenvertauschungsmatrix$ $Q_i^j$ , die die Zeilen $i$ und $j$ vertauscht:

$\det Q_i^j = -1$
$Transvektionsmatrix$ $P_i^j(\lambda)$ , die die Operation $R_i \leftarrow R_i + \lambda R_j$ ausführt:

$\det P_i^j(\lambda) = 1$

Bei Vertauschungen und Transvektionen bezeichnen die Indizes $zwei verschiedene Zeilen$ , also $i\neq j$ . Eine einzelne Zeilenvertauschung wechselt das Vorzeichen der Determinante. Das Addieren eines Vielfachen einer Zeile zu einer anderen lässt die Determinante dagegen unverändert.

Gaußsche Eliminierung zur Determinantenberechnung

Die Gauß-Elimination, beziehungsweise eine äquivalente $\mathrm{LU}$ -Zerlegung, überführt eine dichte Matrix in $obere Dreiecksform$ . Die Determinante folgt dann aus den Diagonaleinträgen und den erfassten Zeilenoperationen.

Angenommen, wir verwenden nur Zeilenadditionen und Zeilenvertauschungen, um $A$ in eine obere Dreiecksmatrix $R$ zu überführen. Bei $p$ Zeilenvertauschungen gilt:

\det A = (-1)^p \cdot \det R

Da $R$ eine obere Dreiecksmatrix ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Deshalb:

\det A = (-1)^p \cdot r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Falls ein Algorithmus während der Elimination eine Zeile skaliert, muss dieser Skalierungsfaktor ebenfalls erfasst und aus dem Endergebnis herausgerechnet werden. In numerischen Berechnungen verwendet man üblicherweise partielle Pivotisierung, um einen Nullpivot zu vermeiden und den Einfluss von Rundungsfehlern zu verringern.

Anzahl der Operationen

Für eine dichte $n \times n$ -Matrix benötigt die Elimination oder $\mathrm{LU}$ -Zerlegung ungefähr $\frac{2}{3}n^3 + O(n^2)$ Gleitkommaoperationen. Das anschließende Multiplizieren der Diagonaleinträge erfordert nur $O(n)$ zusätzliche Arbeit. Eine naive rekursive Kofaktorentwicklung kann dagegen wie $O(n!)$ wachsen.

Bei großen unstrukturierten Matrizen wächst die Operationszahl der Elimination $kubisch$ und damit langsamer als die faktorielle Operationszahl der rekursiven Kofaktorentwicklung.

Eine Determinante dritter Ordnung durch Elimination berechnen

Das folgende Beispiel zeigt die Determinantenberechnung mit Gauß-Elimination:

A = \begin{pmatrix} 0 & 3 & 3 \\ 2 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}

$Schritt 1$ : Vertausche die Zeilen $1$ und $3$ , um einen $Pivot ungleich Null$ zu erhalten:

\begin{pmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 0 & 3 & 3 \end{pmatrix}

$Schritt 2$ : Eliminiere die erste Spalte, indem du $2$ mal Zeile $1$ von Zeile $2$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 3 & 3 \end{pmatrix}

$Schritt 3$ : Eliminiere die zweite Spalte, indem du $1{,}5$ mal Zeile $2$ von Zeile $3$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 6 \end{pmatrix} = R

Da es $einen Zeilentausch$ gibt ( $p = 1$ ):

\det A = (-1)^1 \cdot \det R

Das Rechenverfahren an die Matrixgröße anpassen

Grundlegender Fall einer Matrix erster Ordnung

Für Matrizen der Größe $1 \times 1$ ist die Determinante sehr einfach. Wenn $A \in \mathbb{R}^{1 \times 1}$ mit $A = (a_{11})$ , dann:

\det A = a_{11}

Bei einer $1\times1$ -Matrix ist die Determinante gleich ihrem $einzigen Eintrag$ . Größere Matrizen werden durch Entwicklung oder Elimination auf kleinere Fälle zurückgeführt.

Konzept der Submatrix

Betrachten wir ein Beispiel für eine $3 \times 3$ -Matrix. Angenommen, wir haben:

A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

Um die Submatrix $A_{12}$ zu erhalten, entfernen wir Zeile $1$ und Spalte $2$ :

A_{12} = \begin{pmatrix} \cancel{a_{11}} & \cancel{a_{12}} & \cancel{a_{13}} \\ a_{21} & \cancel{a_{22}} & a_{23} \\ a_{31} & \cancel{a_{32}} & a_{33} \end{pmatrix}

Für die Submatrix $A_{23}$ entfernen wir Zeile $2$ und Spalte $3$ :

A_{23} = \begin{pmatrix} a_{11} & a_{12} & \cancel{a_{13}} \\ \cancel{a_{21}} & \cancel{a_{22}} & \cancel{a_{23}} \\ a_{31} & a_{32} & \cancel{a_{33}} \end{pmatrix}

Dieser Vorgang gilt für alle Kombinationen von Zeilen und Spalten, die entfernt werden.

Kofaktorentwicklung

Die Kofaktorentwicklung berechnet die Determinante aus kleineren Minoren. Wir können nach einer beliebigen festen Zeile $i$ entwickeln:

\det A = \sum_{j=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Alternativ können wir nach einer beliebigen festen Spalte $j$ entwickeln:

\det A = \sum_{i=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Kofaktorentwicklung für eine Matrix dritter Ordnung

Für eine $3 \times 3$ -Matrix sieht die Kofaktorentwicklung beispielsweise so aus:

A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 1 \\ 1 & 2 & 0 \end{pmatrix}

Wir wählen die $erste Zeile$ zur Erweiterung:

\begin{aligned} \det A &= 2 \cdot (-1)^{1+1} \det A_{11} \\ &\quad{}+ 1 \cdot (-1)^{1+2} \det A_{12} \\ &\quad{}+ 3 \cdot (-1)^{1+3} \det A_{13} \end{aligned}

Dreieckige und diagonale Matrizen

Für eine obere Dreiecksmatrix $R$ :

R = \begin{pmatrix} r_{11} & * & \cdots & * \\ 0 & r_{22} & \cdots & * \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}

Ihre Determinante ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Für die untere Dreiecksmatrix $L$ :

L = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ * & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ * & * & \cdots & l_{nn} \end{pmatrix}

Ihre Determinante ist:

\det L = l_{11} \cdot l_{22} \cdot \ldots \cdot l_{nn}

Für eine Diagonalmatrix $D$ :

D = \begin{pmatrix} d_{11} & 0 & \cdots & 0 \\ 0 & d_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{nn} \end{pmatrix}

Ihre Determinante ist:

\det D = d_{11} \cdot d_{22} \cdot \ldots \cdot d_{nn}

Für alle drei Matrizentypen ist die Determinante gleich $dem Produkt aller Hauptdiagonalelemente$ .

Elementarmatrizen

Elementarmatrizen sind Matrizen, die aus der Identitätsmatrix mit einer elementaren Zeilenoperation erhalten werden. Die Determinanten elementarer Matrizen haben leicht zu berechnende Werte:

$Zeilenskalierungsmatrix$ $S_i(\lambda)$ , mit $\lambda \neq 0$ , die Zeile $i$ mit $\lambda$ multipliziert:

$\det S_i(\lambda) = \lambda$
$Zeilenvertauschungsmatrix$ $Q_i^j$ , die die Zeilen $i$ und $j$ vertauscht:

$\det Q_i^j = -1$
$Transvektionsmatrix$ $P_i^j(\lambda)$ , die die Operation $R_i \leftarrow R_i + \lambda R_j$ ausführt:

$\det P_i^j(\lambda) = 1$

Gaußsche Eliminierung zur Determinantenberechnung

Angenommen, wir verwenden nur Zeilenadditionen und Zeilenvertauschungen, um $A$ in eine obere Dreiecksmatrix $R$ zu überführen. Bei $p$ Zeilenvertauschungen gilt:

\det A = (-1)^p \cdot \det R

Da $R$ eine obere Dreiecksmatrix ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Deshalb:

\det A = (-1)^p \cdot r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Anzahl der Operationen

Bei großen unstrukturierten Matrizen wächst die Operationszahl der Elimination $kubisch$ und damit langsamer als die faktorielle Operationszahl der rekursiven Kofaktorentwicklung.

Eine Determinante dritter Ordnung durch Elimination berechnen

Das folgende Beispiel zeigt die Determinantenberechnung mit Gauß-Elimination:

A = \begin{pmatrix} 0 & 3 & 3 \\ 2 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}

$Schritt 1$ : Vertausche die Zeilen $1$ und $3$ , um einen $Pivot ungleich Null$ zu erhalten:

\begin{pmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 0 & 3 & 3 \end{pmatrix}

$Schritt 2$ : Eliminiere die erste Spalte, indem du $2$ mal Zeile $1$ von Zeile $2$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 3 & 3 \end{pmatrix}

$Schritt 3$ : Eliminiere die zweite Spalte, indem du $1{,}5$ mal Zeile $2$ von Zeile $3$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 6 \end{pmatrix} = R

Da es $einen Zeilentausch$ gibt ( $p = 1$ ):

\det A = (-1)^1 \cdot \det R