Determinant/Leibniz formula/Fact/Proof

{{ Mathematical text/Proof |Text= {{ Proofstructure |Strategy= |Notation= |Proof= We do induction over ${\displaystyle {}n\geq 1}$, the base case is clear, so let ${\displaystyle {}n\geq 2}$. The set of permutations ${\displaystyle {}\pi \in S_{n}}$ can be split up, by sorting along ${\displaystyle {}\pi (1)}$, and considering the bijective mappings {{ Mapping/display |name= \pi {{|}}_{ \{2 , \ldots , n\} } |\{2 , \ldots , n\} | \{1 , \ldots , n\} \setminus \{i\} || |pm= }} as a permutation ${\displaystyle {}\rho }$ on ${\displaystyle {}\{1,\ldots ,n-1\}}$, by both sets in an order-preserving way with ${\displaystyle {}\{1,\ldots ,n-1\}}$. This yields a bijection ${\displaystyle {}S_{n,i}\cong S_{n-1}}$, where ${\displaystyle {}S_{n,i}}$ denotes the set of permutations on ${\displaystyle {}\{1,\ldots ,n\}}$ which send ${\displaystyle {}1}$ to ${\displaystyle {}i}$. Between the signs, there is the relation

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

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

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

Hence, we get

${\displaystyle {}{\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, ${\displaystyle {}M_{1i}}$ is the submatrix in which the first row and the ${\displaystyle {}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. |Closure= }} |Textform=Proof |Category=See }}