Monge Array

In mathematics, Monge arrays or Monge matrices are objects named after the discoverer, the French mathematician Gaspard Monge .

Content

Definition

They say that the m- on- n matrix is a Monge array , if for all $\scriptstyle i,\,j,\,k,\,\ell$ ${\ displaystyle \ scriptstyle i, \, j, \, k, \, \ ell}$ such that

1\leq i<k\leq m

{\ displaystyle 1 \ leq i <k \ leq m}

and

1\leq j<\ell \leq n

{\ displaystyle 1 \ leq j <\ ell \ leq n}

takes place ^[1] ^[2]

A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].

{\ displaystyle A [i, j] + A [k, \ ell] \ leq A [i, \ ell] + A [k, j].}

Thus, for any two rows and any two columns of the Monge array (2 × 2 submatrices), four elements at the intersection points have the property that the sum of the upper left and lower right elements (along the main diagonal ) is less than or equal to the sum of the lower left and upper elements ( anti-diagonal ).

This matrix is a Monge array:

{\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}}

{\ displaystyle {\ 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}}

For example, take the intersection of rows 2 and 4 with columns 1 and 5. Four elements at the intersections form a matrix:

{\begin{bmatrix}17&23\\11&7\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 17 & 23 \\ 11 & 7 \ end {bmatrix}}}

17 + 7 = 24

23 + 11 = 34

The sum of the elements along the main diagonal is less than the sum of the elements along the anti-diagonal.

Properties

The above definition is equivalent to the statement

A matrix is a Monge array if and only if

A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]

{\ displaystyle A [i, j] + A [i + 1, j + 1] \ leq A [i, j + 1] + A [i + 1, j]}

for all

1\leq i<m

{\ displaystyle 1 \ leq i <m}

and

1\leq j<n

{\ displaystyle 1 \ leq j <n}

.

Any subarray obtained by selecting specific rows and columns from the initial Monge array will again be a Monge array.

Any linear combination with non-negative coefficients of Monge arrays will be a Monge array.

There is one interesting property of Monge arrays. If you circle the minimum element of each row (if several are the same, select the leftmost one), you will see that the circles move down and to the right. That is, if $f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]$ ${\ displaystyle f (x) = \ arg \ min _ {i \ in \ {1, \ ldots, m \}} A [x, i]}$ then $f(j)\leq f(j+1)$ ${\ displaystyle f (j) \ leq f (j + 1)}$ for all $1\leq j<n$ ${\ displaystyle 1 \ leq j <n}$ . Symmetrically, if you select (the first from the top) at least in each column, the circles will move to the right and down. When choosing the maximum values, the circles move in opposite directions - up to the right and down to the left.
Any Monge array is completely monotone, which means that the minimum row elements go in non-decreasing column order, and the same property is true for any subarray. This property allows you to quickly find lows in rows using .

Related Definitions

The concept of a weak Monge array was proposed - it is a square n- on- n matrix that satisfies the Monge property $A[i,i]+A[r,s]\leq A[i,s]+A[r,i]$ ${\ displaystyle A [i, i] + A [r, s] \ leq A [i, s] + A [r, i]}$ only for everyone $1\leq i<r,s\leq n$ ${\ displaystyle 1 \ leq i <r, s \ leq n}$ .
The Monge matrix is just another name for a submodular function of two discrete variables. A is a Monge matrix if and only if A [ i , j ] is a submodular function of the variables i , j .
An n-on-n matrix A is called a Monge antimatrix if it satisfies the inequality $A[i,j]+A[r,s]\geq A[i,s]+A[r,j]$ ${\ displaystyle A [i, j] + A [r, s] \ geq A [i, s] + A [r, j]}$ for all $1\leq i<r\leq n$ ${\ displaystyle 1 \ leq i <r \ leq n}$ and $1\leq j<s\leq n$ ${\ displaystyle 1 \ leq j <s \ leq n}$

(this inequality is called Monge anti-inequality) ^[3] .

Applications

The square Monge matrix, which is also symmetrical with respect to the main diagonal , is called named (by the name of Fred Sapnik) ^[4] . Such matrices are used to solve the traveling salesman problem (namely, this problem can be easily solved if the distance matrix can be represented as the Sapnik matrix). Note that any linear combination of Sapnik matrices is again a Sapnik matrix.

Literature

↑ Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspectives of Monge properties in optimization. - ELSEVIER, 1996 .-- T. 70 , no. 2 . - S. 95–96 .
↑ Thomas Carmen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algorithms, construction and analysis. - Moscow, St. Petersburg, Kiev: Williams Publishing House, 2005. - P. 137. - ISBN 5-8459-0857-4 .
↑ Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases // Mathematical Programming. - June 1998. - T. 82 , no. 1 . - S. 125-158 .
↑ Fred Supnick. Extreme Hamiltonian Lines // Annals of Mathematics. Second Series. - July 1957. - T. 66 , no. 1 . - S. 179–201 .

Vladimir G. Deineko, Gerhard J. Woeginger. Some problems around traveling salesmen, dart boards, and euro-coins // Bulletin of the European Association for Theoretical Computer Science. - EATCS , October 2006 .-- T. 90 . - S. 43–52 . - ISSN 0252-9742 .

[1] Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspectives of Monge properties in optimization. - ELSEVIER, 1996 .-- T. 70 , no. 2 . - S. 95–96 .

[2] Thomas Carmen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algorithms, construction and analysis. - Moscow, St. Petersburg, Kiev: Williams Publishing House, 2005. - P. 137. - ISBN 5-8459-0857-4 .

[3] Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases // Mathematical Programming. - June 1998. - T. 82 , no. 1 . - S. 125-158 .

[4] Fred Supnick. Extreme Hamiltonian Lines // Annals of Mathematics. Second Series. - July 1957. - T. 66 , no. 1 . - S. 179–201 .