\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\inv}{\rm inv} \newcommand{\sgn}{\rm sgn} \)

Sei $A \in \R^{n \times n}$ eine quadratische Matrix. Die Determinante von $A$ ist definiert als

\begin{align} \det(A) := \sum_{\pi \in S_n}\sgn(\pi) \prod_{i=1}^n A_{i, \pi(i)} \label{def-det} \end{align}

Hierbei bezeichnet $S_n$ die Menge aller $n!$ Permutationen der Menge $[n]$. Das Vorzeichen $\sgn(\pi)$ ist definiert als $(-1)^{{\rm inv}(\pi)}$, wobei ${\rm inv}(\pi) := \left| \left\{ 1 \leq i \lt j \leq n \ | \ \pi(i) \gt \pi(j) \right\} \right|$, also die Anzahl aller Index-Paare, die von $\pi$ in ihrer Reihenfolge vertauscht werden.

Beobachtung Sei $\tau \in S_n$ eine Transposition, also $\tau(k) = l$, $\tau(l) = k$, und $\tau(i) = i$ für alle $i \in [n] \setminus \{k,l\}$. Zeigen Sie: $\sgn(\pi \circ \tau) = - \sgn(\pi)$. Insbesondere: $\inv(\pi \circ \tau) - \inv(\pi) \in \{-1, +1\}$.

Anmerkung: $\pi \circ \tau$ ist wie $\pi$, nur die Stellen $k$ und $l$ vertauscht (nicht die Werte). Zum Beispiel

\begin{align*} \left(\begin{array}{cc}1&2&3&4&5 \\ \hline 4&1&2&5&3\end{array}\right) \ \circ \ \left(\begin{array}{cc}1&2&3&4&5 \\ \hline 1 & 5 & 3 & 4 & 2\end{array}\right) \ = \ \left(\begin{array}{cc}1&2&3&4&5 \\ \hline 4&3&2&5&1\end{array}\right) \end{align*}

Daraus ergibt sich direkt, dass Vertauschen zweier Zeilen von $A$ den Wert von $\det(A)$ mit $-1$ multipliziert. Das wiederum heißt, dass $\det(A)=0$ gilt, wenn zwei Zeilen in $A$ gleich sind. Der Ausdruck (\ref{def-det}) ist linear in den Einträgen der ersten Zeile (bzw. jeder einzelnen Zeile). Daher gilt:

\begin{align*} \det\left( \begin{bmatrix}a_1^T + b_1^T \\ a_2^T \\ \vdots \\ a_n^T \end{bmatrix} \right) = \det\left( \begin{bmatrix}a_1^T \\ a_2^T \\ \vdots \\ a_n^T \end{bmatrix} \right) + \det\left( \begin{bmatrix} b_1^T \\ a_2^T \\ \vdots \\ a_n^T \end{bmatrix} \right) \ . \end{align*}

Woraus wiederum folgt:

\begin{align*} \det\left( \begin{bmatrix}a_1^T \\ a_2^T \\ \vdots \\ a_n^T \end{bmatrix} \right) = \det\left( \begin{bmatrix}a_1^T + \lambda a_2^T \\ a_2^T \\ \vdots \\ a_n^T \end{bmatrix} \right) \ . \end{align*}

In meinem Beispiel haben ich die Zeilen 1 und 2 genommen. Es geht aber analog mit zwei beliebigen Zeilen. Das heißt: wir können Gaussche Eliminierung betreiben und nach polynomiell vielen Schritt folgende Gleichung herleiten:

\begin{align*} \det(A) & = \pm \begin{bmatrix} c_{11} & c_{12} & c_{13} & \dots & c_{1n} \\ 0 & c_{22} & c_{23} & \dots & c_{2n} \\ 0 & 0 & c_{33}& \dots & c_{3n} \\ \vdots & & & \ddots \\ 0 & 0 & \dots & & c_{nn} \end{bmatrix} \end{align*}

Die Determinante der rechten Matrix ist einfach zu sehen: nur eine Permutation $\pi \in S_n$ weicht jeder $0$ aus, nämlich die Identität, und somit ist die Determinante $c_{11} \cdot c_{22} \cdot \cdots \cdot c_{nn}$. Wir können $\det(A)$ also in polynomieller Zeit berechnen; dabei ist allerdings Vorsicht geboten: wenn man naiv vorgeht, kann die Bitkomplexität der involvieren Zahlen sehr groß werden.