Размерность магических матриц

[Maxim19]

Здравствуйте, просят найти размерность магической матрицы. Это квадратные матрицы, сумма столбцов и строк которых равна следу, и равна сумме диагональных элементов вида (I,n-i). И просят посчитать для матриц 3 на 3 и 4 на 4. Тут идей вообще нет. Сижу, нахожу линейно независимые элементы. Для 3 на 3 нашёл 3 таких элемента. Но надо же ещё для 4 на 4 и при этом как доказывать, что больше нет. Думаю подход неверный. Что делать?

[svv]

Maxim19 в сообщении #1591690 писал(а):

просят найти размерность магической матрицы

Просят найти размерность векторного пространства магических матриц порядка $n$ (для $n=3$ и $n=4$).

Maxim19 в сообщении #1591690 писал(а):

Это квадратные матрицы, сумма столбцов и строк которых равна следу, и равна сумме диагональных элементов вида (I,n-i).

Магическая матрица — это квадратная матрица, у которой сумма чисел в каждой строке, в каждом столбце и на обеих диагоналях одинакова.

Неформальное рассуждение. У магической матрицы порядка $n$ имеется $n$ строк, $n$ столбцов и $2$ диагонали, то есть $2n+2$ сумм, которые должны совпадать. Это даёт $2n+1$ условий. Но поскольку сумма всех «строчных» сумм равна сумме всех «столбцовых» сумм, одно из условий избыточно (является следствием остальных). Всего получается $2n$ независимых условий. Тогда среди элементов матрицы можно выбрать $n^2-2n$ элементов так, что их значения можно задать независимо, после чего остальные элементы из условий однозначно определятся. (Но не любые $n^2-2n$ элементов матрицы можно задавать независимо.)

Maxim19 в сообщении #1591690 писал(а):

Для 3 на 3 нашёл 3 таких элемента.

Правильно.
В случае $n=4$ обозначим элементы так:
$\begin{bmatrix}{\color{magenta}a}&{\color{magenta}b}&{\color{magenta}c}&{\color{magenta}d}\\e&{\color{magenta}f}&{\color{magenta}g}&{\color{magenta}h}\\i&j&{\color{magenta}k}&l\\m&n&p&q\end{bmatrix}$
Восемь независимых элементов выделены цветом. Считаем их известными.

Пусть $a+b+c+d=S$. Тогда и $m+n+p+q=S$. Складывая равенства
$m=S-d-g-j$
$n=S-b-f-j$
$p=S-c-g-k$
$q=S-a-f-k$
получим $f+g+j+k=S$. Значит, $j=S-f-g-k$. Теперь и остальные элементы легко находятся.

Остаётся проверить, что все условия действительно удовлетворяются при произвольных значениях независимых элементов (ведь рассуждение выше было неформальным). Это легко, потому что бОльшая часть условий будет выполнена «по построению».

[Maxim19]

Я так и не понял, почему $2n$ условий как бы отнимают $2n$ векторов из базиса. Эти же условия не должны следовать из других условий и так далее

[Ende]

Maxim19
Даже отдельные обозначения нужно оформлять как формулы. Не "2n условий", а "$2n$ условий".

[Maxim19]

Можете подробнее объяснить саму идею. Если это условия, которые записываются в линейных система уравнений, то это же не однородные системы. Тем более непонятно про интуитивную ту независимость

[Geen]

svv в сообщении #1591778 писал(а):

Тогда среди элементов матрицы можно выбрать $n^2-2n$ элементов так, что их значения можно задать независимо

Хм, возьмём $n=2$

[Maxim19]

Это всё весело, но я вообще не понял связи ограничений и размерности. Было бы ещё понятно, если бы сами ограничения задавались линейной однородной системой, тогда можно было бы связать как нибудь с пространством решений

[svv]

Maxim19 в сообщении #1591850 писал(а):

Это всё весело, но я вообще не понял связи ограничений и размерности.

Maxim19, Вы меня расстраиваете.

$n=3,\quad A=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}$
Условия магичности:
$a_{11}+a_{12}+a_{13}=a_{21}+a_{22}+a_{23}=a_{31}+a_{32}+a_{33}=$ (строки)
$a_{11}+a_{21}+a_{31}=a_{12}+a_{22}+a_{32}=a_{13}+a_{23}+a_{33}=$ (столбцы)
$a_{11}+a_{22}+a_{33}=a_{13}+a_{22}+a_{31}$ (диагонали)

