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.

Read more about Monge Array:  Properties, Applications

Other articles related to "monge array, monge":

Monge Array - Applications
... A square Monge matrix which is also symmetric about its main diagonal is called a Supnick matrix (after Fred Supnick) this kind of matrix has applications to the traveling salesman problem (namely ...

Famous quotes containing the word array:

    Any one who knows what the worth of family affection is among the lower classes, and who has seen the array of little portraits stuck over a labourer’s fireplace ... will perhaps feel with me that in counteracting the tendencies, social and industrial, which every day are sapping the healthier family affections, the sixpenny photograph is doing more for the poor than all the philanthropists in the world.
    Macmillan’s Magazine (London, September 1871)