## § Monge Matrix

- Suppose we two line segments
`AB`

, `CD`

:

```
A C
@ @
@ @
@ @
B D
```

- What is the relationship between the lengths
`|AC| + |BD|`

(straight lines) versus `|AC| + |BD|`

(diagonals)? - Draw the diagonal, label the point of intersection of diagonals as
`I`

.

```
A---C
@\ /@
@ I @
@/ \@
B---D
```

- By triangle inequality, we have that
`AI + IC > AC`

and `BI + ID > BD`

. Adding these up, we get `(AI + IC) + (BI + ID) > AC + BD`

. - Rearranging we get
`(AI + ID) + (BI + IC) > AC + BD`

, which is equal to `AD + BC > AC + BD`

. - So, the
*sum of lengths between opposite points is greater than sum of lengths between non-opposite points *. - If we think of this as a matrix
`dist[A/B][C/D]`

, we have that `dist[a][d] + dist[b][c] > dist[a][c] + dist[b][d]`

. - If we replace
`A=0`

, `B=1`

, `C=0`

, `D=1`

(since those are the indexes of the points on the two line segments), we get `dist[0][1] + dist[1][0] > dist[0][0] + dist[1][1]`

- If we generalize to
*sets * of points on a line, let's have the indexes `i, j`

. Then the condition would read `dist[i][j] + dist[j][i] > dist[i][i] + dist[j][j]`

. - A matrix
`dist[.][.]`

which obeys this condition is said to be a *Monge Matrix *.

#### § Theorem: Monge matrices are totally monotone

#### § Theorem: totally monotone matrices have ascending row minima

#### § 1D 1D DP [TODO ]

- https://robert1003.github.io/2020/02/29/dp-opt-knuth.html
- Suppose we have a dp $dp[r] = \min_{0 \leq l \leq r} f(l, r)$. That is, we need to find row minima for each row $r$ in a 2D matrix.
- Now assume that $f(l, r)$ has ascending row minima