# finding permutations which fulfills given conditions

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be a finite set. Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_1$ and $>_2$ on $K$ such that $$s \, >_1 \,\, t \text{ and } x \, >_2 \,\, y$$ if and only if $$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

• I have submitted an edit of the question so it is clearer (the way I understood it). If that was not the initial meaning of the question you can delete it: I have left your question untouched.
– Gopi
Commented Oct 19, 2011 at 17:53
• It's worth noting that in the lattice induced by the product order of $A_1$ and $A_2$, the point $(k_2, k'_2)$ is the meet of $(k_1, k'_2), (k_2, k'_1)$ and the point $(k_1, k'_1)$ is the join. So actually your condition is merely the definition of supermodularity for $g$. So rephrased, your question is: Is there a way, for any function $g$, to construct a product lattice from two total orders so that $g$ is supermodular ? Commented Oct 19, 2011 at 22:33
• I'm concerned with "if and only if" in the REFORMULATION. For example, if g is a constant function, g is supermodular. But the condition in the REFORMULATION is not satisfied because for all 4-tuples (k1,k2,k1',k2') the inequality is satisfied (with equality). Commented Oct 19, 2011 at 23:05
• Another interpretation might be this: can we permute the rows and columns of a matrix to make it "supermodular"? (Again, assuming that the "if and only if" part is wrong.) Commented Oct 19, 2011 at 23:35
• @KostiaAntoniuk: I see. but to be honest, your first question was very cryptic. This one makes more sense :) Commented Oct 20, 2011 at 6:50

Jukka's comment reminds me of the following reference.

If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix. There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).

The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.

• Thnx! Definitely, I will read those papers. Indeed, I'm interested in the question is the set of permuted inverse Monge matrices a convex set. I hope after reading those paper I will now the answer on this. Commented Oct 20, 2011 at 6:35