В математике массивы Монжа или матрицы Монжа — это объекты, названные по имени открывателя, французского математика Гаспара Монжа .

Определение

Говорят, что m -на- n матрица является массивом Монжа , если для всех ${\displaystyle \scriptstyle i,\,j,\,k,\,\ell }$ , таких, что

${\displaystyle 1\leq i<k\leq m}$ и ${\displaystyle 1\leq j<\ell \leq n}$

имеет место

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

Таким образом, для любых двух строк и любых двух столбцов массива Монжа (2 × 2 подматрицы) четыре элемента на точках пересечения имеют свойство, что сумма верхнего левого и нижнего правого элементов (по главной диагонали ) меньше или равна сумме нижнего левого и верхнего элементов (по антидиагонали ).

Эта матрица является массивом Монжа:

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

Например, возьмём пересечение строк 2 и 4 со столбцами 1 и 5. Четыре элемента на пересечениях образуют матрицу:

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

17 + 7 = 24

23 + 11 = 34

Сумма элементов по главной диагонали меньше суммы элементов по антидиагонали.

Свойства

• Вышеприведённое определение эквивалентно утверждению

Матрица является массивом Монжа тогда и только тогда, когда ${\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}$ для всех ${\displaystyle 1\leq i<m}$ и ${\displaystyle 1\leq j<n}$ .

• Любой подмассив, полученный отбором определённых строк и столбцов из начального массива Монжа, снова будет массивом Монжа.

• Любая линейная комбинация с неотрицательными коэффициентами массивов Монжа будет массивом Монжа.

• Есть одно интересное свойство массивов Монжа. Если обвести кружками минимальный элемент каждой строки (если несколько одинаковых, выбираем самый левый), вы увидите, что кружки перемещаются вниз и направо. То есть, если ${\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}$ , то ${\displaystyle f(j)\leq f(j+1)}$ для всех ${\displaystyle 1\leq j<n}$ . Симметрично, если выбрать (первый сверху) минимум в каждом столбце, кружки будут перемещаться направо и вниз. При выборе максимальных значений кружки перемещаются в противоположных направлениях — вверх направо и вниз налево.
• Любой массив Монжа полностью монотонен, что означает, что минимальные элементы строк идут в неубывающем порядке столбцов, и то же самое свойство верно для любого подмассива. Это свойство позволяет найти быстро минимумы в строках с помощью .

Связанные определения

• Было предложено понятие слабого массива Монжа — это квадратная n -на- n матрица, которая удовлетворяет свойству Монжа ${\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}$ только для всех ${\displaystyle 1\leq i<r,s\leq n}$ .
• Матрица Монжа — это просто другое название для субмодулярной функции от двух дискретных переменных. A является матрицей Монжа тогда и только тогда, когда A [ i , j ] является субмодулярной функцией от переменных i , j .
• n-на-n матрица A называется антиматрицей Монжа, если она удовлетворяет неравенству ${\displaystyle A[i,j]+A[r,s]\geq A[i,s]+A[r,j]}$ для всех ${\displaystyle 1\leq i<r\leq n}$ и ${\displaystyle 1\leq j<s\leq n}$

(это неравенство называется антинеравенством Монжа) .

Приложения

• Квадратная матрица Монжа, которая также симметрична относительно главной диагонали , называется матрицей Сапника (по имени Фреда Сапника) . Такие матрицы применяются для решения задачи коммивояжёра (а именно — эта задача легко решается, если матрицу расстояний можно представить как матрицу Сапника). Заметим, что любая линейная комбинация матриц Сапника снова является матрицей Сапника.

Литература

5.E Girlich,MKovalev,AZaporozhets Subcones of submodular functions ( subclasses of Monge matrices)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p

• Vladimir G. Deineko, Gerhard J. Woeginger. Some problems around travelling salesmen, dart boards, and euro-coins // Bulletin of the European Association for Theoretical Computer Science. — EATCS , October 2006. — Т. 90 . — С. 43–52 . — ISSN .