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

  • 2
    Which way do you multiply transpositions? Does $(76)(36)$ send $7$ to $3$, or does it send $3$ to $7$?2012-11-04
  • 0
    thats a good question. apparently I learned that you send from the inner to the outer so 3 to 7 I suppose?2012-11-04
  • 0
    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"2012-11-04
  • 0
    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?2012-11-04
  • 0
    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...2012-11-04
  • 0
    Okay, thanks for clarifying. I just find the given transposition confusing, given the initial representation of $\pi$. As I mention in my comment, there are many ways to write a permutation as the product of transpositions.2012-11-04
  • 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 don't see anything in this answer after "Here's why:".2012-11-04
  • 0
    thanks, thats also an easy and fast way :D2012-11-04
  • 0
    i think you meant the correct thing but i must be 2 so that 2 moves to 1 if we go further to the left2012-11-04
  • 0
    It is 2; see my correction.2012-11-04
  • 0
    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 me2012-11-04
  • 0
    Yes, Freddy, thanks for catching the typo...all good now!2012-11-04
  • 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