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 i,j,k,ℓ such that 1≤i<k≤m and 1≤j<ℓ≤n, one obtains A[i,j]+A[k,ℓ]≤A[i,ℓ]+A[k,j]. 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:

[1017132823172216292324282234241113617745443237233633192167566515334]

For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are [1723117]. 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

A matrix is a Monge array if and only if A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j] for all 1≤i<m and 1≤j<n.

Applications

Monge matrices has applications in combinatorial optimization problems: