Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
How is the sum of the variance of the rows defined? –  Gerry Myerson Feb 19 '13 at 11:32
    
@ Gerry, I have now defined the sum of variance of the rows in condition number 2. –  Nilotpal Sinha Feb 19 '13 at 11:42
    
Call the matrix $M=(m_{ij})$. Then, if I understand correctly, ``total sum of the variance of each row'' is defined to be $\sum_{i=1}^k \frac1n \sum_{j=1}^n (m_{ij}-\frac 1n \sum_{\ell=1}^n m_{i\ell})^2$. –  Kevin O'Bryant Feb 19 '13 at 16:50
    
@Kevin: Yes this is the right understanding –  Nilotpal Sinha Feb 19 '13 at 17:36

2 Answers 2

up vote 3 down vote accepted

$\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$.

share|improve this answer

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.]

share|improve this answer
1  
Note that for $k=n$, if we take a latin square, we get the same: for even $n=2r$, $S_{k,n}\ge\frac12\sum_{j=1}^r(2j-1)^2=\frac{n(n^2-1)}{12}$, for odd $n=2r-1$, $S_{k,n}\ge 2\sum_{j=1}^{r-1}j^2=\frac{n(n^2-1)}{12}$. And as you say, this sort of ranking seems to be most inconsistent already. –  Wolfgang Feb 19 '13 at 17:06
    
@Kevin: Thanks for the insight and the lower bound. 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. I am updating this comment in the question. –  Nilotpal Sinha Feb 19 '13 at 18:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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