# Monge Array

Monge Array

In 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

So whenever we pick two rows and two columns of a Monge array (a 2 × 2 sub-matrix) and consider the four elements at the intersection points, 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:

$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:

$begin{bmatrix} 17 & 23\ 11 & 7 end{bmatrix}$
17 + 7 = 24
23 + 11 = 34

The sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements.