Monge array

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 $\scriptstyle i,\, j,\, k,\, \ell$ such that

:$1\le i < k\le m\text1\le j < \ell\le n$

one obtains

:A ,j+ A ,\ell\le A ,\ell+ A ,j\,

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

For example, take the intersection of rows 2 and 4 with columns 1 and 5.
The four elements are:
:$\begin 17 & 23\\ 11 & 7 \end$

: 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

*The above definition is equivalent to the statement
:A matrix is a Monge array if and only if A ,j+ A +1,j+1le A ,j+1+ A +1,j/math> for all $1\le i < m$ and $1\le j < n$.

*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 f(x) = \arg\min_ A ,i/math>, then $f(j)\le f(j+1)$ for all $1\le j < n$. 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 A ,i+ A ,sle A ,s+ A ,i/math> only for all $1\le i < r,s\le n$.
*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

*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). Any linear combination of Supnick matrices is itself a Supnick matrix.

References

* {{cite journal , title = Some problems around travelling salesmen, dart boards, and euro-coins , first1 = Vladimir G. , last1 = Deineko , first2 = Gerhard J. , last2 = Woeginger , author2-link = Gerhard J. Woeginger , journal = Bulletin of the European Association for Theoretical Computer Science , publisher = EATCS , volume = 90 , date=October 2006 , issn = 0252-9742 , pages = 43–52 , url = http://alexandria.tue.nl/openaccess/Metis211810.pdf , format = PDF

Theoretical computer science