How can I find the inverse of a permutation?

Question

My question is, how can the inverse of $5 9 1 8 2 6 4 7 3$ be $3 5 9 7 1 6 8 4 2$? At first glance, 1 and 2 are both less than 3, for example, which seems to conflict with the instruction "then sorting the columns into increasing order". Is this not a total order over the natural numbers?

The reader should not confuse inversions of a permutation with the inverse of a permutation. Recall that we can write a permutation in two-line form $$\left(\begin{matrix} 1 & 2 & 3 & \cdots & n\\ a_1 & a_2 & a_3 & \cdots & a_n \end{matrix}\right)$$ the inverse $a'^1a'^2a'^3 ... a'^n$ of this permutation is the permutation obtained by interchanging the two rows and then sorting the columns into increasing order of the new top row: $$\left(\begin{matrix} a_1 & a_2 & a_3 & \cdots & n\\ 1 & 2 & 3 & \cdots & n \end{matrix}\right)=\left(\begin{matrix} 1 & 2 & 3 & \cdots & n\\ a'_1 & a'_2 & a'_3 & \cdots & a'_n \end{matrix}\right) $$ For example, the inverse of $5 9 1 8 2 6 4 7 3$ is $3 5 9 7 1 6 8 4 2$, since

$$\left(\begin{matrix} 5 & 9 & 1 & 8 & 2 & 6 & 4 & 7 & 3\\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{matrix}\right)=\left(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 3 & 5 & 9 & 7 &1 & 6 & 8 & 4 & 2 \end{matrix}\right) $$

— Knuth, Donald. The Art of Computer Programming: Sorting and Searching. Vol. 3, Second Edition.

Answer 1

The last step is to sort the columns $j\choose i_j$ in increasing order such that the column $1\choose i_1$ comes first, then comes $2\choose i_2$ and so on. Indeed, the wording is a bit misleading. The column $j\choose i_j$ stands for the assignment $j\mapsto i_j$ (here in the inverse permutation).

Answer 2

Given permutation is: 591826473 To get the inverse of this first write down the position of 1 It is in the 3rd position . SO inverse starts as "3 ...". Next locate 2 in the permutation. It is in the 5th position. So inverse expands to "35...." Similarly go on chasing 3,4 etc and note down their positions and build the inverse permutation.

Answer 3

For some general theory see

$\quad$ Converse relation of a function

Let $\bar 9 = \{1,2,3,4,5,6,7,8,9\}$ and observe that this set comes equipped with a natural ordering.

The permutation $\rho = | \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$ in $S_9$, by definition (compact notation), has graph

$\quad G_{\rho} = \{\,(n, n^{th} \text{ spot in } | \; 5\,9\,1\,8\,2\,6\,4\,7\,3 \; |) \mid n \in \bar 9 \, \} $

Also, $\rho^{-1} = {G_{\rho}}^{-1}$.

Since $1$ is in spot $3$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,?\,?\,?\,?\,?\,?\,?\,? \; |$;
Since $2$ is in spot $5$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,5\,?\,?\,?\,?\,?\,?\,? \; |$;
$\dots$
Since $9$ is in spot $2$ of $| \;5\,9\,1\,8\,2\,6\,4\,7\,3 \; |$, $\; \rho^{-1} = | \;3\,5\,9\,7\,1\,6\,8\,4\,2 \; |$ and done.