Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

These questions were from an assignment I had some time ago but the solutions were not provided.

A permutation $P$ on a finite set $A$ is a binary relation with the property that for each $a∈A$, there is precisely one element of $P$ of the form $(a, x)$, and precisely one element of $P$ of the form $(x, a)$.

For example, $\{(1, 4), (2, 2), (3, 1), (4, 3)\}$ is a permutation of the set $\{1, 2, 3, 4\}$.

Q: If $P$ is a permutation, describe the general form of its directed graph diagram.

My solution: The general form of its directed graph being that it is one-to-one is that each element will have exactly one arrow going from it and one to it.

(The marker of this assignment states, "What does this mean for the structure of the diagram?").

Q: If $P$ and $Q$ are permutations on the set $\{1, 2, ... n\}$, how is the directed graph diagram of $P$ related to the directed graph $Q^{-1} \circ P \circ Q$?

A: I claimed that they will have the exact same figure, meaning that the shape of the closed circuits will always be the same. Apparently this is correct according to the marker, but I am not sure how to prove this statement.

share|improve this question
    
    
I had linked the second already but I guess Arthur Fischer's explanation is better. –  Shahab Oct 7 '12 at 17:05
add comment

2 Answers

up vote 1 down vote accepted
  1. The marker might have been looking for you to say that the directed graph diagram of the permutation will consist of some number of disjoint cycles.

  2. As you stated, the directed graph diagram of $Q^{-1} \circ P \circ Q$ will have the exact same shape as the directed graph diagram of $P$, but nodes in the cycles might change.

    This basically follows from the fact that $( Q^{-1} \circ P \circ Q ) ( Q^{-1} ( a ) ) = Q^{-1} ( P ( a ) )$, and so the cycle $$a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_n \rightarrow a_1$$ in $P$ will correspond to the cycle $$Q^{-1} (a_1) \rightarrow Q^{-1} (a_2) \rightarrow \cdots \rightarrow Q^{-1} ( a_n ) \rightarrow Q^{-1} (a_1)$$ in $Q^{-1} \circ P \circ Q$.

share|improve this answer
add comment

For your first question note that you will have disjoint circuits in your directed graph.

For your second question, you will get the same figure (though the corresponding permutation may be different from $P$ or $Q$). This follows from a result proved here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.