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
such that one obtains[1] So for any two rows and two columns of a Monge array (a 2 × 2 sub-matrix) the four elements at the intersection points have the property that the sum of the upper-left and lower right elements (across the main diagonal) is less than or equal to the sum of the lower-left and upper-right elements (across the antidiagonal).
This matrix is a Monge array: For example, take the intersection of rows 2 and 4 with columns 1 and 5.
Monge matrices has applications in combinatorial optimization problems: