Mathwords logoMathwords

Inverse Permutation — Definition, Formula & Examples

An inverse permutation is a permutation that undoes the effect of another permutation, restoring elements to their original positions. If a permutation sends element ii to position σ(i)\sigma(i), the inverse permutation sends the element at position σ(i)\sigma(i) back to position ii.

Given a permutation σ\sigma of the set {1,2,…,n}\{1, 2, \ldots, n\}, the inverse permutation σ−1\sigma^{-1} is the unique permutation satisfying σ−1(σ(i))=i\sigma^{-1}(\sigma(i)) = i and σ(σ−1(i))=i\sigma(\sigma^{-1}(i)) = i for all i∈{1,2,…,n}i \in \{1, 2, \ldots, n\}. Equivalently, if σ(i)=j\sigma(i) = j, then σ−1(j)=i\sigma^{-1}(j) = i.

How It Works

To find the inverse of a permutation written in two-line notation, swap the two rows and then reorder the columns so the top row is in ascending order. In one-line notation, if σ=[σ(1),σ(2),…,σ(n)]\sigma = [\sigma(1), \sigma(2), \ldots, \sigma(n)], you construct σ−1\sigma^{-1} by placing ii in position σ(i)\sigma(i). The composition of a permutation with its inverse always yields the identity permutation, which maps every element to itself.

Worked Example

Problem: Find the inverse of the permutation σ=[3,1,4,2]\sigma = [3, 1, 4, 2] on the set {1,2,3,4}\{1, 2, 3, 4\}.
Step 1: Write the permutation in two-line notation, with inputs on top and outputs on the bottom.
σ=(12343142)\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}
Step 2: Swap the two rows so that outputs become inputs.
(31421234)\begin{pmatrix} 3 & 1 & 4 & 2 \\ 1 & 2 & 3 & 4 \end{pmatrix}
Step 3: Reorder the columns so the top row is in ascending order (1, 2, 3, 4).
σ−1=(12342413)\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}
Answer: The inverse permutation is σ−1=[2,4,1,3]\sigma^{-1} = [2, 4, 1, 3]. You can verify: σ\sigma sends 1→3, so σ−1\sigma^{-1} sends 3→1. Similarly, 2→4→2, 3→1→3, and 4→2→4.

Why It Matters

Inverse permutations arise in cryptography when decoding ciphers that scramble character positions. In abstract algebra, the existence of inverses is one of the axioms that makes the set of all permutations on nn elements form a group (the symmetric group SnS_n), a structure central to modern algebra and physics.

Common Mistakes

Mistake: Reversing the one-line notation (writing it backward) instead of properly computing the inverse.
Correction: The reverse of [3,1,4,2][3, 1, 4, 2] is [2,4,1,3][2, 4, 1, 3] — but only by coincidence would that be correct. Instead, systematically place ii into position σ(i)\sigma(i): since σ(1)=3\sigma(1)=3, put 1 in position 3 of σ−1\sigma^{-1}, and so on.