Number of inversions

**zadir** · November 14th 2010, 12:53 AM

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.

**Drexel28** · November 14th 2010, 07:39 AM

Originally Posted by zadir

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.

**zadir** · November 14th 2010, 08:21 AM

For instance for n=2
$ \left[ {\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} } \right] $
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:
$ \left[ {\begin{array}{cc} a_{22} & a_{12} \\ a_{21} & a_{11} \\ \end{array} } \right] $
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.

**Drexel28** · November 14th 2010, 09:20 AM

Originally Posted by zadir

For instance for n=2
$ \left[ {\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} } \right] $
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:
$ \left[ {\begin{array}{cc} a_{22} & a_{12} \\ a_{21} & a_{11} \\ \end{array} } \right] $
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.

**zadir** · November 14th 2010, 11:08 AM

There are some definitions:
Permutation Inversion -- from Wolfram MathWorld
Leibniz formula for determinants - Wikipedia, the free encyclopedia

Thank you that you sacrifice time for me.

**Drexel28** · November 14th 2010, 11:15 AM

Originally Posted by zadir

There are some definitions:
Permutation Inversion -- from Wolfram MathWorld
Leibniz formula for determinants - Wikipedia, the free encyclopedia

Thank you that you sacrifice time for me.

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?

**zadir** · November 14th 2010, 12:04 PM

Originally Posted by Drexel28

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.

Thread: Number of inversions

LinkBack

Thread Tools

Display

Number of inversions

Similar Math Help Forum Discussions

Inversions

Proof regarding inversions

Proof related to inversions

Another IRV question... Inversions

Inversions of a permutation

Search Tags