Monge arrays
An \(m \times n\) array \(A\) of real numbers is a Monge array if for all \(i, j, k,\) and \(l\) such that \(1 \le i < k \le m\) and \(1 \le j < l \le n\), we have:
\[A[i,j] + A[k,l] \le 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:
\[\begin{matrix} 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{matrix}\]
Prove that an array is a Monge if and only if for all \(i = 1, 2, \ldots, m-1\) and \(j = 1, 2, \ldots, n-1\), we have
\[A[i,j] + A[i+1,j+1] \le A[i,j+1] + A[i+1,j]\](Hint: For the “if” part, use induction separately on rows and columns.)
The following array is not a Monge. Change one element in order to make it Monge. (Hint: Use part (a).)
\[\begin{matrix} 37 & 23 & 22 & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \end{matrix}\]Let \(f(i)\) be the index of the column containing the leftmost minimum element of row \(i\). Prove that \(f(1) \le f(2) \le \cdots \le f(m)\) for any \(m \times n\) Monge array.
Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of an \(m \times n\) Monge array \(A\):
Construct a submatrix \(A'\) of \(A\) consisting of the even-numbered rows of \(A\). Recursively compute 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.
Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is \(O(m + n\lg m)\).
Think of the Monge property as a kind of “anti-crossing” constraint. If you imagine drawing lines from the upper-left to lower-right and from upper-right to lower-left, the Monge property says the non-crossing pair (upper-left + lower-right) is no larger than the crossing pair. Many real-world problems naturally have this structure, particularly those involving distances, costs, or optimal substructure in dynamic programming.
A
Assume the adjacent-pair condition holds. We prove the general Monge condition by induction.
Base case: For \(k = i+1\) and \(l = j+1\), this is exactly the adjacent condition.
Inductive step:
Row induction: Suppose \(A[i,j] + A[k,l] \le A[i,l] + A[k,j]\) holds. We prove it for \(k+1\):
\[\begin{align*} A[i,j] + A[k+1,l] &\le A[i,j] + A[k,l] + (A[k+1,l] - A[k,l])\\ &\le A[i,l] + A[k,j] + (A[k+1,l] - A[k,l])\\ &= A[i,l] + A[k+1,j] + (A[k,l] - A[k,l])\\ &\quad - (A[k+1,j] - A[k,j]) + (A[k+1,l] - A[k,l])\\ &\le A[i,l] + A[k+1,j] \end{align*}\]The last inequality follows from applying the adjacent condition to rows \(k\) and \(k+1\), columns \(j\) and \(l\).
Column induction: Similar argument extends to \(l+1\).
Proof: The general condition with \(k=i+1, l=j+1\) gives the adjacent condition directly.
B
Given array:
\[\begin{matrix} 37 & 23 & 22 & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \end{matrix}\]Check adjacent pairs systematically using the condition \(A[i,j] + A[i+1,j+1] \le A[i,j+1] + A[i+1,j]\).
For rows 1-2, columns 2-3:
\(A[1,2] + A[2,3] = 23 + 7 = 30\) \(A[1,3] + A[2,2] = 22 + 6 = 28\)
We have \(30 > 28\), which violates the Monge property.
Change: Modify \(A[2,2]\) from \(6\) to \(11\) (or adjust other elements).
Verification: \(A[1,2] + A[2,3] = 23 + 7 = 30\) and \(A[1,3] + A[2,2] = 22 + 11 = 33\), so \(30 \le 33\) ✓
C
Let \(f(i)\) be the column index of the leftmost minimum in row \(i\).
This property is remarkable: it says that as we go down the rows of a Monge array, the position of the minimum in each row never moves to the left. It can only stay in place or shift to the right. This structure is what makes efficient algorithms possible, as we’ll see in part D.
Proof by contradiction:
Assume \(f(i) > f(i+1)\) for some \(i\). Let \(j = f(i+1)\) and \(l = f(i)\).
By definition:
- \(A[i+1, j] \le A[i+1, l]\) (\(j\) is leftmost min of row \(i+1\))
- \(A[i, l] \le A[i, j]\) (\(l\) is leftmost min of row \(i\), and \(j < l\))
Adding these: \(A[i+1,j] + A[i,l] \le A[i+1,l] + A[i,j]\)
But the Monge property requires:
\(A[i,j] + A[i+1,l] \le A[i,l] + A[i+1,j]\)
Rearranging: \(A[i+1,j] + A[i,l] \ge A[i+1,l] + A[i,j]\)
For both to hold, we need equality:
\(A[i+1,j] + A[i,l] = A[i+1,l] + A[i,j]\)
But this contradicts our assumption that \(f(i) > f(i+1)\) (strict inequality in definitions).
D
The clever idea here is to solve only half the problem recursively (the even rows), and then use the leftmost minima property to efficiently fill in the other half (the odd rows). For each odd row \(i\), we know from part C that its minimum lies between the minima of rows \(i-1\) and \(i+1\), dramatically reducing our search space.
Algorithm:
- Construct submatrix \(A'\) with even-numbered rows of \(A\)
- Recursively find leftmost minima for each row of \(A'\)
- Compute leftmost minima for odd-numbered rows of \(A\) using the results from step 2
Computing odd-row minima in \(O(m+n)\) time:
For odd row \(i\), we know:
- \(f(i-1)\) (from even row \(i-1\), found recursively)
- \(f(i+1)\) (from even row \(i+1\), found recursively)
By part C: \(f(i-1) \le f(i) \le f(i+1)\)
So we only search columns \([f(i-1), f(i+1)]\) for row \(i\).
Total work for all \(m/2\) odd rows: Each column is examined at most twice (once from above, once from below), giving \(O(m+n)\) total.
E
Recurrence:
\[T(m,n) = T(m/2, n) + O(m + n)\]Solution:
\[\begin{align*} T(m,n) &= T(m/2,n) + c(m+n)\\ &= T(m/4,n) + c(m/2+n) + c(m+n)\\ &= T(m/2^k,n) + c\sum_{i=0}^{k-1}(m/2^i + n)\\ &= T(1,n) + c(2m + kn)\\ &= O(n) + c(2m + n\lg m)\\ &= O(m + n\lg m) \end{align*}\]where \(k = \lg m\) (when \(m/2^k = 1\)).