2
$\begingroup$

Let $p,q$, $(p\neq q)$ be odd primes. Define the function $f:\{0,1,\ldots,pq-1\}\to \{0,1,\ldots,pq-1\}$ by $f(x+yp)=qx+y$, where $x\in \{0,1,\ldots,p-1\}$ and $y\in\{0,1,\ldots,q-1\}$. How does one calculate the number of inversions for $f$?

A complete solution would be quite helpful.

$\endgroup$
  • $\begingroup$ "Inversions" are defined for a permutation of an ordered set; you need to define a total order on $\mathbb{Z}_{pq}$. I assume you really want the function $f : \left\{0,1,\ldots,pq-1\right\} \to \left\{0,1,\ldots,pq-1\right\}$ (not $f : \mathbb{Z}_{pq} \to \mathbb{Z}_{pq}$) that sends each $x + yp$ to $qx + y$ for $x \in \left\{0,1,\ldots,p-1\right\}$ and $y \in \left\{0,1,\ldots,q-1\right\}$. $\endgroup$ – darij grinberg Mar 23 at 5:10
  • 1
    $\begingroup$ Note that it does not matter whether or not $p$ and $q$ are prime or distinct. A very similar (most likely equivalent, but I am too tired) problem has been posed as Exercise 3 in UMN Fall 2017 Math 4990 homework set #8 (the link goes to a PDF that sketches a solution and contains a link to another writeup with a solution). $\endgroup$ – darij grinberg Mar 23 at 5:12
  • $\begingroup$ @darijgrinberg Yes. Appreciate the comments. Thank you :) $\endgroup$ – crskhr Mar 23 at 5:25
1
$\begingroup$

We will consider the case $p=3, q=5$ which is easy to draw. Hopefully you agree the ideas generalize. Consider these matrices:

$$ A = \begin{bmatrix} 0 & 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \end{bmatrix}, \ \ \ \ \ \ \ \ \ \ \ \ \ B = \begin{bmatrix} 0 & 3 & 6 & 9 & 12 \\ 1 & 4 & 7 & 10 & 13 \\ 2 & 5 & 8 & 11 & 14 \end{bmatrix} $$

Let the rows be numbered $x = 0, 1, 2$ from top to bottom and the columns be numbered $y = 0, 1, 2, 3, 4$ from left to right. Then $A_{xy} = qx+y$ and $B_{xy} = x+py$.

So here's a recipe for evaluating $f(i)$ where $i \in \mathbb{Z}_{pq}$:

  • First, find location $(x,y)$ where $B_{xy}= i$

  • Then, look up the same location in matrix $A$ and we have $f(i) = A_{xy}$.

If I may abuse notation a bit, the chain of mapping that just happened was something like this:

$$i = x+py = B_{xy} \rightarrow (x,y) \rightarrow A_{xy} = qx+y = f(i) = f(x+py)$$

which has an overall effect of $x + py \rightarrow qx+y$ as desired.

OK, so how does this help? Consider $(i,j) \in \mathbb{Z}_{pq}^2$. It is an inversion if $i < j$ and $f(i) > f(j)$. Let their locations be $(x_i, y_i), (x_j, y_j)$, i.e. $i = x_i + p y_i = B_{x_i y_i}$ and $f(i) = q x_i + y_i = A_{x_i y_i}$, and similarly for $j$.

  • From matrix $B$, it is obvious that $i = B_{x_i y_i} < j = B_{x_j y_j}$ iff $y_j > y_i$ ($j$'s column is to the right of $i$'s column), or, $y_j = y_i$ and $x_j > x_i$ ($j$ is in the same column and below $i$).

  • From matrix $A$, similarly, $f(i) = A_{x_i y_i} > f(j) = A_{x_j y_j}$ iff $x_j < x_i$ ($j$'s row is above $i$'s row), or, $x_j = x_i$ and $y_j < y_i$ ($j$ is in same row and to the left of $i$).

Since we need both conditions above to be true, this means $(i,j)$ is an inversion iff $y_j > y_i$ and $x_j < x_i$, i.e. $(x_j, y_j)$ must be strictly to the right and above $(x_i, y_i)$.

E.g. in the following colored matrices, the blue cell represents $i=4, f(i) = f(1 + 1 \cdot 3) = 5 \cdot 1 + 1 = 6$. The red area in the $B$ matrix represents $j> i$ and the red area in the $A$ matrix represents $f(j) < f(i)$. Clearly the only overlap (for this choice of $i$) are the $3$ cells corresponding to $x=0, y=2,3,4$. These are the values of $j$ which form inversions with this choice of $i$.

$$ A = \begin{bmatrix} \color{red}{0} & \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} \\ \color{red}{5} & \color{blue}{6} & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \end{bmatrix}, \ \ \ \ \ \ \ \ \ \ \ \ \ B = \begin{bmatrix} 0 & 3 & \color{red}{6} & \color{red}{9} & \color{red}{12} \\ 1 & \color{blue}{4} & \color{red}{7} & \color{red}{10} & \color{red}{13} \\ 2 & \color{red}{5} & \color{red}{8} & \color{red}{11} & \color{red}{14} \end{bmatrix} $$

E.g. $j=6 > i=4$ and $f(j) = f(0 + 2\cdot 3) = 5\cdot 0 + 2 = 2 < f(i) = 6$.

So each $(i,j)$ pair that is an inversion is a pair of cells which form the top-right and bottom-left corners of a rectangle, where the rectangle has $c>1$ columns and $r>1$ rows. To count such rectangles, simply pick any $2$ distinct columns, and any $2$ distinct rows. So the final answer, i.e. the total number of inversion pairs, is ${p \choose 2}{q \choose 2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.