When we want to define transformations using permutations, what are the subtle differencies betwen the use of permutation matrices, and the use of permutations?
Say I want to define a way to shuffle a sequence of numbers. Shoud I define my transformation with permutation matrices, or only with the permutation notations, i.e. cycle, permutation?
Thank you.
As a practical matter, a permutation defined as a mapping from the set $\,1,2,\dots,n\,$ to itself is easily implemented as a vector or array and composition of permutations is an $\,O(n)\,$ operation using $\,O(n)\,$ space. The equivalent operation using permutation arrays is an $\,O(n^3)\,$ operation using $\,O(n^2)\,$ space. Other than some time and space complexity differences, the two approaches are mathematically equivalent.