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.



Most inconsistent ranking
$\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$.
> 
> 
> 


