Results 1 to 7 of 7

Math Help - Number of inversions

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    43

    Number of inversions

    What happens to the number of inversions in a permutation group if we reflect the matrix across its antidiagonal?

    (I suppose that Leibniz formula for determinants should be used or maybe showing by induction?)

    Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by zadir View Post
    What happens to the number of inversions in a permutation group if we reflect the matrix across its antidiagonal?

    (I suppose that Leibniz formula for determinants should be used or maybe showing by induction?)

    Thank you in advance.
    A little more context would be helpful.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    For instance for n=2
    \[<br />
\left[ {\begin{array}{cc}<br />
 a_{11} & a_{12}  \\<br />
 a_{21} & a_{22}  \\<br />
 \end{array} } \right]<br />
\]
    So the number of inversions in the two groups:
    in a_{11}a_{12} it is 0
    in a_{12}a_{21} it is 1
    (That's why the value of its matrix is a_{11}a_{12}-a_{12}a_{21})
    If we reflect it across its antidagonal:
    \[<br />
\left[ {\begin{array}{cc}<br />
 a_{22} & a_{12}  \\<br />
 a_{21} & a_{11}  \\<br />
 \end{array} } \right]<br />
\]
    And the number of inversions are the same. For n=3 it is a little more complicated. So I don't really know what happens with the number of inversions if n>2. I would be glad if you could help me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by zadir View Post
    For instance for n=2
    \[<br />
\left[ {\begin{array}{cc}<br />
 a_{11} & a_{12}  \\<br />
 a_{21} & a_{22}  \\<br />
 \end{array} } \right]<br />
\]
    So the number of inversions in the two groups:
    in a_{11}a_{12} it is 0
    in a_{12}a_{21} it is 1
    (That's why the value of its matrix is a_{11}a_{12}-a_{12}a_{21})
    If we reflect it across its antidagonal:
    \[<br />
\left[ {\begin{array}{cc}<br />
 a_{22} & a_{12}  \\<br />
 a_{21} & a_{11}  \\<br />
 \end{array} } \right]<br />
\]
    And the number of inversions are the same. For n=3 it is a little more complicated. So I don't really know what happens with the number of inversions if n>2. I would be glad if you could help me.
    I know what you meant, sort of. This is pretty much what I thought. You're taking the idea of an inversion in a permutation \sigma\in S_n to be two values x,y\in[n] such that x<y but \sigma(x)>\sigma(y). But could you explain this a little more? Combinatorially inversions can be seen as connecting the values of your matrix with lines and an inversion is an incidence of intersecting lines.

    So, could you give a precise definition and not an example? It's clear if you interpret combinatorially (as above) that the number of inversions is invariant under such a flip.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by zadir View Post
    I'm sorry, you've explained to me what I knew an inversion was for a permutation. My question was, how exactly do you want to interpret this with a matrix?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    Quote Originally Posted by Drexel28 View Post
    I'm sorry, you've explained to me what I knew an inversion was for a permutation. My question was, how exactly do you want to interpret this with a matrix?
    Sorry, I see. The determinant of a matrix can be definied by permutations. So the inversion refers to permutation, that refers to determinant and that to the matrix.
    Or the last step can be left out, we can say that we reflect the determinant across its minor diagonal.
    Here are some links:
    A Determinant's relation to permutations
    Determinants

    And thanks once again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2010, 03:12 PM
  2. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 03:12 PM
  3. Proof related to inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 9th 2010, 06:19 AM
  4. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 25th 2009, 04:49 PM
  5. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2008, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum