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 <math>i, j, k, \ell</math> such that
<math display="block">1\le i < k\le m\text{ and }1\le j < \ell\le n,</math>
one obtains
<math display=block>
A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j].
</math>
In other words, for any two rows and two columns of a Monge array, the four elements at the intersection points (a 2 × 2 sub-matrix) have the property that the sum of the upper-left and lower-right elements (on the main diagonal) is less than or equal to the sum of the lower-left and upper-right elements (on the antidiagonal).
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 display=block>
\begin{bmatrix}
17 & 23\\
11 & 7 \end{bmatrix}.</math>
The sum of the upper-left and lower-right elements (17 + 7 = 24) is not larger than the sum of the lower-left and upper-right elements (23 + 11 = 34).
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>.
- A square Monge matrix which is also symmetric about its main diagonal is called a Supnick matrix (after Fred Supnick). Any linear combination of Supnick matrices is itself a Supnick matrix,