Кресты

[bot]

Пусть $\varphi:\{1, 2, \ldots ,mn\} \to \{1, 2, \ldots , m\}\times \{1, 2, \ldots, n\} $ - биекция.
Множество $K_{ij}=\{(i, k) \mid k=1, \ldots ,n\}\cup \{(k, j) \mid k=1, \ldots ,m\}$ назовём крестом с узлом $(i,j).$
;Каждому кресту сопоставим строку $(a_1, a_2, \ldots ,a_{mn})$, состоящую из нулей и единиц, по правилу $a_s=1$ тогда и только тогда, когда $\varphi(s)$ принадлежит кресту. Доказать невырожденность матрицы, составленной из всех таких строк.

[worm2]

Уточняю, что $m>1$ и $n>1$ (иначе утверждение неверно ).

Переформулировка.
В таблице из $n$ строк и $m$ столбцов записаны числа.
Оказалось, что для каждой клетки сумма чисел в столбце этой клетки плюс сумма чисел в строке этой клетки равна числу в этой клетке.
Доказать, что в каждой клетке записан 0.
(это приводит к системе линейных уравнений с матрицей, невырожденность которой нам нужно доказать по условию, с точностью до перестановки строк и столбцов).

Доказательство.
Пусть $S$ — сумма чисел во всей таблице, $S_i$ — сумма чисел в $i$-й строке, $i=1,2, \dots, n$, $S^j$ — сумма чисел в $j$-м столбце, $j=1,2, \dots, m$.
Посчитаем $S_i$ как сумму чисел в клетках этой строки. По условию получается: $mS_i+S=S_i$, откуда $S_i=\dfrac{S}{1-m}$. Посчитав сумму $S_i$ по всем строкам, которая, разумеется, должна быть равна $S$, имеем: $S=\dfrac{n}{1-m}S$, откуда $S=0$, а значит и $S_i=0$.
Аналогично, $S^j=0$. Ещё раз вспоминая условие, заключаем, что в ячейке $(i, j)$ записано число $S_i+S^j=0$.

[bot]

worm2

(Оффтоп)

Лет 50 назад придумал задачу в формулировке, что суммы элементов в разных крестах одинаковы, а доказать, что все числа одинаковы. Сейчас вспомнил и переформулировал. а worm2 перепереформулировал.

worm2 в сообщении #1673442 писал(а):

Уточняю, что $m>1$ и $n>1$ .

Переуточняю: $mn>1$. В доказательсте можно ограничиться только суммами элементов в строках (или в столбцах) и свести задачу к простому случаю $m=1, n>1$ или $n=1, m>1$
Стоп, в случае строки крест - это строка с выколотым элементом.

[makxsiq]

В общем, похоже есть другое решение. Рассмотрим, например, случай $m=2$ и произвольное $n$. Тогда определитель матрицы размера $2n\times 2n$, для которой надо показать невырожденность, перестановкой столбцов можно привести к виду:

$$ \begin{center} \begin{vmatrix} 1 & 1 & 1 &\cdots & 1 & 1 & 0 & 0 & \cdots & 0\\ 1 & 1 & 1 &\cdots & 1 & 0 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 &\cdots & 1 & 0 & 0 & 1 & \cdots & 0\\ \vdots &\vdots &\vdots &\ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 &\cdots & 1 & 0 & 0 & 0 & \cdots &1 \\ 1 & 0 & 0 & \cdots & 0 & 1 & 1 & 1 &\cdots & 1 \\ 0 & 1 & 0 & \cdots & 0 & 1 & 1 & 1 &\cdots & 1 \\ 0 & 0 & 1 & \cdots & 0 & 1 & 1 & 1 &\cdots & 1 \\ \vdots &\vdots &\vdots &\ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots &1 & 1 & 1 & 1 &\cdots & 1 \end{vmatrix} \end{center} $$

Этот определитель, а следовательно и определитель исходной матрицы с точностью до знака, равен $(-1)^{n+1} \cdot (n^2-1)$.

(Оффтоп)

И предварительно для произвольных $m$ и $n$, определитель матрицы размера $mn \times mn$ по модулю равен

$$(m-1)^{n-1}(n-1)^{m-1}(n+m-1)$$