  The symmetric group $\mathfrak{S}_n$ (and more generally, any Coxeter group)
admits an associative operation known as the Demazure product. In this paper,
we first extend the Demazure product to the (infinite) set of all biwords on
$\{1, \ldots, n\}$, or equivalently, the set of all $n \times n$ nonnegative
integer matrices. We define this product diagrammatically, via braid-like
graphs we call kelp beds, since they significantly generalize the seaweeds
introduced by Tiskin (2015). Our motivation for this extended Demazure product
arises from optimization theory, in particular the semigroup of all $(n+1)
\times (n+1)$ simple nonnegative integer Monge matrices equipped with the
distance (i.e., min-plus) product. As our main result, we show that this
semigroup of Monge matrices is isomorphic to the semigroup of biwords equipped
with the extended Demazure product. We exploit this isomorphism to write down
generating functions for the growth series of the Monge matrices with respect
to certain natural matrix norms.
