Editing Monge array (section)

{{Short description|Type of mathematical object}}
{{refimprove|date=September 2012}}
In mathematics applied to [[computer science]], '''Monge arrays''', or '''Monge matrices''', are mathematical objects named for their discoverer, the French mathematician [[Gaspard Monge]].

An ''m''-by-''n'' [[matrix (mathematics)|matrix]] is said to be a ''Monge array'' if, for all <math>\scriptstyle i,\, j,\, k,\, \ell</math> such that

:<math>1\le i < k\le m\text{ and }1\le j < \ell\le n</math>

one obtains<ref name="Burkard1996">{{cite journal
| journal= Discrete Applied Mathematics
| first1 = Rainer E. | last1 = Burkard
| first2 = Bettina | last2 = Klinz
| first3 = Rüdiger | last3 = Rudolf
| title = Perspectives of Monge properties in optimization
| publisher = ELSEVIER 
| volume = 70 
| year = 1996
| issue = 2 
| pages = 95–96
 | doi=10.1016/0166-218x(95)00103-x
| doi-access = }}</ref>

:<math>A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j].\,</math>

So for any two rows and two columns of a Monge array (a 2&nbsp;&times;&nbsp;2 sub-matrix) the four elements at the intersection points have the property that the sum of the upper-left and lower right elements (across the [[main diagonal]]) is less than or equal to the sum of the lower-left and upper-right elements (across the [[antidiagonal]]).

This matrix is a Monge array:
:<math>
\begin{bmatrix}
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{bmatrix}</math>

For example, take the intersection of rows 2 and 4 with columns 1 and 5.
The four elements are:
:<math>
\begin{bmatrix}
17 & 23\\
11 & 7 \end{bmatrix}</math>

: 17 + 7 = 24
: 23 + 11 = 34

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.