Editing Monge array (section)

==Properties==
*The above definition is equivalent to the statement
:A matrix is a Monge array [[if and only if]] <math>A[i,j] + A[i+1,j+1]\le A[i,j+1] + A[i+1,j]</math> for all <math>1\le i < m</math> and <math>1\le j < n</math>.<ref name="Burkard1996"/>

*Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array.
*Any [[linear combination]] with non-negative coefficients of Monge arrays is itself a Monge array.
*Every Monge array is totally monotone, meaning that its row minima occur in a nondecreasing sequence of columns, and that the same property is true for every subarray. This property allows the row minima to be found quickly by using the [[SMAWK algorithm]]. If you mark with a circle the leftmost minimum of each row, you will discover that your circles march downward to the right; that is to say, if <math>f(x) = \arg\min_{i\in \{1,\ldots,m\}} A[x,i]</math>, then <math>f(j)\le f(j+1)</math> for all <math>1\le j < n</math>. Symmetrically, if you mark the uppermost minimum of each column, your circles will march rightwards and downwards. The row and column ''maxima'' march in the opposite direction: upwards to the right and downwards to the left.
*The notion of ''weak Monge arrays'' has been proposed; a weak Monge array is a square ''n''-by-''n'' matrix which satisfies the Monge property <math>A[i,i] + A[r,s]\le A[i,s] + A[r,i]</math> only for all <math>1\le i < r,s\le n</math>.
*Monge matrix is just another name for [[supermodular function|submodular function]] of two discrete variables. Precisely, ''A'' is a Monge matrix if and only if ''A''[''i'',''j''] is a submodular function of variables&nbsp;''i'',''j''.