The minimal number of permutation matrices

Question

What is the minimal number of permutation matrices we need to fix in order to express any other permutation matrix as a product of those fixed matrices (actually, we can take every matrix of those fixed matrices several times).

Answer 1

All the permutations of $n$ elements can be generated by these two permutations (I use cycle notation for readablility): the transposition $s = (1,2)$ and the cycle $r = (1,2,\ldots, n-1,n)$. First of all I suppose known already that each permutation is the composition of transpositions (also called exchanges or 2-cycles) $(a_i, a_j)$. The first step is to construct the $n$ transpositions of the form $(i, {i+1})$ and $(1,n)$ with $1 \leq i < n$. One can easily verify that they are obtained as $r^{-j} \circ s \circ r^j$ with $0 \leq j < n$. The next step is to generate the remaining transpositions $(i,j)$. These can be obtained by the "palindromic" compositions: $(i, i+1) \circ (i+1, i+2) \circ \ldots \circ (j-2, j-1) \circ (j-1,j) \circ (j-2, j-1) \circ \ldots \circ (i+1, i+2) \circ (i, i+1) $ This proves that every permutation can be written as a word using only $r$ and $s$. Note that this construction is only of theorethical importance. In practice, if one wants to construct groups generated by some permutations it is more practical to use algorithms like the Schreier-Sims algorithm.