Monge arrays
An m×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:
1017132823172216292324282234241113617745443237233633192167566515334a. 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 “if” part, use inductions separately on rows and columns.)
First of all, the “only if” part of this statement is already implied by the definition of a Monge array. For the “if” part we will use induction to show that
A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]⟹A[i,j]+A[k,j+1]≤A[i,j+1]+A[k,j]where i<k. The base case of k=i+1 is given. Next by assuming that this holds for k=1+n we must prove that it also holds for k+1=i+n−1. Combining these two gives us:
A[i,j]+A[k,j+1]+A[k,j]+A[k+1,j+1]≤A[i,j+1]+A[k,j]+A[k,j+1]+A[k+1,j]A[i,j]+A[k+1,j+1]≤A[i,j+1]+A[k+1,j]which proves the inductive step. Employing this exact same approach on the rows which shows that this statement is indeed a restatement of the definition of Monge arrays.
b. The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a.))
37232232216710533430313213964321158
Let’s call this array B. Part a tells us that in order for B to be Monge, the following must be true:
B[i,j]+B[i+1,j+1]≤B[i,j+1]+B[i+1,j]∀i=1,2,3,4∀j=1,2,3(Where the bounds for i and j come from the size of the array). Since B is not Monge, it must be true that this does not hold in all cases.
i=1,j=1:B[1,1]+B[2,2]≤B[1,2]+B[2,1]=37+6≤23+21=43≤44i=1,j=2:B[1,2]+B[2,3]≤B[1,3]+B[2,2]=23+7≤22+6=30≤28i=1,j=3:B[1,3]+B[2,4]≤B[1,4]+B[2,3]=22+10≤32+7=32≤39i=2,j=1:B[2,1]+B[3,2]≤B[2,2]+B[3,1]=21+34≤6+53=55≤59i=2,j=2:B[2,2]+B[3,3]≤B[2,3]+B[3,2]=6+30≤7+34=36≤41i=2,j=3:B[2,3]+B[3,4]≤B[2,4]+B[3,3]=7+31≤10+30=38≤40i=3,j=1:B[3,1]+B[4,2]≤B[3,2]+B[4,1]=53+13≤34+32=66≤66i=3,j=2:B[3,2]+B[4,3]≤B[3,3]+B[4,2]=34+9≤30+13=43≤43i=3,j=3:B[3,3]+B[4,4]≤B[3,4]+B[4,3]=30+6≤31+9=36≤40i=4,j=1:B[4,1]+B[5,2]≤B[4,2]+B[5,1]=32+21≤13+43=53≤56i=4,j=2:B[4,2]+B[5,3]≤B[4,3]+B[5,2]=13+15≤9+21=28≤30i=4,j=3:B[4,3]+B[5,4]≤B[4,4]+B[5,3]=9+8≤6+15=17≤31The case that does not hold is where i=1 and j=2, therefore we must change one of these terms so that this case holds. Reducing B[1,2] by 2 will invalidate the case where i=1 and j=1 so we cannot use this value. Reducing B[2,3] by 2 will not invalidate any cases. Thus by setting B[2,3]=5 this array becomes Monge.
c. Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove that f(1)≤f(2)≤⋯≤f(m) for any m×n Monge array.
Suppose f(i)>f(i+1). Based on the definition of Monge arrays, this would mean that in dealing with rows i and i+1 and columns f(i) and f(i+1) the following must be true:
A[i,f(i+1)]+A[i+1,f(i)]≤A[i,f(i)]+A[i+1,f(i+1)]however this contradicts the definition of the function f which states that A[i,f(i+1)]>A[i,f(i)] and A[i+1,f(i)]≥A[i+1,f(i+1)].
d. Here is a description of a divide-and-conquer algorithm that computes the left-most minimum element in each row of an m×n Monge array A:
Construct a submatrix A′ of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row of A′. Then compute the leftmost minimum in the odd-numbered rows of A.
Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that the leftmost minimum of the even-numbered rows is known) in O(m+n) time.
Based on the conclusion of part c we can restrict the elements which we need to examine. For each odd row k we need only consult the elements between f(k−1) and f(k+1) where f(0)=1 and f(m)=f(m+1)=n.
The matrix has ⌈m/2⌉ odd-numbered rows, and so finding the leftmost minimum of each of them takes
⌈m/2⌉∑k=1(f(k+1)−f(k−1)+1)=⌈m/2⌉⌈m/2⌉∑k=1(f(k+1)−f(k−1)=O(m)+f(⌈m/2⌉)−f(1)=O(m+n)T(n)=T(m/2)+O(m+n)=T(m/2)+am+bn=am+bn+am2+bn+am4+bn+…=logm−1∑i=0(am2i+bn)≤(am∞∑i=012i)+bnlogm=am(11−12)+bnlogm=2am+bnlogm=O(m+nlogm)e. Write the recurrence describing the running time of the algorithm described in part d. Show that its solution is O(m+nlogm).