An \(m \times n\) array \(A\) of real numbers is a Monge array if for all \(i\), \(j\), \(k\), and \(l\) such that \(1 \leq i < k \leq m\) and \(1 \leq j < l \leq n\), we have

\(A[i, j] + A[k, l] \leq 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{array}{c c c c c} 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{array}\]

a. Prove that an array is 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] \leq 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] \leq A[i, j + 1] + A[i + 1, j] \implies A[i, j] + A[k, j + 1] \leq 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:

\[\begin{split} A[i, j] + A[k, j+1] + A[k, j] + A[k+1, j+1] & \leq A[i, j+1] + A[k, j] + A[k, j+1] + A[k+1, j] \\ A[i, j] + A[k+1, j+1] & \leq A[i, j+1] + A[k+1, j] \\ \end{split}\]

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.))

\[\begin{array}{c c c c} 37 & 23 & 22 & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \\ \end{array}\]

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] \leq B[i, j+1] + B[i+1, j] \quad \forall i = 1, 2, 3, 4 \quad \forall 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.

\[\begin{split} i = 1, j = 1 &: B[1, 1] + B[2, 2] \leq B[1, 2] + B[2, 1] & = 37 + 6 \leq 23 + 21 &= 43 \leq 44 \\ i = 1, j = 2 &: B[1, 2] + B[2, 3] \leq B[1, 3] + B[2, 2] & = 23 + 7 \leq 22 + 6 &= 30 \leq 28 \\ i = 1, j = 3 &: B[1, 3] + B[2, 4] \leq B[1, 4] + B[2, 3] & = 22 + 10 \leq 32 + 7 &= 32 \leq 39 \\ i = 2, j = 1 &: B[2, 1] + B[3, 2] \leq B[2, 2] + B[3, 1] & = 21 + 34 \leq 6 + 53 &= 55 \leq 59 \\ i = 2, j = 2 &: B[2, 2] + B[3, 3] \leq B[2, 3] + B[3, 2] & = 6 + 30 \leq 7 + 34 &= 36 \leq 41 \\ i = 2, j = 3 &: B[2, 3] + B[3, 4] \leq B[2, 4] + B[3, 3] & = 7 + 31 \leq 10 + 30 &= 38 \leq 40 \\ i = 3, j = 1 &: B[3, 1] + B[4, 2] \leq B[3, 2] + B[4, 1] & = 53 + 13 \leq 34 + 32 &= 66 \leq 66 \\ i = 3, j = 2 &: B[3, 2] + B[4, 3] \leq B[3, 3] + B[4, 2] & = 34 + 9 \leq 30 + 13 &= 43 \leq 43 \\ i = 3, j = 3 &: B[3, 3] + B[4, 4] \leq B[3, 4] + B[4, 3] & = 30 + 6 \leq 31 + 9 &= 36 \leq 40 \\ i = 4, j = 1 &: B[4, 1] + B[5, 2] \leq B[4, 2] + B[5, 1] & = 32 + 21 \leq 13 + 43 &= 53 \leq 56 \\ i = 4, j = 2 &: B[4, 2] + B[5, 3] \leq B[4, 3] + B[5, 2] & = 13 + 15 \leq 9 + 21 &= 28 \leq 30 \\ i = 4, j = 3 &: B[4, 3] + B[5, 4] \leq B[4, 4] + B[5, 3] & = 9 + 8 \leq 6 + 15 &= 17 \leq 31 \\ \end{split}\]

The 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) \leq f(2) \leq \cdots \leq f(m)\) for any \(m \times 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)] \leq 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)] \geq 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 \times 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 \(\lceil m / 2 \rceil\) odd-numbered rows, and so finding the leftmost minimum of each of them takes

\[\begin{split} \sum\limits_{k=1}^{\lceil m / 2 \rceil} (f(k+1) - f(k - 1) + 1) &= \lceil m / 2 \rceil \sum\limits_{k=1}^{\lceil m / 2 \rceil} (f(k+1) - f(k - 1) \\ &= O(m) + f(\lceil m / 2 \rceil) - f(1) \\ &= O(m + n) \\ \end{split}\]

e. Write the recurrence describing the running time of the algorithm described in part d. Show that its solution is \(O(m + n \log m)\).

\[\begin{split} T(n) &= T(m/2) + O(m + n) \\ &= T(m/2) + am + bn \\ &= am + bn + \frac{am}{2} + bn + \frac{am}{4} + bn + \dots \\ &= \sum\limits_{i=0}^{\log m - 1} \left(\frac{am}{2^i} + bn \right) \\ &\leq \left(am \sum\limits_{i=0}^{\infty} \frac{1}{2}^i \right) + bn \log m \\ &= am \left( \frac{1}{1 - \frac{1}{2}} \right) + bn \log m \\ &= 2am +bn \log m \\ &= O(m + n \log m) \\ \end{split}\]