# How to efficiently (fast) calculate the transpose of a *permutation matrix* in Python3?

The permutation matrix is represented as a list of positive integers, plus zero. The number indicates the position of the 1 in that row, e.g. a number zero would mean that the 1 is in the right-most position².

My first attempt is as follows, together with a printing function to help assess the result. It seems too convoluted to me. Please note that a permutation matrix multiplication is simpler than an ordinary matrix multiplication.

def transpose(m):
"""Transpose a permutation matrix.
m: list of positive integers and zero."""
c = {}
idx = 0
for row in reversed(m):
c[-row] = idx
idx += 1

return list(map(
itemgetter(1), sorted(c.items(), reverse=False, key=itemgetter(0))
))

def print_binmatrix(m):
"""Print a permutation matrix 7x7.
m: list of positive integers and zero."""

for row in m:
print(format(2 ** row, '07b'), row)

# Usage example with a matrix 35x35. Ideally, it should scale up without sacrificing speed at smaller matrices like this.
transpose([8, 4, 21, 17, 30, 28, 1, 27, 5, 3, 16, 12, 11, 14, 20, 6, 33, 19, 22, 25, 31, 15, 13, 18, 10, 0, 7, 2, 9, 23, 24, 26, 29, 32, 34])
# Result
[25, 6, 27, 9, 1, 8, 15, 26, 0, 28, 24, 12, 11, 22, 13, 21, 10, 3, 23, 17, 14, 2, 18, 29, 30, 19, 31, 7, 5, 32, 4, 20, 33, 16, 34]


[2]: This way, the "zero matrix" is the one with 1's in the secondary diagonal, since only one 1 is allowed per column.

• What are you trying to optimize, speed or memory usage? – pacmaninbw Apr 30 '20 at 18:28
• Can you clarify how you are encoding a "permutation matrix" as a list of natural numbers? Do the list values represent the zero-based index of the "1" in each row of the permutation matrix? – Nick2253 Apr 30 '20 at 18:29
• And when you say efficiently - does that include pulling in libraries (numpy) to do this properly? – Reinderien Apr 30 '20 at 18:42
• Also, can you include code in your question that calls your functions with realistic data? – Reinderien Apr 30 '20 at 18:43
• @pacmaninbw speed – olyk Apr 30 '20 at 18:45

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

• Your third option is 3 times faster. Thanks! – olyk Apr 30 '20 at 21:53
• However the result doesn't seem to match. – olyk Apr 30 '20 at 22:05
• @viyps The transpose_l functions assume indexing from the left! I've added the _r versions. – Andrew Apr 30 '20 at 22:16
• Ok! The R version is also faster. I have another problem which is to convert a number to such matrices, it has much more room for optimization, but it is far more involved to explain. If you are interested I can post another question. – olyk Apr 30 '20 at 22:35
• @viyps Sure, go ahead. If not I, someone else will surely give you some tips! – Andrew Apr 30 '20 at 22:37