Also, this seems like a good problem to be lazy about, by defining a PermutedMatrix in addition to PermutationMatrix.
Suppose,
P = PermutationMatrix([1,3,4,2])
A = rand(4,4)
B = rand(4,4)
M = P*A // would be a PermutedMatrix
R = B*M // == B*(P*A) == (B*P)*A
// and performing permutation on columns
// is easier and faster.
// `getindex` on PermutedMatrix would go
// through the permutation