Proof of Adjugate Formula for the Matrix Inverse

We work directly from the permutation definition of the determinant and the definitions of minors, cofactors, and the adjugate, to establish $A\cdot\operatorname{adj}(A)=(\det A)\,I_n$ and $\operatorname{adj}(A)\cdot A=(\det A)\,I_n$; uniqueness of the matrix inverse then gives $A^{-1}=\tfrac{1}{\det A}\operatorname{adj}(A)$.

Setup. For $j,l\in\{1,\dots,n\}$ let $\phi_j:\{1,\dots,n\}\setminus\{j\}\to\{1,\dots,n-1\}$ be the unique order-preserving bijection ($\phi_j(i')=i'$ for $i'<j$ and $\phi_j(i')=i'-1$ for $i'>j$), and define $\psi_l:\{1,\dots,n\}\setminus\{l\}\to\{1,\dots,n-1\}$ analogously. Given $\sigma\in S_n$ with $\sigma(j)=l$, define the induced permutation $\hat{\sigma}\in S_{n-1}$ by $\hat{\sigma}=\psi_l\circ\sigma|_{\{1,\dots,n\}\setminus\{j\}}\circ\phi_j^{-1}$.

Lemma A (sign relation). For $\sigma\in S_n$ with $\sigma(j)=l$, $\operatorname{sgn}(\sigma)=(-1)^{j+l}\operatorname{sgn}(\hat{\sigma})$.

Proof. By the sign definition, $\operatorname{sgn}(\sigma)=(-1)^{N(\sigma)}$ where $N(\sigma)$ counts inversions. Partition the inversions of $\sigma$:

(a) Pairs $(i_1,i_2)$ with $i_1<i_2$ and $i_1,i_2\ne j$: since $\phi_j$ and $\psi_l$ are order-preserving, these biject with inversions of $\hat{\sigma}$, contributing $N(\hat{\sigma})$ to $N(\sigma)$.

