Group theory and generalizations Proof
Proof that the symmetric group is generated by transpositions
Builds on Symmetric groupTranspositionSubgroup generated by a subsetSubgroupDecomposition of a permutation into transpositions
Proof
- Let , let be the symmetric group, and let be the set of all transpositions in .
- By definition, the subgroup generated by is the intersection of all subgroups of that contain . In particular, .
- Let be a subgroup of with . A subgroup is closed under products, so by induction on the number of factors, contains each product of elements of .
- By the decomposition into transpositions, each is such a product. So .
- By steps 3 and 4, the only subgroup of that contains is itself. Hence .
Idea
Any subgroup that contains all transpositions contains all their products. Every permutation is such a product, so that subgroup is the whole group.
Reading path
To understand this page from the ground up, read these 75 pages in order. The foundations come first. The path takes the proofs Proof of the decomposition of a permutation into transpositions, Proof of the commutativity of addition by induction, Proof that equivalence classes form a partition, Proof that disjoint cycles commute, Proof of strong induction from ordinary induction, Proof of the laws of exponents in a group, Proof that an intersection of subgroups is a subgroup, Proof of the decomposition of a permutation into disjoint cycles, Proof of the well-ordering principle from strong induction, Proof of the division algorithm, Proof of the uniqueness of inverses, Proof of the subgroup criterion.
- Binary operation definition
- Cycle notation concept
- Definition by recursion concept
- Divisibility definition
- Element definition
- Group concept
- Mathematical induction concept
- Natural numbers object
- Peano axioms concept
- Proposition concept
- Identity element definition
- Set definition
- Subgroup definition
- Symmetric group definition
- Successor function definition
- Conjunction definition
- Disjunction definition
- Implication definition
- Predicate definition
- Inverse element definition
- Empty set object
- Family of sets definition
- Ordered pair definition
- Transposition definition
- Intersection definition
- Proof that an intersection of subgroups is a subgroup proof
- Union definition
- Addition of natural numbers definition
- Set-builder notation concept
- Biconditional definition
- The successor function is injective statement
- Zero is not a successor statement
- Existential quantifier definition
- Universal quantifier definition
- Proof of the uniqueness of inverses proof
- Cartesian product definition
- Disjoint sets definition
- Proof of the commutativity of addition by induction proof
- Subset definition
- Axiom of extensionality statement
- Union of a family of sets definition
- Order on the natural numbers definition
- Uniqueness quantifier definition
- Uniqueness of inverses statement
- Binary relation definition
- Partition of a set definition
- Commutativity of addition statement
- Proof of strong induction from ordinary induction proof
- Reflexive relation definition
- Symmetric relation definition
- Transitive relation definition
- Proof of the subgroup criterion proof
- Proof of the laws of exponents in a group proof
- Function definition
- Strong induction statement
- Equivalence relation definition
- Subgroup criterion statement
- Laws of exponents in a group statement
- Injective function definition
- Proof of the well-ordering principle from strong induction proof
- Proof that disjoint cycles commute proof
- Intersection of subgroups is a subgroup statement
- Equivalence class definition
- Well-ordering principle statement
- Disjoint cycles commute statement
- Subgroup generated by a subset definition
- Proof that equivalence classes form a partition proof
- Proof of the division algorithm proof
- Equivalence classes form a partition statement
- Division algorithm statement
- Proof of the decomposition of a permutation into disjoint cycles proof
- Decomposition of a permutation into disjoint cycles statement
- Proof of the decomposition of a permutation into transpositions proof
- Decomposition of a permutation into transpositions statement
- Proof that the symmetric group is generated by transpositions proof
Where this leads
248 pages build on this one.
- Singular value decomposition
- Change of variables in multiple integrals
- Lotka–Volterra equations
- Volume of a ball in R^n
- Leibniz formula for determinants
- Triangularisation
- A matrix is invertible iff its determinant is a unit
- Lagrange multiplier with one constraint
- Determinant is multiplicative
- Spectral theorem for normal matrices
- Product of a matrix and its adjugate
- Eigenvalues are the roots of the characteristic polynomial
- Scalar triple product
- Jacobian of spherical coordinates
- Laplace expansion along a column
- Spectral theorem
- Determinant of the inverse
- Existence of an eigenvalue over an algebraically closed field
- Cauchy–Binet formula
- Minimal polynomial divides the characteristic polynomial
- Cramer's rule
- Liouville's formula
- Permuting rows multiplies the determinant by the sign
- Linearisation at an equilibrium
- Determinant of a matrix exponential
- The symmetric group is generated by transpositions
- Matrix determinant lemma
- Implicit function theorem
- Laplace expansion along a row
- Determinant is the product of the eigenvalues
- Hyperbolic equilibrium point
- Spectral theorem for Hermitian matrices
- Inverse in terms of the adjugate
- QR decomposition
- Cayley–Hamilton theorem
- Trace is a coefficient of the characteristic polynomial
- Sylvester's determinant theorem
- Cylindrical coordinates
- Rule of Sarrus
- Polar decomposition
- Determinant of a block triangular matrix
- Determinant of a triangular matrix
- Inverse function theorem
- Determinant via the Schur complement
- Determinant of a linear map is the determinant of its matrix
- Wronskian test for linear independence of solutions
- Classification of equilibria of planar linear systems
- Implicit function theorem for a surjective derivative
- Trace is the sum of the eigenvalues
- Vandermonde determinant
- Principal axis theorem
- Cayley–Hamilton theorem for linear maps
- Implicit differentiation
- Polar coordinates
- Spherical coordinates
- Variation of constants formula for linear systems
- Hartman–Grobman theorem
- Pendulum equation
- Stability of linear systems via eigenvalues
- Determinant is a coefficient of the characteristic polynomial
- Integration in polar coordinates
- Characteristic polynomial does not depend on the basis
- Lagrange multipliers
- Sylvester's criterion
- Cholesky decomposition
- Volume of a ball in R^3
- Diffeomorphism
- Decomposition into generalised eigenspaces
- Local homeomorphism from the inverse function theorem
- Determinant of a 2 by 2 matrix
- Determinant of a transpose
- Morse–Smale system
- Spectral theorem for unbounded self-adjoint operators
- Proof of the Lagrange multiplier rule with one constraint
- Routh–Hurwitz theorem
- Proof of the principal axis theorem from the spectral theorem
- Cuthill–McKee algorithm
- Hautus lemma
- Holomorphic inverse function theorem
- Proof of the implicit function theorem for a surjective derivative
- Proof of the singular value decomposition from the spectral theorem
- Jacobi's formula
- Proof of the implicit function theorem from the inverse function theorem
- Quantum Zeno effect
- Hilbert–Schmidt expansion theorem
- Proof of the Laplace expansion along a column by transposition
- Duality of controllability and observability
- Markov partition
- Augmented Lagrangian method
- Minimal realization
- Proof of the Schur complement formula by block factorization
- Minimum degree algorithm
- Proof of Cramer's rule by the adjugate
- Proof that the scalar triple product is a determinant
- Anharmonic oscillator
- Proof of Sylvester's criterion by induction and completing the square
- Proof of the Wronskian test for linear independence of solutions
- Volterra's principle
- Bilinear series of a symmetric kernel
- Choquet-Bruhat–Geroch theorem on maximal developments
- Proof of the Lagrange multiplier theorem by the implicit function theorem
- QR algorithm
- Spectral decomposition theorem
- Black hole stability problem
- Mason's gain formula
- Sylvester's determinant identity
- Proof that the constant coefficient of the characteristic polynomial is a signed determinant
- Incomplete Cholesky factorization
- Proof that the determinant is multiplicative by expanding the rows
- Proof that permuting rows multiplies the determinant by the sign
- Central polynomial
- Box–Muller transform
- Kaplansky's theorem on PI rings
- Proof that a matrix is invertible iff its determinant is a unit
- Proof that the trace is the sum of the eigenvalues by comparing coefficients
- Proof of the determinant of a block triangular matrix by the Leibniz formula
- Nested dissection
- Uhlmann's theorem
- Kalman rank condition
- Marshallian demand function
- Proof that a C^1 map with invertible derivative is a local homeomorphism and an open map
- Nash–Moser theorem
- Spectral theorem for compact self-adjoint operators
- Courant–Fischer characterization of characteristic values
- Proof of Liouville's formula
- Utility maximization problem
- Proof of the spectral theorem for self-adjoint operators by induction on the dimension
- Proof of the Laplace expansion along a row by the Leibniz formula
- Principle of material frame-indifference
- Detectability
- Mixed state
- Implicit function theorem in Banach spaces
- Melnikov method
- Strong cosmic censorship conjecture
- Euler's elastica
- Proof that the determinant of a transpose equals the determinant
- Lyapunov–Schmidt reduction
- Purification of a quantum state
- Gleason's theorem
- Weak cosmic censorship conjecture
- Numerical continuation
- Proof of the inverse in terms of the adjugate
- Proof of the eigenvalue criteria for stability of linear systems via the Jordan normal form
- Inverted pendulum
- Proof that the trace is a coefficient of the characteristic polynomial by the Leibniz formula
- Schur polynomial
- Stone's theorem on one-parameter unitary groups
- Closing lemma
- Sequential quadratic programming
- Kalman decomposition
- Anosov flow
- Lidskii's trace formula for integral operators
- Hamiltonian operator
- Second quantization
- Differential-algebraic system of equations
- Proof of the decomposition into generalised eigenspaces
- Smale's problems on dynamics
- Controllability Gramian
- Posner's theorem
- Controllable canonical form
- Spectrum of the Laplace–Beltrami operator
- Backus–Gilbert method
- Principal stresses
- Furuta pendulum
- Topological quantum field theory
- Smooth dynamical system
- Brunovsky normal form
- Wick rotation
- Eckart–Young theorem
- Balanced truncation
- Ackermann's formula
- Proof of the existence of an eigenvalue over an algebraically closed field
- Strang splitting
- Proof of the variation of constants formula for linear systems
- Zermelo's navigation problem
- Lie–Trotter product formula
- Routh–Hurwitz stability criterion
- Regular value theorem
- Proof of the determinant of the inverse
- Inverse function theorem in Banach spaces
- Proof of the inverse function theorem by the contraction mapping principle
- Kharitonov's theorem
- Proof of the polar decomposition from the singular value decomposition
- Born rule
- Borel functional calculus
- Proof of the matrix determinant lemma from Sylvester's determinant theorem
- Proof of the formula for the determinant of a 2 by 2 matrix
- Proof of the Cholesky decomposition by induction on the size
- Configuration space
- Schmidt decomposition
- Hyperbolic set
- Operator monotone function
- Proof of the spectral theorem for normal matrices by deflation
- Mercer's theorem
- Proof of the spectral theorem for Hermitian matrices
- Lagrange multipliers for constraints
- Proof that the minimal polynomial divides the characteristic polynomial
- Proof of triangularisation by induction on the size
- Proof of Sylvester's determinant theorem by two block factorizations
- Proof of the product of a matrix and its adjugate by Laplace expansion
- Anharmonic oscillator
- Proof of the volume of a ball in R^3 from the n-dimensional formula
- Generalized Lotka–Volterra equation
- Proof of the determinant of a triangular matrix by the Leibniz formula
- Quantum computing
- Wave function collapse
- Principal component analysis
- Proof of the Leibniz formula from the defining properties of the determinant
- Proof of the Cayley–Hamilton theorem for linear maps
- Axiom A
- Inertia tensor and principal axes
- Bidiagonalization
- Pole placement theorem
- Duffing equation
- Kapitza's pendulum
- Liénard–Chipart criterion
- Indirect utility function
- Proof of the Vandermonde determinant by column operations
- Schur product theorem
- Singular values of a compact operator
- Numerical methods for linear least squares
- Spherical pendulum
- Observable
- Slice theorem
- Schmidt's singular value decomposition of a kernel
- Proof that the determinant of a matrix exponential is the exponential of the trace
- Proof that the eigenvalues are the roots of the characteristic polynomial
- Van der Pol oscillator
- Proof of the rule of Sarrus
- Polar decomposition of the deformation gradient
- Anosov diffeomorphism
- Spectral theorem for bounded normal operators
- Proof of the Cauchy–Binet formula by multilinearity
- Adjoint state method
- Stability conjecture
- Hidden-variable theory
- Channel capacity of a quantum channel
- Stabilizability
- Gain scheduling
- Proof of the Cayley–Hamilton theorem with the adjugate
- Amitsur–Levitzki theorem
- Hill differential equation
- Proof that the determinant of a linear map does not depend on the basis
- Time-optimal control
- Proof that the determinant is the product of the eigenvalues by comparing constant terms
- Normal form
- Proof of the QR decomposition by clearing the first column
- Proof that similar matrices have the same characteristic polynomial
Further reading
- Web https://en.wikipedia.org/wiki/Symmetric_group, Generators and relations
About this page
| Tag | 36FRFTA090 |
|---|---|
| URI | m2://36FRFTA090 |
| Kind | proof |
| Writing | W0 stub |
| MSC | 20B30 |
| Proves | The symmetric group is generated by transpositions |
| Uses | Symmetric group, Transposition, Subgroup generated by a subset, Subgroup, Decomposition of a permutation into transpositions |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.