Массив Монжа

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

Определение

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

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

имеет место

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

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

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

$\left[\begin{array}{ccccc}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{array}\right]$

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

$\left[\begin{array}{cc}17& 23\\ 11& 7\end{array}\right]$

17 + 7 = 24

23 + 11 = 34

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

Свойства

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

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

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

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

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

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

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

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

Приложения

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

Литература

Шаблон:Примечания5.E Girlich,MKovalev,AZaporozhets Subcones of submodular functions ( subclasses of Monge matrices)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p

• Шаблон:Статья

Шаблон:Rq