{
localUrl: '../page/cycle_notation_symmetric_group.html',
arbitalUrl: 'https://arbital.com/p/cycle_notation_symmetric_group',
rawJsonUrl: '../raw/49f.json',
likeableId: '2667',
likeableType: 'page',
myLikeValue: '0',
likeCount: '2',
dislikeCount: '0',
likeScore: '2',
individualLikes: [
'AlexeiAndreev',
'EricBruylant'
],
pageId: 'cycle_notation_symmetric_group',
edit: '8',
editSummary: '',
prevEdit: '7',
currentEdit: '8',
wasPublished: 'true',
type: 'wiki',
title: 'Cycle notation in symmetric groups',
clickbait: 'Cycle notation is a convenient way to represent the elements of a symmetric group.',
textLength: '4288',
alias: 'cycle_notation_symmetric_group',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'PatrickStevens',
editCreatedAt: '2016-06-15 10:17:16',
pageCreatorId: 'PatrickStevens',
pageCreatedAt: '2016-06-14 16:07:58',
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: '64',
text: 'There is a convenient way to represent the elements of a [-497] on a finite set.\n\n# $k$-cycle\n\nA $k$-cycle is a member of $S_n$ which moves $k$ elements to each other cyclically.\nThat is, letting $a_1, \\dots, a_k$ be distinct in $\\{1,2,\\dots,n\\}$, a $k$-cycle $\\sigma$ is such that $\\sigma(a_i) = a_{i+1}$ for $1 \\leq i < k$, and $\\sigma(a_k) = a_1$, and $\\sigma(x) = x$ for any $x \\not \\in \\{a_1, \\dots, a_k \\}$.\n\nWe have a much more compact notation for $\\sigma$ in this case: we write $\\sigma = (a_1 a_2 \\dots a_k)$.\n(If spacing is ambiguous, we put in commas: $\\sigma = (a_1, a_2, \\dots, a_k)$.)\nNote that there are several ways to write this: $(a_1 a_2 \\dots a_k) = (a_2 a_3 \\dots a_k a_1)$, for example.\nIt is conventional to put the smallest $a_i$ at the start.\n\nNote also that a cycle's inverse is extremely easy to find: the inverse of $(a_1 a_2 \\dots a_k)$ is $(a_k a_{k-1} \\dots a_1)$.\n\nFor example, the double-row notation $$\\begin{pmatrix}1 & 2 & 3 \\\\ 2 & 3 & 1 \\\\ \\end{pmatrix}$$\nis written as $(123)$ or $(231)$ or $(312)$ in cycle notation.\n\nHowever, it is unclear without context which symmetric group $(123)$ lies in: it could be $S_n$ for any $n \\geq 3$.\nSimilarly, $(145)$ could be in $S_n$ for any $n \\geq 5$.\n\n# General elements, not just cycles\n\nNot every element of $S_n$ is a cycle. For example, the following element of $S_4$ has [4cq order] $2$ so could only be a $2$-cycle, but it moves all four elements:\n$$\\begin{pmatrix}1 & 2 & 3 & 4 \\\\ 2 & 1 & 4 & 3 \\\\ \\end{pmatrix}$$\n\nHowever, it may be written as the composition of the two cycles $(12)$ and $(34)$: it is the result of applying one and then the other.\nNote that since the cycles are disjoint (having no elements in common), [49g it doesn't matter in which order we perform them].\nIt is a very important fact that [49k every permutation may be written as the product of disjoint cycles].\nIf $\\sigma$ is a permutation obtained by first doing cycle $c_1 = (a_1 a_2 \\dots a_k)$, then by doing cycle $c_2$, then cycle $c_3$, we write $\\sigma = c_3 c_2 c_1$; this is by analogy with function composition, indicating that the first permutation to apply is on the rightmost end of the expression.\n(Be aware that some authors differ on this.)\n\n## Order of an element\n\nFirstly, a cycle has [4cq order] equal to its length.\nIndeed, the cycle $(a_1 a_2 \\dots a_k)$ has the effect of rotating $a_1 \\mapsto a_2 \\mapsto a_3 \\dots \\mapsto a_k \\mapsto a_1$, and if we do this $k$ times we get back to where we started.\n(And if we do it fewer times - say $i$ times - we can't get back to where we started: $a_1 \\mapsto a_{i+1}$.)\n\nNow, suppose we have an element in disjoint cycle notation: $(a_1 a_2 a_3)(a_4 a_5)$, say, where all the $a_i$ are different.\nThen the order of this element is $3 \\times 2 = 6$, because: \n\n- $(a_1 a_2 a_3)$ and $(a_4 a_5)$ are disjoint and hence commute, so $[(a_1 a_2 a_3)(a_4 a_5)]^n = (a_1 a_2 a_3)^n (a_4 a_5)^n$\n- $(a_1 a_2 a_3)^n (a_4 a_5)^n$ is the identity if and only if $(a_1 a_2 a_3)^n = (a_4 a_5)^n = e$ the identity, because otherwise (for instance, if $(a_1 a_2 a_3)^n$ is not the identity) it would move $a_1$.\n- $(a_1 a_2 a_3)^n$ is the identity if and only if $n$ is divisible by $3$, since $(a_1 a_2 a_3)$'s order is $3$.\n- $(a_4 a_5)^n$ is the identity if and only if $n$ is divisible by $2$.\n\nThis reasoning generalises: the order of an element in disjoint cycle notation is equal to the [-least_common_multiple] of the lengths of the cycles.\n\n# Examples\n\n- The element $\\sigma$ of $S_5$ given by first performing $(123)$ and then $(345)$ is $(345)(123) = (12453)$. Indeed, the first application takes $1$ to $2$ and the second application does not affect the resulting $2$, so $\\sigma$ takes $1$ to $2$; the first application takes $2$ to $3$ and the second application takes the resulting $3$ to $4$, so $\\sigma$ takes $2$ to $4$; the first application does not affect $4$ and the second application takes $4$ to $5$, so $\\sigma$ takes $4$ to $5$; and so on.\n\nThis example suggests a general procedure for expressing a permutation which is already in cycle form, in *disjoint* cycle form. It turns out that [49k this can be done in an essentially unique way].\n\n## Cycle type\n\nThe [-4cg] is given by taking the list of lengths of the cycles in the disjoint cycle form.',
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: 'true',
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: [
'disjoint_cycle_notation_is_unique',
'cycle_type_of_a_permutation'
],
parentIds: [
'symmetric_group'
],
commentIds: [
'49j'
],
questionIds: [],
tagIds: [],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
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: '13016',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '8',
type: 'newEdit',
createdAt: '2016-06-15 10:17:16',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12959',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '7',
type: 'newEdit',
createdAt: '2016-06-15 08:28:47',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12958',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '6',
type: 'newEdit',
createdAt: '2016-06-15 08:27:49',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12955',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '5',
type: 'newRequiredBy',
createdAt: '2016-06-15 08:25:28',
auxPageId: 'cycle_type_of_a_permutation',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12956',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '5',
type: 'newChild',
createdAt: '2016-06-15 08:25:28',
auxPageId: 'cycle_type_of_a_permutation',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12686',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '5',
type: 'newEdit',
createdAt: '2016-06-14 16:45:28',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12683',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '4',
type: 'newEdit',
createdAt: '2016-06-14 16:38:41',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12671',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '3',
type: 'newChild',
createdAt: '2016-06-14 16:34:15',
auxPageId: 'disjoint_cycle_notation_is_unique',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12664',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '3',
type: 'newEdit',
createdAt: '2016-06-14 16:25:28',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12659',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '2',
type: 'newEdit',
createdAt: '2016-06-14 16:10:24',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12658',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '1',
type: 'newEdit',
createdAt: '2016-06-14 16:07:58',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12656',
pageId: 'cycle_notation_symmetric_group',
userId: 'PatrickStevens',
edit: '1',
type: 'newParent',
createdAt: '2016-06-14 15:51:54',
auxPageId: 'symmetric_group',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'true',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}