Most inconsistent ranking

Question

A matrix of $k$ rows and $n$ columns is filled with the numbers $1,2,\ldots,k$ such that the following conditions are satisfied:

1. Every column contain all the numbers form 1 to $k$ without repetition.
2. The variance of the elements of each row is calculated. The matrix is filled in such a way that the total sum $S_{kn}$ of the variance of each row is maximized.
3. $k < n < \infty$.

Questions:

1. What is the representation of the maximum value of $S_{kn}$ in a closed form in terms of $k$ and $n$? If exact representaion is not possible, can we have the upper and lower bound.
2. Is there an algorithm to fill the matrix such that $S_{kn}$ is maximized?
3. If repetition is allowed, what would be the answers for the above two questions.

Motivation: I am doing a worst case scenario analysis of the theoretically most inconsistent ranking where I need the solution of the following problem. In my problem, I have a ranking system which gave me the rank matrix. In the best case when the ranking system is completely consistent, the variance of each row will be zero and hence the total sum will be zero. In my case I have a finite total sum of variance say $S$ and I want to compare it against the worst or the maximum possible total sum $S_{kn}$ in order to quantify how consistent the rank matrix is.

Answer 1

$\newcommand{\E}{\mathrm{E}}$ $\newcommand{\Var}{\mathrm{Var}}$ $\newcommand{\Cov}{\mathrm{Cov}}$ Extending Kevin's answer let me show that

$$S_{k,n} \leq \frac{k^3-k}{12}.$$

It is easy to see that $$\Var(X) \leq \E\[(X-c)^2\]$$ for any random variable $X$ and any constant $c$.

Let $a_\{i,j\}$ denote the entry of the matrix on the intersection of $i^\mathrm{th}$ row and $j^\mathrm{th}$ column. Let $R_i$ (resp. $C_j$) be the random variables corresponding to uniformly sampling entries of $i^\mathrm{th}$ row (resp. $j^\mathrm{th}$ column). Then

\begin{align*} S_{k,n} &= \max \sum_{i=1}^k \Var(R_i) \leq \sum_{i=1}^k \E\[(R_i - \frac{k+1}{2})^2\]=\frac{1}{n}\sum_{1\leq i \leq k, 1 \leq j \leq n} ( a_{ij}-(k+1)/2)^2 \newline &= \frac{k}{n}\sum_{j=1}^n \Var(C_j)= \frac{k}{n} \cdot n \cdot \frac{k^2-1}{12} \end{align*}

It is clear that the bound is achieved if and only if the average value of each row is $(k+1)/2$. Examples with this property can be constructed for all even $n$. It is also easy to see that for fixed $k$ and $n \to \infty$ one can make the row averages be arbitrarily close to $(k+1)/2$ and thus the total variance arbitrarily close to the upper bound.

If $k$ is even and $n$ is odd then the bound can not be achieved exactly, as $n(k+1)/2$ is not integral. When $k$ is odd and $n=3$ then one can have $i^\mathrm{th}$ row consisting of $$\langle i; (i + (k-1)/2) \:\mathrm{mod}\: k; (k-2i +2) \:\mathrm{mod}\: k \rangle.$$ Combining this construction with pairs of ``reverse" columns, one achieves the bound for all $n \geq 3$. To summarize:

• $\max S_{k,n} = \frac{k^3-k}{12}$, when $n$ is even, or $k$ is odd and $n \geq 3$;

• $\max S_{k,n} < \frac{k^3-k}{12}$, otherwise, but $\lim_{n \to \infty} \max S_{k,n}=\frac{k^3-k}{12}$ for all $k$.

Answer 2

Some trivial cases:

• $k=1$: $S_{1,n} = 0$.
• $n=1$: $S_{k,1} = 0$.
• $k=2$: Say you have $n_1$ copies of $\langle 1,2 \rangle$ and $n_2$ copies of $\langle 2,1\rangle$. The variance of each row is $n_1 n_2 /n^2$, which is maximized with $n_1 = \lfloor n/2 \rfloor$. That is, $$S_{k,n} = \frac{2 \lfloor n/2 \rfloor \cdot \lceil n/2 \rceil}{n^2}.$$ That this is already parity dependent does not bode well for finding an exact formula for higher $k$.
• $k=3$: Computations for small $n$ indicate that $S_{3,n} = 2$, achieved in many ways, including taking $n/2$ copies of $\langle 1,2,\dots,k\rangle$ and $n/2$ copies of $\langle k,k-1,\dots,1\rangle$, when $n$ is even, and when $n$ is odd taking one copy of each of $\langle 1,2,3\rangle, \langle 2,3,1\rangle, \langle 3,1,2\rangle$ and splitting the rest evenly between $\langle 1,2,3 \rangle$ and $\langle 3,2,1\rangle$. That the formula comes out so clean for $k=3$ is encouraging.
• $n$ even: By taking $n/2$ copies of $\langle 1,2,\dots,k\rangle$ and $n/2$ copies of $\langle k,\dots,2,1\rangle$, we get $$S_{k,n} \geq \frac{k^3-k}{12}.$$ This bound appears to be sharp for even $n$.

If you're interested in fixed $k$, $n\to\infty$ or in fixed $n$, $k\to\infty$, the problem would be more tractable.

[Comment: I'm using the variance, not the sample variance. The two problems are equivalent, of course, but for reporting values this is relevant.]