Алгебра матричного умножения · 4.1

Магические, чарующие и полумагические квадраты

Обычное матричное произведение выводит нас из трёхмерного пространства магических квадратов в пятимерную алгебру полумагических матриц. На этой странице получены явные законы умножения, полная классификация и точные разложения.

1. Произведение двух магических квадратов

Используем доказанную ранее общую форму магического квадрата:

M(E,x,y)= \begin{pmatrix} E+x&E-x+y&E-y\\ E-x-y&E&E+x+y\\ E+y&E+x-y&E-x \end{pmatrix}.

Положим s₀=M(1,0,0), s₁=M(0,1,0), s₂=M(0,0,1). Тогда M(E,x,y)=Es₀+xs₁+ys₂. Прямое перемножение трёх базисных матриц показывает, что произведение двух магических квадратов обычно уже не удовлетворяет диагональным условиям, но сохраняет равенство всех сумм строк и столбцов.

s_1

\begin{pmatrix} 1&-1&0\\-1&0&1\\0&1&-1 \end{pmatrix}

s_2

\begin{pmatrix} 0&1&-1\\-1&0&1\\1&-1&0 \end{pmatrix}

s_1^2

\begin{pmatrix} 2&-1&-1\\-1&2&-1\\-1&-1&2 \end{pmatrix}

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

2. Стандартная теория и наша терминология

Матрица называется полумагической, если суммы всех её строк и всех её столбцов совпадают. Для матрицы 3×3 будем записывать эту общую сумму как 3E. Обозначим через P матрицу центрального отражения, а через 𝟙 — матрицу из единиц:

P= \begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}, \qquad \mathbf 1= \begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}.

В стандартной терминологии полумагическая матрица A веса E называется associated, если A+PAP=2E𝟙, и balanced, или центросимметрической, если PAP=A.

Теорема о соответствии

Над полем характеристики, отличной от 2 и 3, associated-полумагические матрицы 3×3 — это в точности магические квадраты M(E,x,y). Balanced-полумагические матрицы 3×3 — это в точности матрицы C(E,z,w), которые в проекте называются чарующими квадратами.

Доказательство для associated-компоненты

Для M(E,x,y) противоположные относительно центра клетки имеют сумму 2E, поэтому M+PMP=2E𝟙. Обратно, associated-условие даёт центральную клетку E и сумму 2E для каждой противоположной пары. Обе главные диагонали поэтому имеют сумму 3E; вместе с полумагическими условиями матрица является магической.

Доказательство для balanced-компоненты

Центросимметрическая матрица с одинаковыми суммами строк и столбцов сначала имеет вид слева. Сравнение первой строки с первым столбцом вынуждает d=b, а равенство сумм даёт e=a+c−b:

\begin{pmatrix}a&b&c\\d&e&d\\c&b&a\end{pmatrix} = \begin{pmatrix}a&b&c\\b&a+c-b&b\\c&b&a\end{pmatrix}.

Положив E=(a+b+c)/3, z=(a−b)/3 и w=(c−b)/3, получаем единственную форму

C(E,z,w)= \begin{pmatrix} E+2z-w&E-z-w&E-z+2w\\ E-z-w&E+2z+2w&E-z-w\\ E-z+2w&E-z-w&E+2z-w \end{pmatrix}.

Историческое положение

Название «чарующий квадрат» возникло внутри проекта при независимом выводе этой трёхмерной компоненты. В общей литературе используется название balanced semimagic matrix. Алгебра полумагических матриц изучалась по меньшей мере с работ Вайнера и Мурасе 1950-х годов; разложение на associated и balanced-компоненты и его блочная форма развиты в последующих работах.

3. Четыре закона умножения

Раскрытие произведений по базису даёт четыре точные формулы. Они верны как полиномиальные тождества и не требуют деления:

\begin{aligned} M(E_1,x_1,y_1)M(E_2,x_2,y_2) &=C(3E_1E_2,\ x_1x_2-y_1y_2,\ y_1x_2-x_1y_2),\\ M(E_1,x_1,y_1)C(E_2,x_2,y_2) &=3M(E_1E_2,\ x_1x_2-y_1y_2,\ y_1x_2-x_1y_2),\\ C(E_1,x_1,y_1)M(E_2,x_2,y_2) &=3M(E_1E_2,\ x_1x_2+y_1y_2,\ y_1x_2+x_1y_2),\\ C(E_1,x_1,y_1)C(E_2,x_2,y_2) &=3C(E_1E_2,\ x_1x_2+y_1y_2,\ y_1x_2+x_1y_2). \end{aligned}

Следовательно, MM попадает в C, произведения MC и CM — в M, а CC — в C. Порядок множителей существенен: вторые координаты в формулах MC и CM различаются. В частности, всякое произведение нечётного числа магических квадратов снова магическое, а произведение чётного числа — чарующее.

Последнее утверждение доказывается индукцией по числу множителей с использованием четырёх включений, а не проверкой отдельных произведений.

4. Полная форма полумагического квадрата

Сложение магической и чарующей компонент с единственным общим параметром E приводит к пяти координатам:

S(E,x,y,z,w)=M(E,x,y)+C(0,z,w) = \begin{pmatrix} E+x+2z-w&E-x+y-z-w&E-y-z+2w\\ E-x-y-z-w&E+2z+2w&E+x+y-z-w\\ E+y-z+2w&E+x-y-z-w&E-x+2z-w \end{pmatrix}.