Равенство этих восьми ($2n+2$) сумм можно записать в виде семи ($2n+1$) однородных уравнений:
1) $a_{11}+a_{12}+a_{13}=a_{21}+a_{22}+a_{23}$
2) $a_{11}+a_{12}+a_{13}=a_{31}+a_{32}+a_{33}$
3) $a_{11}+a_{12}+a_{13}=a_{11}+a_{21}+a_{31}$
4) $a_{11}+a_{12}+a_{13}=a_{12}+a_{22}+a_{32}$
5) $a_{11}+a_{12}+a_{13}=a_{13}+a_{23}+a_{33}$
6) $a_{11}+a_{12}+a_{13}=a_{11}+a_{22}+a_{33}$
7) $a_{11}+a_{12}+a_{13}=a_{13}+a_{22}+a_{31}$
Эти условия не являются независимыми: условие 5) можно получить, если из суммы 1) и 2) вычесть сумму 3) и 4). Но остальные шесть условий ($2n$) уже независимы. Условия можно записать в матричной форме:
$\begin{bmatrix}-1&-1&-1&1&1&1&0&0&0 \\-1&-1&-1&0&0&0&1&1&1 \\\phantom{+}0&-1&-1&1&0&0&1&0&0 \\-1&\phantom{+}0&-1&0&1&0&0&1&0 \\-1&-1&\phantom{+}0&0&0&1&0&0&1 \\\phantom{+}0&-1&-1&0&1&0&0&0&1 \\-1&-1&\phantom{+}0&0&1&0&1&0&0\end{bmatrix} \begin{bmatrix}a_{11}\\a_{12}\\a_{13}\\a_{21}\\a_{22}\\a_{23}\\a_{31}\\a_{32}\\a_{33}\end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\\0\\0\\0\end{bmatrix}$

Матрица в левой части (назовём её $B$) имеет $M=7$ строк и $N=9$ столбцов. Она преобразует вектор из девятимерного пространства матриц $3\times 3$ в вектор из семимерного "пространства условий" (который равен нуль-вектору, когда все условия выполнены, иначе его компоненты показывают, какие условия не выполнены). Магическим матрицам соответствуют те векторы, которые принадлежат $\ker B$. В данном примере
$\begin{array}{l}\dim \operatorname{im} B=\operatorname{rank} B=6\\\dim \ker B=N-\dim\operatorname{im} B=3\end{array}$
в соответствии с rank-nullity theorem. Это и есть та связь.

[Maxim19]

Всё всё. Просто невнимательность. Действительно, однородные уравнения. Я зациклился на мысли, что там всё неоднородно и приравнивал это всё к какому-то $N$ чему все равны

-- 01.05.2023, 04:19 --

Вызывает вопрос только с определением ранга той большой матрицы. Какая там идея? Именно не про случай для $n=3$, а в общем случае

[Geen]

Maxim19 в сообщении #1591862 писал(а):

неоднородно и приравнивал это всё к какому-то $N$ чему все равны

Ну так, объявляете эту $N$ ещё одной переменной и учитываете, что количество связей тоже увеличилось на 1....

[svv]

Maxim19 в сообщении #1591862 писал(а):

Какая там идея? Именно не про случай для $n=3$, а в общем случае

Я не решал задачу в общем случае, и у меня нет идей. Я решал только для $n=3$ и $n=4$. Ещё раз объясню логику для $n=4$. Начнём с

svv в сообщении #1591778 писал(а):

Неформальное рассуждение. У магической матрицы порядка $n$ имеется $n$ строк, $n$ столбцов и $2$ диагонали, то есть $2n+2$ сумм, которые должны совпадать. Это даёт $2n+1$ условий. Но поскольку сумма всех «строчных» сумм равна сумме всех «столбцовых» сумм, одно из условий избыточно (является следствием остальных). Всего получается $2n$ независимых условий. Тогда среди элементов матрицы можно выбрать $n^2-2n$ элементов так, что их значения можно задать независимо, после чего остальные элементы из условий однозначно определятся. (Но не любые $n^2-2n$ элементов матрицы можно задавать независимо.)

В действительности, это рассуждение даёт правильное значение ранга матрицы ограничений (условий) при всех $n>2$. Почему оно названо неформальным? Единственный нестрогий момент здесь — то, что даже оставшиеся $2n$ условий могут оказаться зависимыми. Поэтому сначала я предполагаю, что при $n=4$ имеется $2n=8$ независимых условий и соответственно в матрице $A$ можно выбрать $n^2-2n=8$ независимых элементов.

