Monge array

In mathematics applied to computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge.

An m-by-n matrix is said to be a Monge array if, for all ${\displaystyle i,j,k,\ell }$ such that $${\displaystyle 1\leq i<k\leq m{\text{ and }}1\leq j<\ell \leq n,}$$ one obtains $${\displaystyle A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].}$$ In other words, for any two rows and two columns of a Monge array, the four elements at the intersection points (a 2 × 2 sub-matrix) have the property that the sum of the upper-left and lower-right elements (on the main diagonal) is less than or equal to the sum of the lower-left and upper-right elements (on the antidiagonal).

This matrix is a Monge array:

${\displaystyle {\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}}$

For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are $${\displaystyle {\begin{bmatrix}17&23\\11&7\end{bmatrix}}.}$$ The sum of the upper-left and lower-right elements (17 + 7 = 24) is not larger than the sum of the lower-left and upper-right elements (23 + 11 = 34).