2
$\begingroup$

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

  • 0
    okay I understand now, thank you both!2012-11-04

2 Answers 2

4

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).$

  • 0
    I am thinking for providing a GAP code to do this.+2013-08-02
3

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}$

There are several ways to think about this.

  • 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$.

  • 0
    thank you, it works for the other exercises as well :)2012-11-04