# Why does sorting twice produce a rank vector

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.

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

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

# Mrank=[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 M1 is the index of M and that M2 is the index of M1 .

So we have these:

where

And

where

1. # [0 1 2 3 4]*N2=M2

So based on Formula 1,

# R=N1

Then based on definition, the rank vector is

1. # [0 1 2 3 4]*R-1=[0 1 2 3 4]*N1-1

Then, what is N1-1 ?

Based on Formula 2 and Formula 3,

So

Therefore,

1. # N1-1 = N2

Plug it into Formula 5 we get the rank vector

# [0 1 2 3 4]*N2

Based on Formula 4, it is exactly M2

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.

• Seems like a perfectly serviceable answer to me @Leucippus Nov 15 at 19:44