Теорема классификации

Над полем характеристики, отличной от 2 и 3, отображение (E,x,y,z,w)↦S(E,x,y,z,w) является биекцией между K⁵ и множеством полумагических матриц 3×3.

Прямое направление

У M(E,x,y) все строки и столбцы имеют сумму 3E, а у C(0,z,w) — сумму 0. Поэтому каждая строка и каждый столбец S(E,x,y,z,w) имеют сумму 3E.

Обратное направление и единственность

Пусть A полумагическая и её общая сумма равна T. Если обозначить её левый верхний блок через a,b,d,e, то уравнения для первых двух строк и столбцов последовательно вынуждают все остальные клетки:

A= \begin{pmatrix} a&b&T-a-b\\ d&e&T-d-e\\ T-a-d&T-b-e&a+b+d+e-T \end{pmatrix}.

Последняя строка и последний столбец автоматически имеют сумму T. Тем самым пять величин T,a,b,d,e задают все полумагические матрицы и задают их однозначно. При наличии деления на 2 и 3 те же пять степеней свободы переводятся в наши координаты:

\begin{gathered} E=\frac{T}{3},\qquad x=\frac{a_{11}-a_{33}}2,\qquad y=\frac{a_{31}-a_{13}}2,\\ u=\frac{a_{11}+a_{33}}2-E,\qquad v=\frac{a_{13}+a_{31}}2-E,\\ z=\frac{2u+v}{3},\qquad w=\frac{u+2v}{3}. \end{gathered}

Подстановка принудительной формы A в эти выражения и затем в S возвращает каждую из девяти клеток A. Формулы восстановления одновременно доказывают существование и единственность координат E,x,y,z,w.

5. Единственное чётно-нечётное разложение

Полная форма уже содержит каноническое разложение

S(E,x,y,z,w)=C(E,z,w)+M(0,x,y).

Чарующая часть содержит общий центр и играет роль чётной компоненты; магическая часть имеет нулевой центр и играет роль нечётной. Их пересечение нулевое: если C(E,z,w)=M(0,x,y), то сравнение общих сумм даёт E=0, а единственность пяти координат даёт x=y=z=w=0.

По четырём законам произведение однородных компонент имеет степень, равную сумме степеней по модулю 2. Тем самым пятимерная алгебра полумагических матриц получает ℤ/2ℤ-градуировку.

6. Порождение магическими квадратами

Точная формула

S(E,x,y,z,w) =M(E,x,y)+M(0,1,0)M(0,z,-w).

Первый закон умножения даёт M(0,1,0)M(0,z,−w)=C(0,z,w), поэтому правая часть в точности равна определению S. Следовательно, всякий рациональный полумагический квадрат 3×3 является суммой магического квадрата и произведения двух магических квадратов.

Здесь не утверждается, что все три слагаемых единственны. Единственным является разложение на чарующую часть C(E,z,w) и магическую часть с нулевым центром M(0,x,y).

7. Почему S=M₁(I+M₂) не универсально

Единичная матрица принадлежит чарующей компоненте:

I_3=C\!\left(\frac13,\frac13,0\right).

Если представить S(E,x,y,z,w) в виде M(a,x,y)(I₃+M(b,u,v)), то сравнение магической и чарующей частей даёт

E=a(1+3b),\qquad \begin{pmatrix}z\\w\end{pmatrix} = \begin{pmatrix}x&-y\\y&-x\end{pmatrix} \begin{pmatrix}u\\v\end{pmatrix}.

Над ℚ первое уравнение разрешимо при любом E, например при a=1. Поэтому единственное препятствие находится во второй системе. Её определитель равен y²−x².

Если x²≠y², матрица системы обратима и допускает любые z,w. Если x=y≠0, обе координаты результата равны x(u−v); если x=−y≠0, они равны x(u+v) и −x(u+v). Каждое из полученных условий достаточно: требуемое значение достигается выбором одного из u,v равным нулю. При x=y=0 образ системы состоит только из нулевой пары. Поэтому получаем точную классификацию:

Магическая часть	Точно покрываемая чарующая часть
$x^2\ne y^2$	Любые z,w
$x=y\ne0$	$z=w$
$x=-y\ne0$	$z=-w$
$x=y=0$	$z=w=0$

Например, S(0,1,1,1,0) не допускает такого представления: равенство x=y вынуждало бы z=w, тогда как здесь z=1 и w=0. Это точный контрпример к универсальности, а таблица описывает максимальную область применимости формулы.

8. Граница этой статьи

На этой странице доказаны классификация и законы умножения над полями, где 2 и 3 обратимы, а сами произведения записаны как целочисленные полиномиальные тождества. Над ℤ полная полумагическая матрица может иметь общую сумму, не делящуюся на 3, поэтому координаты S(E,x,y,z,w) описывают не всю целочисленную решётку. Этот вопрос требует отдельной статьи.

Следующая статья строит изоморфизм с K⊕M₂(K), выделяет четырёхмерный идеал нулевой суммы и записывает в нём явный базис расщеплённых кватернионов 1,i,j,k.

Блочная структура и кватернионы →Общая форма M(E,x,y)