Hamiltonian path in $S_n$?

Question

Say $S_n$ is the symmetric group. Define a graph $G$ by $G=(S_n,E)$, where there is an edge from $\sigma_1$ to $\sigma_2$ if and only if $\sigma_2=t\sigma_1$ for some transposition $t$.

Is there a Hamiltonian path in $G$? If yes, is there a convenient way to define such a path?

No work so far - sue me. Context: For no practical reason, thinking about an elegant implementation of the formula $$\det(A)=\sum_{\sigma\in S_n}\text{sgn}(\sigma)\prod_{j=1}^n a_{j,\sigma(j)}.$$

Answer 1

Yes, such Hamiltonian path exists and it can obtained just by swapping adjacent elements between two successive permutations. The procedure to generate it is called the Steinhaus–Johnson–Trotter algorithm.

For example, for $S_4$, it gives the following Hamiltonian path (actually a cycle) through the $4!=24$ permutations: $$123\color{blue}{4}\to 12\color{blue}{4}3\to 1\color{blue}{4}23\to \color{blue}{4}1\color{red}{23}\to\\ \color{blue}{4}132\to 1\color{blue}{4}32 \to 13\color{blue}{4}2\to \color{red}{13}2\color{blue}{4}\to\\ 312\color{blue}{4} \to 31\color{blue}{4}2\to 3\color{blue}{4}12\to \color{blue}{4}3\color{red}{12} \to\\ \color{blue}{4}321\to 3\color{blue}{4}21\to 32\color{blue}{4}1 \to \color{red}{32}1\color{blue}{4}\to\\ 231\color{blue}{4}\to 23\color{blue}{4}1\to 2\color{blue}{4}31\to \color{blue}{4}2\color{red}{31}\to\\ \color{blue}{4}213\to 2\color{blue}{4}13 \to 21\color{blue}{4}3\to \color{red}{21}3\color{blue}{4}\to$$

Answer 2

Yes.

For $S_1$ and $S_2$, this is trivial.

For $S_n$ with $n\ge 2$ apply recursion: Starting with the identity, a Hamiltonian path for $S_{n-1}$ allows you to walk through all $(n-1)!$ permutations of $\{1,\ldots,n\}$ that map $n\mapsto n$. More generally, if you start with any $\sigma\in S_n$, this allows you to walk through all $(n-1)!$ permutations of $\{1,\ldots,n\}$ that map $n\mapsto \sigma(n)$.

To get all $n!$ elements of $S_n$, start with all permutations mapping $n\mapsto n$. Then apply $(n\,n-1)$ and walk through all permutations mapping $n\mapsto n-1$. Then apply $(n-1\,n-2)$ and walk through all permutations mapping $n\mapsto n-2$. Then ...

---

Regarding your goal with the determinant: Note that this method will cost you $O(n!)$ operations, whereas the Gauss algorithm uses only $O(n^3)$.