Monge array
|
|
Monge arrays, or Monge matrices, are mathematical objects used primarily in computer science. They are named for their discoverer, the French mathematician Gaspard Monge.
An m-by-n matrix is said to be a Monge array if, for all i, j, k, l such that
- <math>1\le i < k\le m<math> and <math>1\le j < l\le n<math>
one obtains
- <math>A[i,j] + A[k,l] \le A[i,l] + A[k,j]<math>.
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 matrix is a Monge array:
- <math>
\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}<math>
For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are:
- <math>
\begin{bmatrix} 17 & 23\\ 11 & 7 \end{bmatrix}<math>
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.
Properties
- The above definition is equivalent to the statement
- A matrix is a Monge array if and only if <math>A[i,j] + A[i+1,j+1]\le A[i,j+1] + A[i+1,j]<math> for all <math>1\le i < m<math> and <math>1\le j < n<math>.
- Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array.
- Any linear combination 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 <math>f(x) = \min_{i\in 1..m} A[i,x]<math>, then <math>f(j)\le f(j+1)<math> for all <math>1\le j < n<math>. 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 <math>A[i,i] + A[r,s]\le A[i,s] + A[r,i]<math> only for all <math>1\le i < r,s\le n<math>.
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). Note that any linear combination of Supnick matrices is itself a Supnick matrix.