4-7 Monge arrays

An m x n array A of real numbers is a Monge array if for all i , j , k, and L such

that 1 <=i < k <= m and 1 <= j < L<= n, we have

A[i,j]+A[k,L]<=A[i,L] + A[k,j].

In other words, whenever we pick two rows and two columns of a Monge array and

consider the four elements at the intersections of the rows and the columns, 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. For example, the following array is Monge:

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

a. Prove that an array is Monge if and only if for all i = 1; 2,m - 1 and

j = 1, 2, n-1, we have

A[i,j] + A[i+1, j+1]<=A[i,j +1] + A[i, +1,j]

(Hint: For the

b. The following array is not Monge. Change one element in order to make it

Monge. (Hint: Use part (a).)

37 23 22 32

21 6 7 10

53 34 30 31

32 13 9 6

43 21 15 8

c. Let f (i) be the index of the column containing the leftmost minimum element

of row i . Prove that f(1)<=f(n)<=.<= f(m) for any m x n Monge array. (5 points)