Determinant/Leibniz formula/Fact/Proof

Proof

We do induction over ${}n\geq 1$, the base case is clear, so let ${}n\geq 2$. The set of permutations ${}\pi \in S_{n}$ can be split up, by sorting along ${}\pi (1)$, and considering the bijective mappings

$\pi {|}_{\{2,\ldots ,n\}}\colon \{2,\ldots ,n\}\longrightarrow \{1,\ldots ,n\}\setminus \{i\}$

as a permutation ${}\rho$ on ${}\{1,\ldots ,n-1\}$, by both sets in an order-preserving way with ${}\{1,\ldots ,n-1\}$. This yields a bijection ${}S_{n,i}\cong S_{n-1}$, where ${}S_{n,i}$ denotes the set of permutations on ${}\{1,\ldots ,n\}$ which send ${}1$ to ${}i$. Between the signs, there is the relation

${}\operatorname {sgn} (\pi )=(-1)^{i-1}\operatorname {sgn} (\rho )=(-1)^{i+1}\operatorname {sgn} (\rho )\,,$

since we need ${}i-1$ transpositions to put the ${}i$-th place to the first place. Altogether, there is a natural bijection

${}S_{n}=\biguplus _{i\in \{1,\ldots ,n\}}S_{n,i}=\biguplus _{i\in \{1,\ldots ,n\}}S_{n-1}\,.$

Hence, we get

${}{\begin{aligned}\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )a_{1\pi (1)}\cdots a_{n\pi (n)}&=\sum _{i=1}^{n}\sum _{\pi \in S_{n,i}}\operatorname {sgn} (\pi )\prod _{j=1}^{n}a_{j\pi (j)}\\&=\sum _{i=1}^{n}a_{1i}\sum _{\pi \in S_{n,i}}\operatorname {sgn} (\pi )\prod _{j=2}^{n}a_{j\pi (j)}\\&=\sum _{i=1}^{n}a_{1i}\sum _{\rho \in S_{n-1}}(-1)^{i+1}\operatorname {sgn} (\rho )\prod _{k=1}^{n-1}(M_{1i})_{k\rho (k)}\\&=\sum _{i=1}^{n}(-1)^{i+1}a_{1i}\det M_{1i}\\&=\det M.\end{aligned}}$

Here, ${}M_{1i}$ is the submatrix in which the first row and the ${}i$-th column is omitted. For the penultimate equation, we use the induction hypothesis, and the last equation rests on Laplace expansion with respect to the first row.

To fact