# Monge array

This article needs additional citations for verification. (September 2012) (Learn how and when to remove this template message) |

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. The four elements are:

- 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.

## Properties[edit]

- The above definition is equivalent to the statement

- A matrix is a Monge array if and only if for all and .

- Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array.
- Any linear combination with non-negative coefficients of Monge arrays is itself a Monge array.
- One interesting property of Monge arrays is that if you mark with a circle the leftmost minimum of each row, you will discover that your circles march downward to the right; that is to say, if , then for all . Symmetrically, if you mark the uppermost minimum of each column, your circles will march rightwards and downwards. The row and column
*maxima*march in the opposite direction: upwards to the right and downwards to the left. - The notion of
*weak Monge arrays*has been proposed; a weak Monge array is a square*n*-by-*n*matrix which satisfies the Monge property only for all . - Every Monge array is totally monotone, meaning that its row minima occur in a nondecreasing sequence of columns, and that the same property is true for every subarray. This property allows the row minima to be found quickly by using the SMAWK algorithm.
- Monge matrix is just another name for submodular function of two discrete variables. Precisely,
*A*is a Monge matrix if and only if*A*[*i*,*j*] is a submodular function of variables*i*,*j*.

## Applications[edit]

- 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, that the problem admits of easy solutions when the distance matrix can be written as a Supnick matrix). Note that any linear combination of Supnick matrices is itself a Supnick matrix.

## References[edit]

**^**Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization".*Discrete Applied Mathematics*. ELSEVIER.**70**(2): 95–96. doi:10.1016/0166-218x(95)00103-x.

- Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "Some problems around travelling salesmen, dart boards, and euro-coins" (PDF).
*Bulletin of the European Association for Theoretical Computer Science*. EATCS.**90**: 43–52. ISSN 0252-9742.