# Permutation and cycles

I need to determine the missing number to fulfill the following reproduction:

$$\pi=\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&1&2&6&7&8}$$

And here is the representation of $pi$ as the product of transpositions:

$$(1 i) (1 3) (2 5) (9 8) (8 7) (7 6) (3 6) = \pi$$

The result for $i$ must be 2 but I have no clue how to get there. I tried to start at $(3 6)$ and then check on which transposition it gets pictured on but it doesn't seem to work for me. Any ideas on how to generally solve these kind of problems?

-Freddy

-
Which way do you multiply transpositions? Does $(76)(36)$ send $7$ to $3$, or does it send $3$ to $7$? – Brian M. Scott Nov 4 '12 at 17:48
thats a good question. apparently I learned that you send from the inner to the outer so 3 to 7 I suppose? – Freddy Nov 4 '12 at 17:52
Note, there is no unique decomposition of this permutation into the product of transpositions, so I'm not sure what you mean by "here is the transposition" – amWhy Nov 4 '12 at 17:52
Have you tried first expressing the permutation as a product of disjoint cycles? Or have you not encountered cycle notation? It would help to know if you were asked to express the permutation as the product of transpositions, or if you were given the transpositions and asked to find the missing number? – amWhy Nov 4 '12 at 17:54
actually I was asked to find the missing number and the transposition was already given. We barely spoke about cycle notation due to lack of time... – Freddy Nov 4 '12 at 18:01

Given the following permutation $$\pi=\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&1&2&6&7&8}$$

You are asked to find the missing number, given the following decomposition of $\pi$ into the product of transpositions:

$$\pi = (1 \;i) (1\; 3) (2 \;5) (9\;8) (8 \;7) (7\; 6) (3 \;6).$$

The missing number is $i=2$, just as you suspected.

This is how I'd approach the problem:

I start with the rightmost transposition, as did you, and I start with $1$. Since there is no $1$ in that transposition, I move to the transposition immediately to the left of $(3 6)$...then to the left of that, ...and continue moving leftward until I reach the first transposition containing $1$: ($1 3)$. We see that 1 goes to 3. That matches the permutation above. So we are done with $1$.

We go back to $(3 6)$ and proceed in the same manner, this time looking for $2$...We move from $(3 6)$ leftward and until we first encounter $2$, which first appears in the transposition $(2 5)$. So $2 \to 5$. That matches the mapping of $2$ to $5$ in the permutation above. So we're done with $2$...

Then we move to $3$, starting back at $(3 6)$ ... : $3 \to 6$, then moving leftward, $6 \to 7$; moving leftward, $7 \to 8$; moving leftward, $8 \to 9$. Since we started this process with $3$, and ended at $9$, and since we know $\pi$ takes $3$ to $9$, we're done with $3$.

Since $\pi$ maps $4$ to $4$, $4$ need not appear at all in the transpositions...

We continue with $5$ and see it first appears (moving right to left) in the transposition $(2 5)$. So $5 \to 2$, but $\pi$ does not maps $5$ to $2$; i.e., we need $5 \to 1$. There's one transposition remaining: $(1, i)$ so $i$ must be $2$, and since we're working with $5 \to 2$), then setting $i = 2$ we have $5 \to 2 \to 1$, as desired.

(The rest of the numbers: $6, 7, 8, 9$ are all mapped explicitly in the transpositions in a manner corresponding to the map of $\pi$.)

So $$\pi = (1\; \underline{2}) (1\; 3) (2 \;5) (9\; 8) (8 \;7) (7\; 6) (3\; 6).$$

-
I don't see anything in this answer after "Here's why:". – coffeemath Nov 4 '12 at 18:17
thanks, thats also an easy and fast way :D – Freddy Nov 4 '12 at 18:34
i think you meant the correct thing but i must be 2 so that 2 moves to 1 if we go further to the left – Freddy Nov 4 '12 at 18:36
It is 2; see my correction. – amWhy Nov 4 '12 at 18:38
at the far bottom [...] we need 5 to go to 1, so i must be 5, since we're working with 5 [...] but that's just cosmetic. I am glad that you helped me – Freddy Nov 4 '12 at 18:42

According to the comments, you’re multiplying from right to left. If you multiply the transpositions that you know completely, you get

$$\pmatrix{6&3&7&8&9&5&2&1&4\\1&9&6&7&8&2&5&3&4}\;,$$

which we rearrange into standard form as

$$\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&2&1&6&7&8}\;.\tag{1}$$

We want to choose $i$ so that

$$(1i)\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&2&1&6&7&8}=\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&1&2&6&7&8}\;.\tag{2}$$

• You can notice that $(1)$ and $\pi$ differ only in what they do to $5$ and $6$, and it’s pretty clear that setting $i=2$ will fix that discrepancy.
• You can notice that if you carry out the multiplication on the lefthand side of $(2)$, you’ll get $$\pmatrix{1&2&3&4&5&6&7&8&9\\\cdot&\cdot&\cdot&\cdot&\cdot&i&\cdot&\cdot&\cdot}\;,$$ so if this product is to be $\pi$, $i$ must be $2$. (Of course you should then finish the multiplication to check.)
• You can use the fact that a transposition is its own inverse: $(2)$ holds if and only if $$\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&2&1&6&7&8}=(1i)\pmatrix{1&2&3&4&5&6&7&8&9\\3&5&9&4&1&2&6&7&8}\;,$$ and the product on the right is going to have a column $\binom5i$, so again $i$ must be $2$.