How to efficiently (fast) calculate the transpose of a *permutation matrix* in Python3?
Perhaps only marginally, but the readability of your code can be improved by using enumerate and the reverse=True flag in sorted.

def transpose_r(ls): 
    return [len(ls)-1-k
            for k, Pk in sorted(enumerate(ls), 
                                reverse=True, 
                                key=itemgetter(1))]


If we index starting from the left, then this is further simplified.

def transpose_l(ls): 
    return [x for x, Px in sorted(enumerate(ls), key=itemgetter(1))]




The transpose has the funny property that transpose(ls)[ls[j]] == j. We can use this to build the transpose without sorting.

def transpose_l(ls):
    tr_ls = [0]*len(ls)

    for l in ls:
        tr_ls[ls[l]] = l

    return tr_ls

def transpose_r(ls):
    n = len(ls)
    tr_ls = [0]*n

    for l in ls:
        tr_ls[n - 1 - ls[l]] = n - 1 - l

    return tr_ls


Alternatively, we can use enumerate again.

def transpose_l(ls):
    tr_ls = [0]*len(ls)

    for ix, l in enumerate(ls):
        tr_ls[l] = ix

    return tr_ls

def transpose_r(ls):
    n = len(ls)
    tr_ls = [0]*n

    for ix, l in enumerate(ls):
        tr_ls[n - 1 - l] = n - 1 - ix

    return tr_ls