Permutations and Their Signs
The determinant of a square matrix can be expressed as a sum with one term for each way of matching its rows to its columns. A permutation records such a matching: it assigns a different column to each row, using every column exactly once. Each matching contributes a product of matrix entries, and its sign determines whether that product is added or subtracted. This signed sum is the Leibniz formula.
For a positive integer \(n\), a permutation of \(\{1,\dots,n\}\) is a bijection from that set to itself. We write its values as the list \(\sigma(1),\dots,\sigma(n)\). An inversion of \(\sigma\) is a pair of positions \(i,j\) such that \(i<j\) but \(\sigma(i)>\sigma(j)\). Write \(\operatorname{inv}(\sigma)\) for the number of inversions. The permutation is even if this number is even and odd if this number is odd.
To count inversions, compare entries in different positions, not the values in isolation. For example, the list \(2,3,1\) has two inversions: \(2>1\) and \(3>1\). The list \(3,1,2\) also has two: \(3>1\) and \(3>2\). Both permutations are even, even though their lists differ.
Worked Example: Counting Inversions in a Permutation
Find the sign of the permutation \(\sigma\) with list \(3,1,4,2\).
There are six pairs of positions to check. The first entry, \(3\), is greater than the later entries \(1\) and \(2\), giving two inversions. The second entry, \(1\), is not greater than either later entry. The third entry, \(4\), is greater than the last entry, \(2\), giving one more inversion. The total is \(\operatorname{inv}(\sigma)=2+0+1=3\), which is odd. Therefore \(\operatorname{sgn}(\sigma)=(-1)^3=-1\).
Check: The list can be put in increasing order by swapping adjacent out-of-order entries: \(3,1,4,2\to1,3,4,2\to1,3,2,4\to1,2,3,4\). There are three swaps, consistent with the odd inversion count and sign \(-1\).
The connection between inversions and swaps is not a coincidence. Swapping adjacent entries changes the inversion count by an odd amount—in fact, by exactly one. The entries being swapped change their relative order, so their pair changes from an inversion to a non-inversion, or vice versa. For any other entry, the total number of inversions it makes with those two entries is unchanged: it remains before both, after both, or between them. Thus the parity of the inversion count flips with each adjacent swap.
Why this matters: The inversion count gives a direct, unambiguous way to find the sign of a permutation. In particular, if a permutation is sorted by repeatedly swapping adjacent out-of-order entries, each swap removes one inversion. The process ends at \(1,2,\dots,n\), which has zero inversions, so the number of swaps used has the same parity as the original inversion count. This explains why the sign records whether the permutation is even or odd.
The Leibniz Formula
Each permutation chooses exactly one entry from each row and one from each column. Its product therefore contains \(n\) entries. The sign is applied to the whole product. Since there are \(n!\) permutations, the formula has \(n!\) terms; for \(n=2\), there are only two.
The determinant has already been defined by cofactor expansion in the earlier material on determinants. The theorem above says that the permutation sum agrees with that determinant. We use the first-row cofactor expansion in the proof: if \(\mathbf{A}_{1j}\) is obtained by deleting row 1 and column \(j\), then \(\det\mathbf{A}=\sum_{j=1}^n(-1)^{1+j}a_{1j}\det\mathbf{A}_{1j}\). This standard expansion is the induction step connecting the two expressions.
Proof. We prove the formula by induction on \(n\). For \(n=1\), there is one permutation, with list \(1\), sign \(+1\), and product \(a_{11}\). The formula gives \(\det\mathbf{A}=a_{11}\), as required.
Now let \(n\geq2\), and assume the formula holds for \((n-1)\times(n-1)\) matrices. Group the permutations in the sum according to the value \(j=\sigma(1)\). For a fixed \(j\), delete the first value \(j\) from the permutation list and reduce each remaining value larger than \(j\) by 1. The resulting list is a permutation \(\tau\) of \(\{1,\dots,n-1\}\). This gives a one-to-one correspondence between permutations with \(\sigma(1)=j\) and permutations \(\tau\) on the remaining ordered rows and columns.
The inversions of \(\sigma\) among positions \(2,\dots,n\) are exactly the inversions of \(\tau\), because reducing values larger than \(j\) by 1 preserves their order. The inversions involving position 1 are exactly the entries after \(j\) that are smaller than \(j\); there are \(j-1\) of them. Consequently, $$ \operatorname{inv}(\sigma)=\operatorname{inv}(\tau)+(j-1), \qquad \operatorname{sgn}(\sigma)=(-1)^{j-1}\operatorname{sgn}(\tau)=(-1)^{1+j}\operatorname{sgn}(\tau). $$ For this fixed \(j\), the entry product is \(a_{1j}\) times the product selected by \(\tau\) from \(\mathbf{A}_{1j}\). By the induction hypothesis, the sum of these products over all \(\tau\) is \((-1)^{1+j}a_{1j}\det\mathbf{A}_{1j}\). Summing over \(j=1,\dots,n\) gives the first-row cofactor expansion, which equals \(\det\mathbf{A}\). This proves the formula for \(n\) and completes the induction. \(\square\)
Deriving the Two-by-Two Formula
For a two-by-two matrix, \(S_2\) contains just the identity permutation, with list \(1,2\), and the swap permutation, with list \(2,1\). The identity has no inversions and sign \(+1\). The swap has one inversion and sign \(-1\). The identity selects entries \(a_{11}\) and \(a_{22}\), while the swap selects \(a_{12}\) and \(a_{21}\). Therefore the Leibniz formula gives the familiar expression.
Worked Example: Reading the Two Terms
Write the Leibniz formula for \(\mathbf{A}=\begin{bmatrix}a&b\\c&d\end{bmatrix}\), identifying the permutation and sign of each term.
The identity permutation has list \(1,2\), zero inversions, and sign \(+1\). It selects \(a_{11}=a\) in row 1 and \(a_{22}=d\) in row 2, so its signed term is \(+ad\). The swap has list \(2,1\), one inversion, and sign \(-1\). It selects \(a_{12}=b\) and \(a_{21}=c\), so its signed term is \(-bc\). Adding the terms gives \(\det\mathbf{A}=ad-bc\).
Check: First-row cofactor expansion gives \(a\det[d]-b\det[c]=a d-b c\), where the determinant of a one-by-one matrix is its sole entry. The two calculations agree.
Worked Example: Evaluating a Two-by-Two Determinant
Use the permutation formula to find the determinant of \(\mathbf{B}=\begin{bmatrix}2&5\\3&7\end{bmatrix}\).
The identity permutation contributes \(+b_{11}b_{22}=+(2)(7)=14\). The swap permutation contributes \(-b_{12}b_{21}=-(5)(3)=-15\). Hence \(\det\mathbf{B}=14-15=-1\).
Check: First-row cofactor expansion gives \(2(7)-5(3)=14-15=-1\), the same value.
The index \(\sigma(i)\) is essential: it says which column is selected for row \(i\). Because \(\sigma\) is a bijection, no column is selected twice and none is omitted. The formula is not a sum over arbitrary choices of entries; it is a sum over precisely these complete row-to-column matchings.
A Common Sign Mistake
A frequent error is to give every permutation a positive sign, or to decide the sign by adding the values in its list. Neither works. For example, the list \(2,1\) has sum \(3\), but its sign is determined by its single inversion, not by that sum. If both terms in a two-by-two determinant are incorrectly added, the matrix \(\begin{bmatrix}1&2\\3&4\end{bmatrix}\) would give \(1\cdot4+2\cdot3=10\). The correct permutation signs give \(1\cdot4-2\cdot3=4-6=-2\).
Correction: Count pairs \(i<j\) for which \(\sigma(i)>\sigma(j)\), then use \((-1)^{\operatorname{inv}(\sigma)}\) on the entire term. In this example, the identity term has sign \(+1\); the swapped-column term has sign \(-1\).
The Leibniz formula is useful because it gives a single expression for determinants of every square size and makes the role of the signs explicit. For a two-by-two matrix, the two possible matchings are easy to list, so the formula reduces immediately to \(ad-bc\). For larger matrices the number of permutations grows, but the same rule still specifies every term and its sign.
Check Your Understanding
Use inversion counts to decide each sign, and keep track of which matrix entry each position selects.
- Find the inversion count and sign of the permutation with list \(2,4,1,3\).
- For the permutation with list \(3,2,1\), list all its inversions and determine its sign.
- For \(\mathbf{A}=\begin{bmatrix}4&1\\2&3\end{bmatrix}\), write the two signed Leibniz terms and evaluate the determinant.
- Explain why a permutation term uses exactly one matrix entry from every row and every column.
- In the induction proof, why are there \(j-1\) inversions involving the first position when \(\sigma(1)=j\)?