(b) Pairs involving $j$: the count of $i_1<j$ with $\sigma(i_1)>l$ plus the count of $i_2>j$ with $\sigma(i_2)<l$. Let $c$ be the number of $i'<j$ with $\sigma(i')<l$. Since $\sigma$ is a bijection with $\sigma(j)=l$, exactly $l-1$ elements of $\{1,\dots,n\}\setminus\{j\}$ satisfy $\sigma(i')<l$ (namely the $l-1$ values in $\{1,\dots,l-1\}$). So the count in (b) is $(j-1-c)+(l-1-c)=j+l-2-2c$.

Hence $N(\sigma)=N(\hat{\sigma})+j+l-2-2c\equiv N(\hat{\sigma})+j+l\pmod{2}$, giving $\operatorname{sgn}(\sigma)=(-1)^{j+l}\operatorname{sgn}(\hat{\sigma})$. \qquad$\square$

Lemma B (Laplace expansion along row $j$). $\det A=\sum_{l=1}^{n}a_{jl}\,(-1)^{j+l}\,M_{jl}(A)=\sum_{l=1}^n a_{jl}\,C_{jl}(A)$.

Proof. Group the determinant sum by the value $l=\sigma(j)$:

$$\det A=\sum_{l=1}^n\,a_{jl}\sum_{\substack{\sigma\in S_n\\\sigma(j)=l}}\operatorname{sgn}(\sigma)\prod_{i'\ne j}a_{i',\sigma(i')}.$$

For fixed $l$, the assignment $\sigma\mapsto\hat{\sigma}$ is a bijection from $\{\sigma\in S_n:\sigma(j)=l\}$ to $S_{n-1}$. By Lemma A, $\operatorname{sgn}(\sigma)=(-1)^{j+l}\operatorname{sgn}(\hat{\sigma})$, and substituting $i'=\phi_j^{-1}(m)$ gives $\prod_{i'\ne j}a_{i',\sigma(i')}=\prod_{m=1}^{n-1}a_{\phi_j^{-1}(m),\,\psi_l^{-1}(\hat{\sigma}(m))}$. Summing over $S_{n-1}$ yields

$$\sum_{\substack{\sigma\in S_n\\\sigma(j)=l}}\operatorname{sgn}(\sigma)\prod_{i'\ne j}a_{i',\sigma(i')}=(-1)^{j+l}\sum_{\hat{\tau}\in S_{n-1}}\operatorname{sgn}(\hat{\tau})\prod_{m=1}^{n-1}a_{\phi_j^{-1}(m),\,\psi_l^{-1}(\hat{\tau}(m))}=(-1)^{j+l}M_{jl}(A),$$

where the last equality is the determinant definition applied to the submatrix $A^{(jl)}$ (rows $\{1,\dots,n\}\setminus\{j\}$, columns $\{1,\dots,n\}\setminus\{l\}$, reindexed via $\phi_j^{-1}$ and $\psi_l^{-1}$). Therefore $\det A=\sum_{l=1}^n a_{jl}(-1)^{j+l}M_{jl}(A)=\sum_{l=1}^n a_{jl}C_{jl}(A)$. \qquad$\square$

Lemma C (equal rows give zero determinant). If $B=(b_{i'k})$ is an $n\times n$ real matrix with rows $i\ne j$ identical ($b_{ik}=b_{jk}$ for all $k$), then $\det B=0$.

Proof. Assume $i<j$. The transposition $(i\;j)\in S_n$ (swapping $i$ and $j$, fixing all others) has inversions: the pair $(i,j)$; the pairs $(i,k)$ for each $k\in\{i+1,\dots,j-1\}$ (since $(i\;j)(i)=j>k=(i\;j)(k)$); and the pairs $(k,j)$ for each $k\in\{i+1,\dots,j-1\}$ (since $(i\;j)(k)=k>i=(i\;j)(j)$). Thus $N((i\;j))=1+2(j-i-1)=2(j-i)-1$, which is odd, so $\operatorname{sgn}((i\;j))=-1$ by the sign definition.

Pair each $\sigma\in S_n$ with $\sigma'=\sigma\circ(i\;j)$. Since $(i\;j)^2=\mathrm{id}$ and $i\ne j$, this is a fixed-point-free involution on $S_n$. For each pair: \begin{itemize} \item $\operatorname{sgn}(\sigma')=\operatorname{sgn}(\sigma)\cdot\operatorname{sgn}((i\;j))=-\operatorname{sgn}(\sigma)$. \item Substituting $i''=(i\;j)(i')$: $\prod_{i'}b_{i',\sigma'(i')}=\prod_{i'}b_{i',\sigma((i\;j)(i'))}=\prod_{i''}b_{(i\;j)(i''),\sigma(i'')}$. Since $b_{ik}=b_{jk}$ for all $k$, replacing $(i\;j)(i'')$ by $i''$ in each factor gives $\prod_{i''}b_{i'',\sigma(i'')}$. \end{itemize} So each pair $(\sigma,\sigma')$ contributes $(\operatorname{sgn}(\sigma)+\operatorname{sgn}(\sigma'))\prod_{i''}b_{i'',\sigma(i'')}=0$ to $\det B$, giving $\det B=0$. \qquad$\square$

Main identity. By the adjugate definition, $(\operatorname{adj}(A))_{lj}=C_{jl}(A)$, so

$$(A\cdot\operatorname{adj}(A))_{ij}=\sum_{l=1}^n a_{il}\,C_{jl}(A).$$

Case $i=j$: Lemma B with row $j=i$ gives $\sum_{l=1}^n a_{il}C_{il}(A)=\det A$.

Case $i\ne j$: Let $B$ be obtained from $A$ by replacing row $j$ with row $i$ (set $b_{i'k}=a_{i'k}$ for $i'\ne j$ and $b_{jk}=a_{ik}$). Since rows other than $j$ are unchanged, deleting row $j$ and any column $l$ from $B$ yields the same submatrix as from $A$, so $C_{jl}(B)=C_{jl}(A)$ for all $l$. Applying Lemma B to $B$ along row $j$:

$$\sum_{l=1}^n a_{il}C_{jl}(A)=\sum_{l=1}^n b_{jl}C_{jl}(B)=\det B.$$

Since $i\ne j$, rows $i$ and $j$ of $B$ are both equal to row $i$ of $A$, so Lemma C gives $\det B=0$.

Therefore $(A\cdot\operatorname{adj}(A))_{ij}=\delta_{ij}\det A$, i.e., $A\cdot\operatorname{adj}(A)=(\det A)\,I_n$.

An analogous argument applied to columns establishes $\operatorname{adj}(A)\cdot A=(\det A)\,I_n$: one groups the determinant sum by the preimage $\sigma^{-1}(i)=l$ (equivalently $\sigma(l)=i$), derives the corresponding sign relation, and pairs each $\sigma$ with $(i\;j)\circ\sigma$ to show that equal-column matrices have determinant zero.

Since $\det A\ne 0$, dividing gives $A\cdot\tfrac{1}{\det A}\operatorname{adj}(A)=I_n$ and $\tfrac{1}{\det A}\operatorname{adj}(A)\cdot A=I_n$. By uniqueness of the matrix inverse, $A^{-1}=\tfrac{1}{\det A}\operatorname{adj}(A)$.

Reading off the $(i,j)$ entry: $(A^{-1})_{ij}=\tfrac{1}{\det A}(\operatorname{adj}(A))_{ij}=\dfrac{C_{ji}(A)}{\det A}$, which is a polynomial in the entries of $A$ divided by $\det A$.