# 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

## 1 Answer

I do not know of a reference. I have a different interest in results like these which I include here.

Color the left and top borders red, and ask for a specific interval of consecutive numbers that will be red. One can show that at most two consecutive numbers can be red, unless one chooses p to be 2, then one can get 3 consecutive numbers to be red.

So what? Generalizing to higher dimensions, a similar construction for three dimensions with the numbering proceeding in the direction (1,1,1) shows that you can get anywhere from 3 up to 5 consecutive numbers colored red. Since we are using a torus topology (oh, and I count pq followed by 1 as being consecutive), it turns out that it doesn't matter which slices we color, as long as exactly one slice (of codimension 1) perpendicular to each axis is chosen. For d dimensions, we can go from d consecutive red numbers up to a number I call C(d)-1, which is the maximum over all choices of pairwise coprime edges p,q,...,r.

Here C(d) is a function defined by Ernst Jacobsthal, which is the maximum over all integers n with d distinct prime factors of g(n), which in turn is the smallest number in which any interval of length g(n) is guaranteed to have a number coprime to n. It is conjectured that C(d) has growth less than quadratic in d, but this is not known.

Gerhard "Following A Path Less Taken" Paseman, 2017.02.10.