Гипотеза с матрицами

[Michail Terekhin]

Здравствуйте! Помогите, пожалуйста, доказать или опровергнуть следующую гипотезу.
Формулировка гипотезы:
Пусть $M \in \{-1, 0, 1\}^{n \times n}$. Рассматривается целевая функция а точнее её максимум:

$$\max_{M \in \{-1,0,1\}^{n \times n}} \left\vert{} \prod_{i=1}^{n} \left( \sum_{j=1}^{n} M_{i,j} \right) - \prod_{j=1}^{n} \left( \sum_{i=1}^{n} M_{i,j} \right) \right\vert{} = n^n + (n - 2)^n$$

То есть максимум модуля разности произведения сумм строк и произведения сумм столбцов для матриц размера $n \times n$ с элементами из $\{-1, 0, 1\}$ равен $n^n + (n - 2)^n$.
Замечание: Значение $n^n + (n - 2)^n$ достигается, например, на матрице, у которой первая строка полностью состоит из $-1$, а все остальные строки — полностью из $1$.
Довольно очевидно, что если знаки произведений сумм строк $R = \prod_{i=1}^{n} r_i$ и сумм столбцов $C = \prod_{j=1}^{n} c_j$ совпадают, то максимум не достигается.
Продвижения в доказательстве:
Если для некоторой матрицы прибавить $1$ к элементу $M_{i,j}$, то целевая функция меняется на $\left( \frac{\vert{}R\vert{}}{r_i} + \frac{\vert{}C\vert{}}{c_j} \right)$, а если вычесть $1$, то на $-\left( \frac{\vert{}R\vert{}}{r_i} + \frac{\vert{}C\vert{}}{c_j} \right)$.
Поскольку для максимальной матрицы изменение функции должно быть $\le 0$, записываем условие локального максимума $y \cdot \left( \frac{\vert{}R\vert{}}{r_i} + \frac{\vert{}C\vert{}}{c_j} \right) \le 0$.
Из этого вытекает: На пересечении строки и столбца с положительными суммами всегда стоит $1$. На пересечении строки и столбца с отрицательными суммами всегда стоит $-1$. Если какой-то элемент равен $0$ у максимальной матрицы, то при его изменении целевая функция не меняется.
Подставляя $y = 1$ а затем $y = -1$, проводим некоторые переносы и объединяем неравенства:

$$1 - M_{i,j} \cdot \left( \frac{\vert{}R\vert{}}{r_i} + \frac{\vert{}C\vert{}}{c_j} \right) \ge 0$$

Предположение об отсутствии нулей:
Если предположить, что в максимальной матрице не может быть нулей, получаем:

$$\frac{\vert{}R\vert{}}{r_i} + \frac{\vert{}C\vert{}}{c_j} \le \frac{1}{M_{i,j}}$$

Складывая по всем $j$, получаем уравнение, не зависящее от $i$. Анализ(в основном графический) показывает, что оно имеет не более двух решений, откуда следует, что строки и столбцы бывают всего двух видов.
Упорядочив строки и столбцы (сначала с положительными суммами, затем с отрицательными), мы получаем разбиение матрицы на 4 блока («бассейна»):Верхний левый полностью заполнен $1$;Нижний правый полностью заполнен $-1$;Остальные два блока однородны и не содержат нулей(Последнее утверждение можно доказать используя условие о двух видах столбцов и строк и суммы строк). Анализ целевой функции для всех вариантов заполнения этих блоков подтверждает гипотезу.
Вопрос: Главное узкое место — предположение об отсутствии нулей в максимальной матрице.
Как строго доказать, что максимальная матрица не может содержать $0$? Или как обобщить доказательство на случай наличия нулей? Если гипотеза неверна в общем случае — буду благодарен за контрпример.

[Null]

Michail Terekhin в сообщении #1736451 писал(а):

Как строго доказать, что максимальная матрица не может содержать $0$?

Это так. Функция линейна по каждой отдельной переменной(можете погуглить про "максимум полилинейной функции"), а значит её максимум достигается на границе(Если коэффициент при $M_{ij}\ge 0$ то $M_{ij}=1$, иначе $M_{ij}=-1$).

[Michail Terekhin]

Благодарю

[Michail Terekhin]

Я заметил ошибку в ваших рассуждениях.
Ноль не может быть максимум только если

$$ \frac{|R|}{r_i} + \frac{|C|}{c_j} \neq 0 $$

.
В противном случае пока ничто не запрещает нули в оптимальной матрице и следовательно гипотеза не доказана. так что вопрос открыт.

[Null]

Michail Terekhin в сообщении #1736582 писал(а):

В противном случае пока ничто не запрещает нули в оптимальной матрице и следовательно гипотеза не доказана. так что вопрос открыт.

Да, в одной из максимальных матриц может быть 0, но есть матрица с таким же значением функции, но состоящая из $\pm 1$.