# Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) > 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P[i]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=[3, 1, 2]$ and $M=$

2 6 7
3 4 8
1 5 9


According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$. Observe that there are 5 pairs in the Cartesian product $\{2,6,7\}\times\{1,5,9\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).
More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L_m$ for all $m$, and $3 \in L_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L_m$ (why?).
It remains to determine $L_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.
• thanks a lot for your kind help....yes,for a cycle of length 1 or 2, it is not possible to satisfy the constraint for obvious reason..but what actually you mean by $L_{m}$? is it the set of cycle size for which solution exists? If so, then also how can I generate the matrix M efficiently? Jul 9, 2014 at 3:09
• @user3724568 $L_m$ is the set of all $k$ such that a solution exists for $k = n$ and $P = 2\;3\;\cdots\;k\;1$. I suspect that you would be able to come up with a simple criterion for whether $k \in L_m$, a criterion that will come with an explicit construction. One you know how to solve single cycles, you should be able to solve the general case. Jul 9, 2014 at 3:38
• So,is it like $L_{1}$ and $L_{2}$ are empty,then $L_{3}$=3,$L_{4}$=4,$L_{5}$=5.$L_{6}$={3,6},$L_{7}$={3,4,7} and so on...but what's next? Jul 9, 2014 at 3:58