{
localUrl: '../page/symmetric_group_is_generated_by_transpositions.html',
arbitalUrl: 'https://arbital.com/p/symmetric_group_is_generated_by_transpositions',
rawJsonUrl: '../raw/4cp.json',
likeableId: '2722',
likeableType: 'page',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [
'EricBruylant'
],
pageId: 'symmetric_group_is_generated_by_transpositions',
edit: '1',
editSummary: '',
prevEdit: '0',
currentEdit: '1',
wasPublished: 'true',
type: 'wiki',
title: 'Every member of a symmetric group on finitely many elements is a product of transpositions',
clickbait: 'This fact can often simplify arguments about permutations: if we can show that something holds for transpositions, and that it holds for products, then it holds for everything.',
textLength: '1658',
alias: 'symmetric_group_is_generated_by_transpositions',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'PatrickStevens',
editCreatedAt: '2016-06-15 10:03:48',
pageCreatorId: 'PatrickStevens',
pageCreatedAt: '2016-06-15 10:03:48',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '0',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '35',
text: 'Given a permutation $\\sigma$ in the [-497] $S_n$, there is a finite sequence $\\tau_1, \\dots, \\tau_k$ of [4cn transpositions] such that $\\sigma = \\tau_k \\tau_{k-1} \\dots \\tau_1$.\nEquivalently, symmetric groups are generated by their transpositions.\n\nNote that the transpositions might "overlap".\nFor example, $(123)$ is equal to $(23)(13)$, where the element $3$ appears in two of the transpositions.\n\nNote also that the sequence of transpositions is by no means uniquely determined by $\\sigma$.\n\n# Proof\n\nIt is enough to show that a [49f cycle] is expressible as a sequence of transpositions.\nOnce we have this result, we may simply replace the successive cycles in $\\sigma$'s disjoint cycle notation by the corresponding sequences of transpositions, to obtain a longer sequence of transpositions which multiplies out to give $\\sigma$.\n\nIt is easy to verify that the cycle $(a_1 a_2 \\dots a_r)$ is equal to $(a_{r-1} a_r) (a_{r-2} a_r) \\dots (a_2 a_r) (a_1 a_r)$.\nIndeed, that product of transpositions certainly does not move anything that isn't some $a_i$; while if we ask it to evaluate $a_i$, then the $(a_1 a_r)$ does nothing to it, $(a_2 a_r)$ does nothing to it, and so on up to $(a_{i-1} a_r)$.\nThen $(a_i a_r)$ sends it to $a_r$; then $(a_{i+1} a_r)$ sends the resulting $a_r$ to $a_{i+1}$; then all subsequent transpositions $(a_{i+2} a_r), \\dots, (a_{r-1} a_r)$ do nothing to the resulting $a_{i+1}$.\nSo the output when given $a_i$ is $a_{i+1}$.\n\n# Why is this useful?\n\nIt can make arguments simpler: if we can show that some property holds for transpositions and that it is closed under products, then it must hold for the entire symmetric group.',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: 'null',
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'PatrickStevens'
],
childIds: [],
parentIds: [
'symmetric_group'
],
commentIds: [],
questionIds: [],
tagIds: [],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [
{
id: '3971',
parentId: 'transposition_in_symmetric_group',
childId: 'symmetric_group_is_generated_by_transpositions',
type: 'requirement',
creatorId: 'AlexeiAndreev',
createdAt: '2016-06-17 21:58:56',
level: '1',
isStrong: 'false',
everPublished: 'true'
}
],
subjects: [],
lenses: [],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12993',
pageId: 'symmetric_group_is_generated_by_transpositions',
userId: 'PatrickStevens',
edit: '1',
type: 'newEdit',
createdAt: '2016-06-15 10:03:48',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12990',
pageId: 'symmetric_group_is_generated_by_transpositions',
userId: 'PatrickStevens',
edit: '1',
type: 'newRequirement',
createdAt: '2016-06-15 09:55:16',
auxPageId: 'transposition_in_symmetric_group',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12989',
pageId: 'symmetric_group_is_generated_by_transpositions',
userId: 'PatrickStevens',
edit: '1',
type: 'newParent',
createdAt: '2016-06-15 09:51:21',
auxPageId: 'symmetric_group',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}