4
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Seems like a perfectly serviceable answer to me @Leucippus $\endgroup$
    – epimorphic
    Commented Nov 15, 2023 at 19:44
1
$\begingroup$

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=Msorted

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:

  1. MN1=[A B C D E]

where

  1. [0 1 2 3 4]*N1=M1

And

  1. M1N2=[0 1 2 3 4]

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,

[0 1 2 3 4]*N1N2=[0 1 2 3 4]

So

N1N2=I

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .