totally monotone matrix

a matrix $\text{[math]}$ is totally monotone if for every $\text{[math]}$ such that $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ , we also have $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 chapter 8.1 total monotonicity and the monge property]

/home/mahmooz/brain/pen/1735760658.297685.xopp

a matrix $\text{[math]}$ is convex monge (concave monge) if for every $\text{[math]}$ such that $\text{[math]}$ , we have $\text{[math]}$ ( $\text{[math]}$ ). it is immediate that if $\text{[math]}$ is convex monge then it is totally monotone. it is also easy to see that the matrix obtained by transposing $\text{[math]}$ is also totally monotone.
[cite:;taken from @graph_klein_2024 chapter 8.1 total monotonicity and the monge property]

we define the upper triangle of $\text{[math]}$ to be the elements of $\text{[math]}$ on or above the main diagonal. more precisely, the upper triangle of $\text{[math]}$ is the portion $\text{[math]}$ of $\text{[math]}$ . similarly, the lower triangle of $\text{[math]}$ consists of all the elements on or below the main diagonal of $\text{[math]}$ .

we will be interested in computing all column minima of a monge matrix $\text{[math]}$ . let $\text{[math]}$ denote the number of rows (or columns) of $\text{[math]}$ , and assume $\text{[math]}$ has the convex monge property. for a subset $\text{[math]}$ of the rows of $\text{[math]}$ , the lower envelope of the rows $\text{[math]}$ of $\text{[math]}$ is the real-valued function $\text{[math]}$ on the integers in $\text{[math]}$ defined by $\text{[math]}$ (the minima of each column $\text{[math]}$ restricted to rows $\text{[math]}$ ).

let $\text{[math]}$ be a convex monge matrix. for any subset $\text{[math]}$ of the rows of $\text{[math]}$ , the function $\text{[math]}$ is monotonically non-increasing.
[cite:;taken from @graph_klein_2024 lemma 8.1.2]

suppose $\text{[math]}$ . then, for $\text{[math]}$ , $\text{[math]}$ . since $\text{[math]}$ is convex monge, $\text{[math]}$ . therefore, for $\text{[math]}$ , $\text{[math]}$ , so $\text{[math]}$ .

a breakpoint of $\text{[math]}$ is a pair of integers $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ (the row $\text{[math]}$ contains the minima of column $\text{[math]}$ but not $\text{[math]}$ ). for $\text{[math]}$ , we always consider $\text{[math]}$ to be a breakpoint of $\text{[math]}$ . for notational convenience we also consider the pair $\text{[math]}$ as a trivial breakpoint. if $\text{[math]}$ are the breakpoints of the lower envelope of $\text{[math]}$ , ordered such that $\text{[math]}$ , then the minimum elements in each column in the range $\text{[math]}$ is at row $\text{[math]}$ .

/home/mahmooz/brain/pen/1736007524.1316235.xopp
we focus our attention on finding the breakpoints of the lower envelope of $\text{[math]}$ , since, given the breakpoints, all column minima can be recovered in $\text{[math]}$ time. lem-sssp-1 suggests the following procedure for finding the breakpoints of the lower envelope of a convex monge matrix $\text{[math]}$ . the procedure maintains the lower envelope of an increasingly larger prefix $\text{[math]}$ of the rows of $\text{[math]}$ . initially $\text{[math]}$ consists of just the first row of $\text{[math]}$ , and the breakpoints of $\text{[math]}$ are just $\text{[math]}$ and $\text{[math]}$ . let $\text{[math]}$ be the non-trivial breakpoints of the lower envelope of the first $\text{[math]}$ rows of $\text{[math]}$ , ordered such that $\text{[math]}$ . note that, by lem-sssp-1, this implies $\text{[math]}$ . to obtain the breakpoints of the lower envelope of the first $\text{[math]}$ rows of $\text{[math]}$ , the procedure compares $\text{[math]}$ and $\text{[math]}$ for increasing values of $\text{[math]}$ , until it encounters an index $\text{[math]}$ such that $\text{[math]}$ . by lem-sssp-1, and by the definition of breakpoints, this implies that

for all $\text{[math]}$ , $\text{[math]}$ , and
for all $\text{[math]}$ , $\text{[math]}$ .

hence, the lower envelope of the first $\text{[math]}$ rows of $\text{[math]}$ consists of a suffix of the breakpoints of $\text{[math]}$ starting at $\text{[math]}$ plus, perhaps, a new breakpoint $\text{[math]}$ for some $\text{[math]}$ . the exact column $\text{[math]}$ where the new breakpoint occurs can be found by binary search for the largest column $\text{[math]}$ such that $\text{[math]}$ .
we summarize the procedure in the following theorem.

there exists a procedure that computes the breakpoints of the lower envelope of a $\text{[math]}$ -by- $\text{[math]}$ convex Monge matrix in $\text{[math]}$ time.
[cite:;taken from @graph_klein_2024 theorem 8.1.3]

[cite:;taken from @graph_klein_2024 chapter 8.1.2 finding all column minima of a monge matrix]