4-6 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 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} $$

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] \le A[i, j + 1] + A[i + 1, j].$$

($\textit{Hint:}$ For the "if" part, use induction seperately on rows and columns.)

b. The following array is not Monge. Change one element in order to make it Monge. ($\textit{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} $$

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

d. 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 determine the leftmost minimum for each row in $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.

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

a. The "only if" part is trivial, it follows form the definition of Monge array.

As for the "if" part, let's first prove that

$$ \begin{aligned} A[i, j] + A[i + 1, j + 1] & \le A[i, j + 1] + A[i + 1, j] \\ \Rightarrow A[i, j] + A[k, j + 1] & \le A[i, j + 1] + A[k, j], \end{aligned} $$

where $i < k$.

Let's prove it by induction. The base case of $k = i + 1$ is given. As for the inductive step, we assume it holds for $k = i + n$ and we want to prove it for $k + 1 = i + n + 1$. If we add the given to the assumption, we get

$$ \begin{aligned} A[i, j] + A[k, j + 1] & \le A[i, j + 1] + A[k, j] & \text{(assumption)} \\ A[k, j] + A[k + 1, j + 1] & \le A[k, j + 1] + A[k + 1, j] & \text{(given)} \\ \Rightarrow A[i, j] + A[k, j + 1] + A[k, j] + A[k + 1, j + 1] & \le A[i, j + 1] + A[k, j] + A[k, j + 1] + A[k + 1, j] \\ \Rightarrow A[i, j] + A[k + 1, j + 1] & \le A[i, j + 1] + A[k + 1, j] \end{aligned} $$

b.

$$ \begin{matrix} 37 & 23 & \mathbf{24} & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \\ \end{matrix} $$

c. Let $a_i$ and $b_j$ be the leftmost minimal elements on rows $a$ and $b$ and let's assume that $i > j$. Then we have

$$A[j, a] + A[i, b] \le A[i, a] + A[j, b].$$

But

$$ \begin{aligned} A[j, a] \ge A[i, a] & (a_i \text{ is minimal}) \\ A[i, b] \ge A[j, b] & (b_j \text{ is minimal}) \\ \end{aligned} $$

Which implies that

$$ \begin{aligned} A[j, a] + A[i, b] & \ge A[i, a] + A[j, b] \\ A[j, a] + A[i, b] & = A[i, a] + A[j, b] \end{aligned} $$

Which in turn implies that either:

$$ \begin{aligned} A[j, b] < A[i, b] & \Rightarrow A[i, a] > A[j, a] \Rightarrow a_i \text{ is not minimal} \\ A[j, b] = A[i, b] & \Rightarrow b_j \text{ is not the leftmost minimal} \end{aligned} $$

d. If $\mu_i$ is the index of the $i$-th row's leftmost minimum, then we have

$$\mu_{i - 1} \le \mu_i \le \mu_{i + 1}.$$

For $i = 2k + 1$, $k \ge 0$, finding $\mu_i$ takes $\mu_{i + 1} - \mu_{i - 1} + 1$ steps at most, since we only need to compare with those numbers. Thus

$$ \begin{aligned} T(m, n) & = \sum_{i = 0}^{m / 2 - 1} (\mu_{2i + 2} - \mu_{2i} + 1) \\ & = \sum_{i = 0}^{m / 2 - 1} \mu_{2i + 2} - \sum_{i = 0}^{m / 2 - 1}\mu_{2i} + m / 2 \\ & = \sum_{i = 1}^{m / 2} \mu_{2i} - \sum_{i = 0}^{m / 2 - 1}\mu_{2i} + m / 2 \\ &= \mu_m - \mu_0 + m / 2 \\ & = n + m / 2 \\ & = O(m + n). \end{aligned} $$

e. The divide time is $O(1)$, the conquer part is $T(m / 2)$ and the merge part is $O(m + n)$. Thus,

$$ \begin{aligned} T(m) & = T(m / 2) + cn + dm \\ & = cn + dm + cn + dm / 2 + cn + dm / 4 + \cdots \\ & = \sum_{i = 0}^{\lg m - 1}cn + \sum_{i = 0}^{\lg m - 1}\frac{dm}{2^i} \\ & = cn\lg m + dm\sum_{i = 0}^{\lg m - 1} \\ & < cn\lg m + 2dm \\ & = O(n\lg m + m). \end{aligned} $$