Массив Монжа

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

Определение

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

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

имеет место^[1][2]

${\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}$. Симметрично, если выбрать (первый сверху) минимум в каждом столбце, кружки будут перемещаться направо и вниз. При выборе максимальных значений кружки перемещаются в противоположных направлениях — вверх направо и вниз налево.
• Любой массив Монжа полностью монотонен, что означает, что минимальные элементы строк идут в неубывающем порядке столбцов, и то же самое свойство верно для любого подмассива. Это свойство позволяет найти быстро минимумы в строках с помощью алгоритма SMAWK^[англ.].

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

• Было предложено понятие слабого массива Монжа — это квадратная 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}$

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

Приложения

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

Литература

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.

Эта страница в последний раз была отредактирована 24 марта 2021 в 08:16.