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.