# Monge array

In

computer science, an

*m*-by-

*n* array of

real numbers is a

**Monge array** if for all

*i*,

*j*,

*k*,

*l* such that:

- and

one obtains:

So whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection points, 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.

This array is a Monge array:

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

It holds that 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.

Monge arrays are useful for keeping growth of functions in O(`n`log `n`) time or less.

See also: