I have "roughed out" an idea for a proof for Fraleigh's Abstract Algebra book, but I am having trouble fully articulating and fleshing out what I want to write.
I need to show that every permutation in $S_n$ can be written as a product of at most $n-1$ transpositions. Since transpositions are cycles of size 2, I know that all transpositions must permute two elements. I also know that the product of two transpositions should yield a larger permutation if I want to permute the entire set. That is, I don't want the product of two transpositions to equal another transposition.
Let's say that we are permuting $4$ different elements, $(a, b, c, d)$. My strategy is to compare the number of transpositions to the number of linearly independent columns in an $4 \times m$ matrix.
$$\begin{bmatrix}1 & 2 & 0 & 0\space \ldots\\1 & 2 & 3 & 0\space \ldots\\ 1 & 0 & 3 & 4\space \ldots\\ 1 & 0 & 0 & 4 \space \ldots\end{bmatrix}$$
I would treat the initial (unpermuted) set as the leftmost column, which is entirely filled in. I would show that if I must fill in at least two rows per column, the maximum number of linearly independent columns I can create (under this restriction) is equal to three. Then I would try to find an isomorphism between adding columns in the matrix to multiplying permutations, and showing the maximum number of unique columns is equal to the maximum number of factorable transpositions that I can have onto a set.
The issue is actually writing this proof out. To prove an isomorphism, I would first have to show that if for two columns, say, $c_1$ and $c_2$, I would have to prove one-to-one correspondence, that is $$ \phi(c_1) = \phi(c_2) \rightarrow c_1 = c_2$$ This would make sense to me from intution, but writing that out rigorously is a challenge. I would also have to show that for every transposition of say $\sigma$ in $S_n$ that there is a preimage in my matrix in $GL(n,\mathbb R)$: $$ c_\sigma = \phi^{-1}(\sigma)$$ The final, and I think hardest part by far is showing the homomorphism property. I need to somehow articulate mathematically that the structure of two columns being linearly dependent or independent can translate into the product of two transpositions being either another transposition, or a larger-sized permutation. I would have to take: $$ \phi(c_1 + c_2) = \phi(c_1) \space \phi(c2) $$ and somehow extrapolate that to get the proof that I want (in the event that $c_1$ is not linearly independent of $c_2$).
Thank you for your time. Any help would be greatly appreciated.