Computing Determinants by Cofactor Expansion

We prove the row-expansion formula for a fixed row index $i$; the column formula follows by the identical argument applied to $A^T$, using $\det A = \det A^T$ (a fact itself provable directly from the Leibniz formula by the substitution $\sigma \mapsto \sigma^{-1}$, which we invoke here as an already-established property of the permutation sum, not as a consequence of cofactor expansion, so there is no circularity).

Step 1: Group the Leibniz sum by the value $\sigma(i)$. Fix $i$. Every permutation $\sigma \in S_n$ sends $i$ to some unique value $j = \sigma(i) \in \{1,\dots,n\}$. Partition $S_n$ into the disjoint blocks

Then

where we pulled $a_{i,\sigma(i)} = a_{ij}$ out of the product since it is constant on $S_n^{(i,j)}$. It remains to show that the inner sum

equals $C_{ij} = (-1)^{i+j} M_{ij}$.

Step 2: Bijection between $S_n^{(i,j)}$ and $S_{n-1}$. Let $A(i|j)$ denote the $(n-1)\times(n-1)$ matrix obtained from $A$ by deleting row $i$ and column $j$; by definition $M_{ij} = \det A(i|j)$. Index the rows of $A(i|j)$ by $k \in \{1,\dots,n\}\setminus\{i\}$ and its columns by $\ell \in \{1,\dots,n\}\setminus\{j\}$, in their original (increasing) order, so its $(p,q)$ entry (for $p,q = 1,\dots,n-1$ in the compressed indexing) equals $a_{k,\ell}$ where $k$ is the $p$-th element and $\ell$ is the $q$-th element of the respective index sets. Given $\sigma \in S_n^{(i,j)}$, define $\tau: \{1,\dots,n\}\setminus\{i\} \to \{1,\dots,n\}\setminus\{j\}$ by $\tau(k) = \sigma(k)$ for $k \ne i$; this is well defined because $\sigma$ is a bijection sending $i \to j$, so it must send $\{1,\dots,n\}\setminus\{i\}$ bijectively onto $\{1,\dots,n\}\setminus\{j\}$. Composing with the order-preserving relabelings of $\{1,\dots,n\}\setminus\{i\}$ and $\{1,\dots,n\}\setminus\{j\}$ as $\{1,\dots,n-1\}$, we obtain a permutation $\tau' \in S_{n-1}$. The map $\sigma \mapsto \tau'$ is a bijection $S_n^{(i,j)} \to S_{n-1}$, since $\sigma$ is completely determined by $\sigma(i)=j$ together with its restriction to $\{1,\dots,n\}\setminus\{i\}$. Under this bijection,

so

where $\epsilon_{ij}$ is the constant by which $\operatorname{sgn}(\sigma)$ differs from $\operatorname{sgn}(\tau')$ (constant across the block because it depends only on $i,j$, not on the particular $\sigma$, as shown next).

Step 3: Compute the sign factor $\epsilon_{ij} = (-1)^{i+j}$. We compute $\epsilon_{ij}$ by relating $\sigma$ to $\tau'$ through explicit transpositions. First handle the case $i = j = n$: here $\sigma(n) = n$, so $\sigma$ restricted to $\{1,\dots,n-1\}$ is literally an element of $S_{n-1}$ (no relabeling needed), and $\operatorname{sgn}(\sigma) = \operatorname{sgn}(\tau')$ directly from the definition of sign via inversions restricted to $\{1,\dots,n-1\}$ (the pair $(k,n)$ for $k<n$ contributes no inversion since $\sigma(k) < n = \sigma(n)$ never holds... more precisely, since $\sigma(n)=n$ is the maximum value, no inversion involves index $n$). Hence $\epsilon_{n,n} = 1 = (-1)^{n+n}$. For general $i,j$, construct $\sigma$ from $\tau'$ (viewed, after relabeling, as a bijection $\{1,\dots,n\}\setminus\{i\} \to \{1,\dots,n\}\setminus\{j\}$) by setting $\sigma(i) = j$ and $\sigma(k) = \tau'(k)$ for $k \ne i$. We relate $\sigma$ to a permutation of the form handled above by conjugating with cyclic shifts: let $c_i \in S_n$ be the cycle $(i \; i+1 \; \cdots \; n)$, which moves position $n$ to position $i$ by a cyclic shift, i.e. $c_i$ has sign $(-1)^{n-i}$ (a cycle of length $n-i+1$ has sign $(-1)^{(n-i+1)-1} = (-1)^{n-i}$). Similarly let $d_j \in S_n$ be the cycle $(j\; j+1\;\cdots\; n)$ with sign $(-1)^{n-j}$. One checks directly that $\sigma = d_j \, \sigma_0\, c_i^{-1}$ where $\sigma_0(n) = n$ and $\sigma_0$ restricted to $\{1,\dots,n-1\}$ corresponds to $\tau'$ under the appropriate relabeling; taking signs,

using $(-1)^{2n} = 1$ and $(-1)^{-i-j} = (-1)^{i+j}$. Hence $\epsilon_{ij} = (-1)^{i+j}$ for all $i,j$, independent of the particular $\sigma \in S_n^{(i,j)}$, confirming the constant claimed in Step 2.

Step 4: Conclude. Combining Steps 1–3,

and therefore

which is exactly the row-$i$ cofactor expansion. Since $i$ was an arbitrary fixed row index, this holds for every row. For columns, apply the row result to $A^T$: the $(i,j)$ minor of $A^T$ equals the $(j,i)$ minor of $A$ (deleting row $j$, column $i$ of $A$ is the same submatrix, transposed, as deleting row $i$, column $j$ of $A^T$, and transposition does not change a determinant by the already-cited fact $\det B = \det B^T$ applied to the smaller matrices). Hence expanding $\det(A^T)$ along its row $j$ gives $\sum_i (A^T)_{ji} (-1)^{j+i} M_{ij}^{A^T\text{-minor}} = \sum_i a_{ij}(-1)^{i+j}M_{ij}$, and since $\det A^T = \det A$, this is the column-$j$ expansion of $A$. Since the right-hand side was shown equal to $\det A$ (the Leibniz sum) for every choice of $i$, and likewise for every choice of $j$, all $2n$ expansions (over $n$ rows and $n$ columns) give the same value, namely $\det A$. $\blacksquare$