What is the Inverse of a Permutation Vector?

The inverse of a permutation vector is another permutation vector that effectively "undoes" the rearrangement performed by the original vector. When the original permutation is composed with its inverse, the result is the identity permutation, where all elements return to their initial positions. This aligns with the fundamental definition of an inverse permutation: "The inverse of a permuations σ is a permuatation σ-1 such that when σ is composed with σ-1 and vice versia, the result is the identity permuation."

Understanding Permutation Vectors

A permutation vector is a common way to represent a permutation, which is essentially a rearrangement of elements. For a set of n elements, a permutation vector is typically a sequence of n distinct numbers from 1 to n (or 0 to n-1, depending on whether 1-based or 0-based indexing is used).

Let's consider a 1-based index system for clarity. If you have an original sequence of elements at positions 1, 2, ..., n, a permutation vector P = [p₁, p₂, ..., pₙ] means that the element originally at position i is moved to position pᵢ.

For example, if you start with elements A, B, C at positions 1, 2, 3, and the permutation vector is P = [2, 3, 1]:

• The element at position 1 (A) moves to position P[1] = 2.
• The element at position 2 (B) moves to position P[2] = 3.
• The element at position 3 (C) moves to position P[3] = 1.

The elements are now arranged as C, A, B at positions 1, 2, 3 respectively.

The Inverse Permutation Concept

The inverse permutation reverses this process. If the original permutation moved an element from position i to position j, the inverse permutation moves the element at position j back to the original position i.

As stated in the definition, composing a permutation with its inverse yields the identity permutation. The identity permutation vector for n elements is simply [1, 2, ..., n], meaning every element stays in its original position.

If P maps position i to j (i.e., P[i] = j), then the inverse permutation vector P⁻¹ maps position j back to i (i.e., P⁻¹[j] = i).

Finding the Inverse Permutation Vector

To find the inverse permutation vector P⁻¹ from a given permutation vector P of length n (using 1-based indexing from 1 to n):

1. Create a new vector P⁻¹ of length n.
2. Initialize P⁻¹ with placeholder values (e.g., zeros).
3. Iterate through the original vector P using an index i from 1 to n. This i represents the original position.
4. Look at the value P[i]. This value, let's call it j, is the new position where the element from i goes.
5. In the inverse vector P⁻¹, the value at the new position j should be the original position i. So, set P⁻¹[j] = i.

After iterating through all i from 1 to n, the resulting P⁻¹ vector will contain the inverse permutation.

Example

Let's find the inverse of the permutation vector P = [2, 3, 1] for n=3 elements.

We want to find P⁻¹ = [q₁, q₂, q₃] such that if P[i] = j, then P⁻¹[j] = i.

Original Position (i)	New Position (j = P[i])	Inverse Mapping (P⁻¹[j] = i)
1	P[1] = 2	P⁻¹[2] = 1
2	P[2] = 3	P⁻¹[3] = 2
3	P[3] = 1	P⁻¹[1] = 3

Building the inverse vector P⁻¹ = [q₁, q₂, q₃] from the inverse mappings:

• The value at position 1 in P⁻¹ (q₁) is 3.
• The value at position 2 in P⁻¹ (q₂) is 1.
• The value at position 3 in P⁻¹ (q₃) is 2.

So, the inverse permutation vector P⁻¹ is [3, 1, 2].

If you apply P then P⁻¹, or P⁻¹ then P, you get the identity [1, 2, 3], confirming [3, 1, 2] is indeed the inverse of [2, 3, 1].