svv в сообщении #1591778 писал(а):

В случае $n=4$ обозначим элементы так:
$\begin{bmatrix}{\color{magenta}a}&{\color{magenta}b}&{\color{magenta}c}&{\color{magenta}d}\\e&{\color{magenta}f}&{\color{magenta}g}&{\color{magenta}h}\\i&j&{\color{magenta}k}&l\\m&n&p&q\end{bmatrix}$
Восемь независимых элементов выделены цветом. Считаем их известными.

Выбирать независимые элементы как попало нельзя. Например, $8$ элементов верхних двух строк зависимы, потому что $a+b+c+d=e+f+g+h$. Менее очевидно, что $a+b+c+d=f+g+j+k$ (выше я писал, как это показать). Но выбор $(a,b,c,d,f,g,h,k)$ удачный. Зная эти элементы, можно найти остальные. Пусть
$S=a+b+c+d\quad(R1)$
Находим последовательно
$\begin{array}{ll}j=S-f-g-k& \\m=S-d-g-j&(D2) \\n=S-b-f-j&(C2) \\p=S-c-g-k&(C3) \\q=S-a-f-k&(D1) \\l=S-d-h-q&(C4) \\e=S-f-g-h&(R2) \\i=S-j-k-l&(R3) \end{array}$
Каждая аббревиатура в скобках означает условие, которое выполнено по построению, и потому его можно не проверять. $C$ означает column, $R$ — row, $D$ — diagonal. Например, $C3$ означает условие, что сумма элементов третьего столбца равна $S$.
Остаётся проверить только условия $C1$ и $R4$, причём достаточно проверить только одно из них, потому что в наборе $(R1,R2,R3,R4,C1,C2,C3,C4)$ любое условие следует из остальных. Я не буду здесь это делать.

Итак, для каждого набора значений переменных $(a,b,c,d,f,g,h,k)$ существует единственный набор значений $(e,i,j,l,m,n,p,q)$ такой, что все условия выполнены и матрица $A$ магическая. А это и означает, что пространство решений восьмимерно.

[Geen]

(Оффтоп)

svv в сообщении #1592020 писал(а):

Единственный нестрогий момент здесь — то, что даже оставшиеся $2n$ условий могут оказаться зависимыми.

:точно:
Вроде бы не должны, но я не придумал как это доказать...

[svv]

Придумал. Пусть $n\geqslant 4$.

Кружочки — элементы матрицы $A$ размера $n\times n$. Цветные — те, что находятся в первой строке, в первом столбце, и ещё $a_{22}$. Их всего $2n$. Остальные $n^2-2n$ белые.
$R_1...R_n$ — строки (rows), $C_1...C_n$ — столбцы (columns), $D_1$ — главная диагональ, $D_2$ — побочная диагональ.
$S$ — сумма элементов любой строки, столбца и диагоналей.

0) Значения элементов, обозначенных белыми кружками, зададим произвольно и дальше считаем известными.
Покажем, что тогда значения цветных элементов определяются однозначно.

1) Найдём $a_{1n}, a_{n1}$ (голубые) и $S$ из системы:
$\begin{cases}S-a_{1n}=\text{сумма белых элементов $n$-го столбца}\\S-a_{n1}=\text{сумма белых элементов $n$-й строки}\\S-a_{1n}-a_{n1}=\text{сумма белых элементов побочной диагонали}\end{cases}$
Это обеспечивает условия $C_n, R_n, D_2$.

2) Зная $S$, найдём все $a_{1k}$ и $a_{k1}$, где $k=3...n-1$ (красные).
Это обеспечивает условия $C_3...C_{n-1}$ и $R_3...R_{n-1}$.

3) Остаётся найти жёлтые элементы. Найдём $a_{11},a_{12},a_{22}$ из системы:
$\begin{cases}a_{11}+a_{12}=S-\text{сумма нежёлтых элементов $1$-й строки}\\a_{12}+a_{22}=S-\text{сумма нежёлтых элементов $2$-го столбца}\\a_{11}+a_{22}=S-\text{сумма нежёлтых элементов главной диагонали}\end{cases}$
Это обеспечивает условия $R_1, C_2, D_1$.

4) Находим $a_{21}=S-a_{22}-\text{сумма нежёлтых элементов $2$-й строки}$
Это обеспечивает условие $R_2$.

А условие $C_1$ будет выполнено автоматически.