# Counting inversions in a certain patterned matrix

Let $p$ and $q$ be relatively prime. Consider the $p\times q$ matrix $A$ containing the entries $1, 2, 3, \dots, pq$, which is formed via $a_{11} = 1, a_{22} = 2, \dots, a_{p-1,q-1} = pq-1, a_{pq} = pq$, using a torus wrap at the edges.

For example with $p=5$ and $q=3$, $A$ looks like:

\begin{bmatrix} 1 & 11 & 6\\\ 7 & 2 & 12\\\ 13 & 8 & 3\\\ 4 & 14 & 9\\\ 10 & 5 & 15 \end{bmatrix}

I am interested in counting the inversions in $A$, that is, cases of $a_{ij} > a_{kl}$, with $k > i$ and $l > j$.

For instance, in the example $a_{12} = 11$ and $a_{43} = 9$ forms an inversion, and there are $6$ inversions altogether.

We can show that, in general, the number of inversions in $A$ is

$$\binom{\frac{(p-1)(q-1)}{2}}{2}.$$

Is there a reference for this result?

• You may like to assume $\gcd(p,q)=1$. – T. Amdeberhan Feb 10 '17 at 12:56
• For the less visual thinkers: You are counting the pairs $\left(i,j\right) \in \left\{0,1,\ldots,pq-1\right\}^2$ satisfying $i > j$ but $i \% p < j \% p$ and $i \% q < j \% q$, where $k \% r$ means the remainder of $k$ modulo $r$. – darij grinberg Mar 13 '17 at 9:09