I'm trying to prove Leibniz formula for the determinant using Laplace expansion. Here's my attempt:
For a $1 \times 1$ matrix $A = \begin{pmatrix}a_{11}\end{pmatrix}$, define $\det A = a_{11}$. For any $n \times n$ matrix $A$, define $\det A$ recursively according to the formula $$ \det A = \sum_{j=1}^n [A]_{1j} (-1)^{j+1}\det A_{1j} $$ where $A_{ij}$ is the matrix obtained from deleting the $i$-th row and $j$-th column of $A$, and $[A]_{ij}$ is the $i,j$-th entry of $A$.
Claim: For any finite set $A$, let $P(A)$ denote the set of all permutations of the elements of $A$.
Then
$$
\det A = \sum_{\sigma \in P(\{1,\cdots, n\})} \left(\text{sgn} \, \sigma \prod_{i=1}^n [A]_{i \sigma(i)} \right)
$$
where $\text{sgn} \, \sigma$ is the sign of the permutation $\sigma = (\sigma(1), \cdots, \sigma(n))$.
Proof: The claim is trivial when $n = 1$.
Suppose the claim is true for all $n \times n$ matrices. Let $A$ be an $(n+1) \times (n+1)$ matrix. Then \begin{align} \det A &= \sum_{j=1}^{n+1} [A]_{1j} (-1)^{j+1}\det A_{1j} \\ &= \sum_{j=1}^{n+1} [A]_{1j} (-1)^{j+1}\sum_{\sigma \in P(\{1,\cdots, n\})} \left(\text{sgn} \, \sigma \prod_{i=1}^n [A_{1j}]_{i \sigma(i)} \right) \\ &= \sum_{j=1}^{n+1} \sum_{\sigma \in P(\{1,\cdots, n\})} (-1)^{j+1} \text{sgn} \, \sigma \cdot \left(\,[A]_{1j} \prod_{i=1}^n [A_{1j}]_{i \sigma(i)} \right) \end{align} where the second equality follows from the induction hypothesis.
For each $\sigma \in P(\{1,\cdots, n\})$, define a permutation $\sigma^j \in P(\{1,\cdots, j-1,j+1,\cdots,n+1\})$ where the $i$-th element of $\sigma^j$ is the $\sigma(i)$-th element of the list $\{1,\cdots, j-1,j+1,\cdots,n+1\}$. Also define $\rho^j = (j,\sigma^j) \in P(\{1, \cdots, n+1\})$. (The dependence of $\sigma^j$ and $\rho^j$ on $\sigma$ is suppressed for notational clarity.) Observe that it takes $j - 1$ transpositions to turn the list $(1, \cdots, n+1)$ into $(j,1 ,\cdots, j-1, j+1, \cdots, n+1\}$ and then $\text{sgn } \sigma$ more transpositions to turn this list into $(j, \sigma^j)$. Thus $\text{sgn } \rho^j = (-1)^{j-1} \text{sgn } \sigma = (-1)^{j+1} \text{sgn } \sigma$. Also observe that $[A_{1j}]_{i \sigma(i)} = [A]_{i+1,\sigma^j(i)}$. Plugging into the previous expression, we have
\begin{align} \det A &= \sum_{j=1}^{n+1} \sum_{\sigma \in P(\{1,\cdots, n\})} \text{sgn} \, \rho^j \cdot \left(\, [A]_{1j} \prod_{i=1}^n [A]_{i+1, \sigma^j(i)} \right) \\ &= \sum_{j=1}^{n+1} \sum_{\sigma \in P(\{1,\cdots, n\})} \text{sgn} \, \rho^j \cdot \left(\, \prod_{i=1}^{n+1} [A]_{i \rho^j(i)} \right) \end{align} The result then follows because every $\rho \in P(\{1, \cdots, n+1\})$ can be uniquely written as $\rho = (j, \sigma^j)$ for some $j$ and $\sigma$.
Does this make sense/easy to follow? Is there a way to be more tidy/elegant? Thanks!
I review my previous answer which was posted 4 years ago and improve it. Here, we use the expansion along the last column of $A$. Which makes the notations simpler.
\begin{eqnarray*} \det{A} &=& \sum_{i=1}^{n+1}(-1)^{i+n+1}[A]_{i,n+1}\det{A_{i,n+1}} \\ &=& \sum_{i=1}^{n+1}(-1)^{i+n+1}[A]_{i,n+1}\sum_{\sigma\in S_n}\text{sgn }\sigma\prod_{j=1}^{n}[A_{i,n+1}]_{j,\sigma(j)} \\ &=& \sum_{i=1}^{n+1}(-1)^{i+n+1}[A]_{i,n+1}\sum_{\sigma\in S_n}\text{sgn }\sigma\left(\prod_{j=1}^{i-1}[A_{i,n+1}]_{j, \sigma(j)}\prod_{j=i}^{n}[A_{i,n+1}]_{j, \sigma(j)}\right) \\ &=& \sum_{i=1}^{n+1}(-1)^{i+n+1}[A]_{i,n+1}\sum_{\sigma\in S_n}\text{sgn }\sigma\left(\prod_{j=1}^{i-1}[A]_{j, \sigma(j)}\prod_{j=i}^{n}[A]_{j+1, \sigma(j)}\right) \\ &=& \sum_{i=1}^{n+1}\sum_{\sigma\in S_n}(-1)^{i+n+1}\text{sgn }\sigma\left(\prod_{j=1}^{i-1}[A]_{j, \sigma(j)}\cdot [A]_{i,n+1}\cdot \prod_{j=i}^{n}[A]_{j+1, \sigma(j)}\right) \\ &=& \sum_{i=1}^{n+1}\sum_{\sigma\in S_n}(-1)^{i+n+1}\text{sgn }\sigma \cdot [A]_{1, \sigma(1)}[A]_{2, \sigma(2)}\cdots [A]_{i-1, \sigma(i-1)} \\ && \times [A]_{i, n+1}\times [A]_{i+1, \sigma(i)}[A]_{i+2, \sigma(i+1)}\cdots [A]_{n+1, \sigma(n)} \\ &=& \star \end{eqnarray*}
For each $\sigma\in S_n$, define $\tau_{\sigma}$ as $$ \begin{matrix} [n+1] & \tau_{\sigma}\in S_{n+1} & [n+1]\\ \hline 1 & \longrightarrow & \sigma(1) \\ 2 & \longrightarrow & \sigma(2) \\ \vdots & \vdots & \vdots \\ i-1 & \longrightarrow & \sigma(i-1) \\ i & \longrightarrow & n+1 \\ i+1 & \longrightarrow & \sigma(i) \\ \vdots & \vdots & \vdots \\ n+1 & \longrightarrow & \sigma(n) \\ \end{matrix} $$
Note that
Therefore, \begin{eqnarray*} \star &=& \sum_{i=1}^{n+1}\sum_{\substack{\tau\in S_{n+1} \\ \tau(i)=n+1}}\text{sgn }\tau \prod_{j=1}^{n+1}[A]_{j, \tau(j)} \\ &=& \sum_{\tau\in S_{n+1}}\text{sgn }\tau\prod_{j=1}^{n+1}[A]_{j, \tau(j)} \end{eqnarray*}