Score:0

Structure of composition of permutations

ru flag

If $P_1, P_2$ are finite permutations, what can we say about $P_3 = P_1 \cdot P_2$? That is, what properties of the composition of permutations can be inferred from the properties of the permutations which are composed?

Since permutations form a group, for any $P_2$ and $P_3$, there exists a $P_1$ that when composed with $P_2$ gives $P_3$. So there range of composition spans the entire space of permutations. That doesn't mean, however, that we can't learn certain things about their structure or nature. For example: If we know the cyclic structure of $P_1$ and $P_2$, can we learn the cyclic structure of $P_3$?

Or, if $P_1$ is a simple cycle (that is, a shift with no fixed points), and $P_2$ is known, what is the range of $P_1 \cdot P_2$?

Or, what is the relationship between $P_1 \cdot P_2$ and $P_2 \cdot P_1$?

More generally: What, if any, properties of composition of permutations can be inferred from the properties of the individual permutations? Or, if you argue that no such properties can be inferred, please prove it.

poncho avatar
my flag
"if $P_1$ is a simple cycle (that is, a shift with no fixed points), what is the range of $P_1 \cdot P_2$?" - I believe you answered that in your previous paragraph "So their range of composition spans the entire space of permutations"
ru flag
@poncho Clarified wording to indicate "what is the range of composition for a **known P2**"
Score:1
ru flag

If we know the cyclic structure of $P_1$ and $_2$, can we learn the cyclic structure of $_3$?

No. Consider the case when $P_1$ is all fixed points bar a 2-cycle and $P_2$ has the same structure. $P_3$ could be the identity; it could consist of two disjoint 2-cycles and the rest fixed points; it could be a 3-cycle and the rest fixed points. We can say that if $P_1$ and $P_2$ belong to the same subgroup (e.g. membership of the alternating group can be inferred from the cycle structure) then so does $P_3$.

If $P_1$ is a simple cycle (that is, a shift with no fixed points), and $_2$ is known, what is the range of $_1⋅_2$?

It's the union of right cosets of shift subgroups whose intersection is $P_2$. This is close to tautologous, but I can't think of a better way to describe it.

what is the relationship between $_1⋅_2$ and $_2⋅_1$?

It's a conjugate by $P_2$ (and so in particular has the same cycle structure). Let $Q=P_1P_2$ so that $P_1=QP_2^{-1}$ and $P_2\cdot P_1=P_2QP_2^{-1}$. $Q$ has $n!$ such representations there is a representation corresponding to any given conjugate and so no further structure can be inferred.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.