Proof of Leibniz formula from Laplace expansion 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!
 A: 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

*

*given a fixed $i$, as $\sigma$ runs through all the permutations in $S_n$, $\tau_{\sigma}$ also run through all the permutations in $S_{n+1}$ which map $i$ to $n+1$.

*$\tau_{\sigma}=\sigma(n+1, n, \cdots, i+1, i)=\sigma(n+1, i)(n+1, i+1)\cdots (n+1, n)$. Hence, $\text{sgn }\tau_{\sigma}=\text{sgn }\sigma \cdot (-1)^{n+1-i}$ and $(-1)^{i+n+1}\text{sgn }\sigma=\text{sgn }\tau_{\sigma}$.

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*}
