Why does sorting twice produce a rank vector

Question

This question came up after I read this post .

There's a function numpy.argsort() that returns the indexes of the original array that would yield a sorted array. By applying this function twice you would get the rank of the original away.

Someone commented that "The first argsort returns a permutation (which if applied to the data would sort it). When argsort is applied to (this or any) permutation, it returns the inverse permutation (that if the 2 permutations are applied to each other in either order the result is the Identity). The second permutation if applied to a sorted data array would produce the unsorted data array, i.e. it is the rank."

But is there any mathematical way to explain it? I think there should be linear algebra formula to explain it.

Answer 1

OK I tried a toy example M=[D A E B C] whose rank is [3 0 4 1 2].

The rank is defined in this way:

If

M*R=M_sorted

then

[0 1 2 3 4]*R^-1 is the rank vector of M

Let's test by plugging in the toy example:

M*R = [D A E B C]*R =[A B C D E]

Therefore

R =  0 0 0 1 0 
     1 0 0 0 0
     0 0 0 0 1
     0 1 0 0 0
     0 0 1 0 0

R^-1 =  0 1 0 0 0 
        0 0 0 1 0
        0 0 0 0 1
        1 0 0 0 0
        0 0 1 0 0

Then the rank vector is

M_rank=[0 1 2 3 4]*R^-1=[3 0 4 1 2]

Indeed!!!!

Now let's prove that the sorted index of the sorted index is the rank vector:

Let's assume that M₁ is the index of M and that M₂ is the index of M₁ .

So we have these:

1. MN₁=[A B C D E]

where

2. [0 1 2 3 4]*N₁=M₁

And

3. M₁N₂=[0 1 2 3 4]

where

4. [0 1 2 3 4]*N₂=M₂

So based on Formula 1,

R=N₁

Then based on definition, the rank vector is

5. [0 1 2 3 4]*R^-1=[0 1 2 3 4]*N₁^-1

Then, what is N₁^-1 ?

Based on Formula 2 and Formula 3,

[0 1 2 3 4]*N₁N₂=[0 1 2 3 4]

So

N₁N₂=I

Therefore,

6. N₁^-1 = N₂

Plug it into Formula 5 we get the rank vector

[0 1 2 3 4]*N₂

Based on Formula 4, it is exactly M₂

Answer 2

Here is a cleaner way to explain it in simple mathematics. Let's denote the original array as $A$, the one after argsort() once as $A'$, and the final outcome after argsort() twice as $A''$.

Let's first be clear about the following statement: if $A'[i] = j$, then it means $A[j]$ is the i-th smallest element in $A$, by the definition of argsort(). Then similarly, if $A''[k] = q$, it means $A'[q]$ is the k-th smallest element in $A'$. Recall that, $A'$ actually contains the indices of $A$, therefore, the elements range from $1$ to $|A|$ (allow me to count from $1$ instead of $0$ for the sake of simplicity).

!BOOM!: That is to say the k-th smallest element in $A'$ exactly equals to $k$, i.e. $A'[q] = k$. Consequently, by the statement at the beginning, $A[k]$ is the q-th smallest element in $A$, which is saying the rank of $A[k]$ is $q$!

P.S., another more efficient way is to do it this way, to avoid sorting twice.