Массив Монжа

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

Определение

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

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

имеет место

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

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

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

${\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. Четыре элемента на пересечениях образуют матрицу:

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

17 + 7 = 24

23 + 11 = 34

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

Свойства

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

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

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

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

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

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

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