Россия
УДК 519.1 Комбинаторный анализ. Теория графов
Перманент многомерных матриц выражен в терминах операций над элементами коммутативной алгебры с нильпотентными индекса 2 образующими. С помощью техники, основанной на данной взаимосвязи, доказано несколько свойств перманента. Изучены различные виды многомерных перестановок. Перманент многомерных матриц рассмотрен с точки зрения перечисляющей функции многомерных перестановок.
многомерная матрица, перманент, многомерная перестановка
Введение
Перманент матрицы A = (aij) n-го порядка опреде-
ляется следующим образом:
PerA =
Σ
σ∈Sn
Πn
i=1
aiσ(i)
(суммирование ведется по всем перестановкам n-го по-
рядка). Перманент нашел широкое применение в комбина-
торике, так как его можно рассматривать в качестве пере-
числяющей функции различных объектов дискретной ма-
тематики: совершенных паросочетаний двудольных гра-
фов, перестановок с ограниченными позициями и т. д. Об-
ширный материал, касающийся перманента можно найти
в ставшей уже классической монографии [1].
Понятие перманента можно обобщить и на случай мно-
гомерных матриц. Эта тематика стала разрабатываться
сравнительно недавно. Подробный обзор, посвященный
данной теме, можно найти в статье [2]. В нашей работе мы
затрагиваем некоторые дополнительные вопросы, связан-
ные с перманентом многомерных матриц, не отраженные,
насколько нам известно, в литературе.
Рассмотрим ассоциативную алгебру над полем F, по-
рожденную элементами ιk, связанными следующими опре-
деляющими соотношениями: ι2
k = 0, ιkιl = ιlιk, k, l =
1, 2, . . . , n. Хорошо известно [1, с. 110], что перманент мат-
рицы можно выразить через произведение однородных
элементов первой степени данной алгебры. Точнее, пусть
дана матрица A = (aij) n-го порядка c элементами из F.
Тогда, как нетрудно заметить,
PerAι1ι2 . . . ιn =
Πn
i=1
(ai1ι1 + ai2ι2 + · · · + ainιn).
В первом разделе мы распространяем данную конструк-
цию на многомерный случай. С помощью техники, осно-
ванной на данной взаимосвязи, мы доказываем некоторые
простейшие свойства перманента многомерных матриц.
Хорошо известно, что перманент можно использовать
для перечисления перестановок с ограниченными позици-
ями [3]. Во втором разделе мы рассматриваем многомерный
аналог данной взаимосвязи на примере многомерных бес-
порядков.
1. Перманент многомерных матриц и некото-
рые его свойства
d-Мерной матрицей A порядка n над полем F назы-
вается d-мерный массив элементов из F, каждый индекс
которого пробегает значения от 1 до n:
A = (ai1i2...id), ik ∈ {1, 2, . . . , n}, ai1i2...id
∈ F.
Множество элементов матрицы A c фиксированными зна-
чениями d − k индексов называется k-мерной гранью,
(d − 1)-мерную грань называют гипергранью [2]. Диаго-
налью матрицы A называется любой набор из n ее эле-
Известия Коми научного центра Уральского отделения Российской академии наук № 5 (71), 2024
Серия «Физико-математические науки»
www.izvestia.komisc.ru
11
ментов, отличающихся друг от друга в каждом индексе:
(a1σ2(1)...σd(1), . . . , anσ2(n)...σd(n)), σi ∈ Sn.
Обозначим через L(A) множество всех диагоналей мат-
рицы A. Перманент матрицы A определяется следующим
образом:
PerA =
Σ
l∈L(A)
Π
a∈l
a.
Очевидно, что еслиA— двумерная матрица, то мы получим
обычное определение перманента.
Пример. Рассмотрим трехмерную матрицу 2-го порядка:
A = (aijk), i, j, k = 1, 2. Графически ее можно изоб-
разить в виде 2 × 2 × 2 куба или двух обычных 2 × 2
матриц:
A =
{(
a111 a112
a121 a122
)
,
(
a211 a212
a221 a222
)}
.
Здесь первый индекс отвечает за номер матрицы, второй —
за номер строки в матрице, третий — за номер столбца.
Перманент данной матрицы имеет следующий вид:
PerA = a111a222 + a112a221 + a121a212 + a122a211.
Рассмотрим ассоциативную алгебру над полем F, по-
рожденную образующими ιjk, j, k = 1, 2, удовлетворяю-
щими следующим определяющим соотношениям:
ιjkιst =
{
0 , если j = s или k = t,
ιstιjk , в противном случае.
Данная алгебра, как нетрудно видеть, является шестимер-
ной. Каждый ее элемент однозначно разлагается по базис-
ным элементам ι11, ι12, ι21, ι22, ι11ι22, ι12ι21, составлен-
ным из образующих и их всевозможных ненулевых про-
изведений с точностью до порядка сомножителей. Назо-
вем такой базис основным. Пусть дана трехмерная матри-
ца 2-го порядка A = (aijk), i, j, k = 1, 2. Рассмотрим
следующие два элемента указанной выше алгебры:
ai = ai11ι11 + ai12ι12 + ai21ι21 + ai22ι22, i = 1, 2.
Коэффициенты элемента a1 соответствуют гиперграни
матрицы A, образованной элементами с первым индек-
сом, равным 1, а коэффициенты элемента a2 — гипергра-
ни, образованной элементами с первым индексом, равным
2. Рассмотрим произведение этих элементов:
a1a2 = (a111a222 + a122a211)ι11ι22+
+ (a112a221 + a121a212)ι12ι21.
Нетрудно видеть, что сумма коэффициентов элемента a1a2
в разложении по основному базису равна перманенту мат-
рицы A. Таким образом, если через sc(a) обозначить сум-
му коэффициентов элемента a в разложении по основному
базису, то sc(a1a2) = PerA.
Можно рассмотреть элементы алгебры, соответствую-
щие другим гиперграням, например, следующие:
bi = a1i1ι11 + a1i2ι12 + a2i1ι21 + a2i2ι22, i = 1, 2.
Их произведение
b1b2 = (a111a222 + a121a212)ι11ι22+
+ (a112a221 + a211a122)ι12ι21
в общем случае будет отличаться от a1a2, но сумма коэф-
фициентов произведения также будет равна перманенту
матрицы A: sc(b1b2) = PerA.
Пусть теперь в общем случае дана (d+1)-мерная мат-
рица n-го порядка A = (ai1i2...id+1) над полем F. Рас-
смотрим алгебру Pd,n(ι) над F с образующими ιj1j2...jd,
j1, j2, . . . , jd = 1, . . . , n, удовлетворяющими коммутаци-
онным соотношениям:
{
ιj1...jd
· ιj′
1...j′
d
= 0 , ∃s : js = j′
s,
ιj1...jd
· ιj′
1...j′
d
= ιj′
1...j′
d
· ιj1...jd , иначе.
(1)
Как и в трехмерном случае, ее основным базисом назовем
базис, составленный из образующих и их всевозможных
ненулевых произведений с точностью до порядка сомно-
жителей. Рассмотрим в этой алгебре следующие элементы:
ai =
Σ
i1,...,id
aii1...idιi1...id, i = 1, 2, . . . , n.
Тогда нетрудно видеть, что
sc(a1a2 . . . an) = Per A. (2)
Аналогично трехмерному случаю, в общем случае в каче-
стве сомножителей можно брать элементы алгебры, соот-
ветствующие и другим гиперграням матрицы.
Соотношение (2) позволяет, например, доказывать
свойства перманента многомерных матриц в терминах пре-
образования элементов алгебры Pd,n(ι). Прежде чем при-
вести пример, рассмотрим два простейших свойства функ-
циии sc.
1. Линейность. Если α, β ∈ F, a, b ∈ Pd,n(F), то
sc(αa + βb) = αsc(a) + βsc(b). (3)
2. Мультипликативность. Предположим, что элементы
a, b, ab ∈ Pd,n(ι), рассматриваемые как элементы век-
торного пространства, имеют m, n и mn ненулевых коор-
динат в основном базисе соответственно. Это возможно то-
гда и только тогда, когда произведение любого базисного
элемента, входящего в разложение a с ненулевым коэф-
фициентом, на любой базисный элемент, входящий в раз-
ложение b с ненулевым коэффициентом, не равно нулю.
Нетрудно видеть, что в этом случае
sc(ab) = sc(a)sc(b). (4)
Например, пусть a = 2ι11 + 3ι12, b = 3ι23 − 4ι33 — два
элемента алгебры P2,3(ι) над R. Тогда
ab = 6ι11ι23 + 9ι12ι23 − 8ι11ι33 − 12ι12ι33.
При этом sc(a) = 5, sc(b) = −1, sc(ab) = −5, и свой-
ство (4) выполняется.
В качестве примера использования соотношения (2)
докажем формально аналог свойства разложения перма-
нента по строке (столбцу) для многомерных матриц. Пусть
12
Известия Коми научного центра Уральского отделения Российской академии наук № 5 (71), 2024
Серия «Физико-математические науки»
www.izvestia.komisc.ru
дана d-мерная матрица A = (ai1i2...id) n-го порядка. То-
гда
PerA = sc
(
Πn
i1=1
Σn
i2,...,id=1
ai1i2...idιi2...id
)
=
= sc
(
Σn
i2,...,id=1
a1i2...idιi2...id
×
×
(
Πn
j1=2
Σn
j2,...,jd=1
aj1j2...jdιj2...jd
))
.
Принимая во внимание первое из определяющих соотно-
шений (1), а также свойства (3), (4), мы можем продолжить
преобразования следующим образом:
PerA = sc
(
Σn
i2,...,id=1
a1i2...idιi2...id
×
×
Πn
j1=2
Σ
jk
̸=ik
k=2,...,n
aj1j2...jdιj2...jd
=
=
Σn
i2,...,id=1
a1i2...idsc
Πn
j1=2
Σ
jk
̸=ik
k=2,...,n
aj1j2...jdιj2...jd
=
=
Σn
i2,...,id=1
a1i2...idPer (A{1, i2, . . . , id}) .
Здесь через A{1, i2, . . . , id} мы обозначили дополни-
тельную матрицу элемента a1i2...id, т. е. матрицу, получае-
мую из матрицы A вычеркиванием всех элементов, лежа-
щих с a1i2...id в одной гиперграни. Очевидно, что в дока-
зательстве можно проводить суммирование и относительно
элементов других гиперграней. Таким образом, перманент
многомерной матрицы равен сумме произведений элемен-
тов некоторой гиперграни на перманенты дополнительных
матриц этих элементов.
Прежде чем перейти к доказательству следующего
свойства, введем дополнительные обозначения. Обозна-
чим через Qk,n — множество всех k-элементных неупо-
рядоченных подмножеств множества {1, 2, . . . , n}. Пусть
A = (ai1i2...id) — d-мерная матрица n-го порядка и α1,
α2,. . . ,αd ∈ Qk,n. Через A[αl=1,...,d] обозначим d-мер-
ную матрицу k-го порядка, которая состоит из элементов
ai1i2...id матрицы A таких, что i1 ∈ α1, i2 ∈ α2, . . . , id ∈
αd, а через A{αl=1,...,d} — d-мерную матрицу (n − k)-го
порядка, получаемую из A удалением элементов ai1i2...id таких, что i1 ∈ α1, i2 ∈ α2,. . . , id ∈ αd. Матрицы
A[αl=1,...,d] и A{αl=1,...,d} будем называть дополнитель-
ными друг другу.
Рассмотрим перманент суммы двух матриц. Пусть A =
(ai1i2...id) иB = (bi1i2...id) — две d-мерные матрицы по-
рядка n. Тогда
Per(A + B) =
= sc
(
Πn
i1=1
Σn
i2,...,id=1
(ai1i2...id + bi1i2...id) ιi2...id
)
=
= sc
(
Πn
i1=1
(
Σn
i2,...,id=1
ai1i2...idιi2...id +
+
Σn
i2,...,id=1
bi1i2...idιi2...id
))
=
= sc
Σn
k=0
Σ
αl
∈Qk,n
l=1,...,d
(
Σ
d∈D(A[αl=1,...,d])
Π
a∈d
aιa
)
×
×
(
Σ
d∈D(B{αl=1,...,d
})
Π
b∈d
bιb
))
=
=
Σn
k=0
Σ
αl
∈Qk,n
l=1,...,d
[
sc
(
Σ
d∈D(A[αl=1,...,d])
Π
a∈d
aιa
)
×
× sc
(
Σ
d∈D(B{αl=1,...,d
})
Π
b∈d
bιb
)]
=
=
Σn
k=0
Σ
αl
∈Qk,n
l=1,...,d
Per(A[αl=1,...,d])Per(B{αl=1,...,d}).
Таким образом, перманент суммы двух матриц равен сум-
ме по всем подматрицам первой матрицы (включая пустую)
произведений перманента подматрицы на перманент до-
полнительной матрицы аналогичной подматрицы во второй
матрице.
2. Перечисление многомерных перестановок
Обычное понятие перестановки легко обобщается на
многомерный случай. Пусть, например, числа 1, 2, . . . , n
расположены в матрице n × n так, что в каждой строке
и каждом столбце стоит ровно по одному числу. Назовем та-
кое расположение двумерной (квадратичной) перестанов-
кой n-го порядка. За тождественную можно принять пе-
рестановку, при которой каждое число i расположено на
пересечении i-й строки и i-го столбца.
Пример. Квадратичные перестановки 2-го порядка:
(
1 ·
· 2
)
,
(
2 ·
· 1
)
,
(
· 1
2 ·
)
,
(
· 2
1 ·
)
.
Квадратичные перестановки 3-го порядка:
1 · ·
· 2 ·
· · 3
,
1 · ·
· · 3
· 2 ·
, . . .
Аналогично можно рассмотреть трехмерные (кубические)
(т. е. расположение чисел от 1 до n в кубе n × n × n),
четырехмерные, пятимерные и т. д. перестановки. Вооб-
ще, d-мерную перестановку можно определить как набор d
Известия Коми научного центра Уральского отделения Российской академии наук № 5 (71), 2024
Серия «Физико-математические науки»
www.izvestia.komisc.ru
13
обычных перестановок (π1, π2, . . . , πd) [4]. Первая отве-
чает за перестановку чисел 1, 2, . . . , n в одном «направ-
лении», вторая — в другом и т. д. Как и в обычном (одно-
мерном) случае, каждой такой перестановке можно поста-
вить в соответствие (d + 1)-мерную (0, 1)-матрицу (мат-
рицу перестановки). В этой матрице элементы на позици-
ях (i, π1(i), π2(i), . . . , πd(i)) будут равны единице, а все
остальные элементы равны нулю. В такой матрице каждая
гипергрань будет содержать ровно одну единицу.
Отметим, что существуют и другие подходы к понятию
многомерной перестановки. Так, в работах [5, 6] рассмат-
риваются многомерные перестановки, которые задаются
многомерными (0, 1)-матрицами, содержащими ровно по
одной единице в каждой одномерной грани. В работе [6]
такие перестановки называют плотными (англ. dense) в от-
личие от рассмотренных выше разреженных (англ. sparse).
Плотные перестановки однозначно ассоциируются с ла-
тинскими квадратами размерности n. В дальнейшем под
многомерной перестановкой мы будем понимать разрежен-
ную перестановку.
В качестве примера рассмотрим многомерное обобще-
ние перестановок без неподвижных точек (беспорядков).
Напомним, что беспорядком (англ. derangement) называ-
ется перестановка π ∈ Sn такая, что π(i) ̸= i для лю-
бого i = 1, 2, . . . , n. При обобщении таких перестано-
вок на многомерный случай возникают сразу несколько ва-
риантов. Частичным d-мерным беспорядком n-го порядка
назовем такую d-мерную перестановку (π1, π2, . . . , πd),
что для любого i ∈ {1, 2, . . . , n} найдется k такое,
что πk(i) ̸= i. Применяя метод включений-исключений
нетрудно показать, что общее число таких перестановок
равно
pd(n) =
Σn
k=0
(−1)kCk
n [(n − k)!]d .
Пусть m ≤ d. d-Мерным беспорядком n-го по-
рядка по m индексам назовем d-мерную переста-
новку (π1, π2, . . . , πd), в которой найдутся индексы
k1, k2, . . . , km такие, что для любого i ∈ {1, 2, . . . , n}
πk1(i) ̸= i, πk2(i) ̸= i, . . . , πkm(i) ̸= i. Опять же, ис-
пользуя принцип включения-исключения, можно показать,
что общее число таких беспорядков равно
ld(n) = (n!)d
(
Σn
k=0
(−1)k
k!
)m
.
Как и в классическом случае, любая (d + 1)-мерная
(0, 1)-матрица A задает целый класс d-мерных переста-
новок. А именно, в этот класс попадают те перестановки,
для матриц инцидентности P которых выполняется нера-
венство P ≤ A, т. е. каждый элемент матрицы P не боль-
ше соответствующего элемента матрицы A. Тогда перма-
нент матрицы A, как и в классическом случае, будет ра-
вен числу перестановок в этом классе. Например, если рас-
смотреть (d+1)-мерную матрицу n-го порядкаAd+1
n , у ко-
торой диагональные элементы aii...i, i = 1, 2, . . . , n рав-
ны нулю, а все остальные элементы — единице, то перма-
нент такой матрицы будет равен числу частичных d-мер-
ных беспорядков n-го порядка (ср. [2]):
PerAd+1
n = pd(n).
Рассмотрим (d + 1)-мерную (0, 1)-матрицу n-го порядка
Bd+1
n , в которой элемент равен нулю тогда и только тогда,
когда его первый индекс совпадает с одним из m других
индексов под номерами k1, k2, . . . , km. Тогда перманент
этой матрицы равен числу беспорядков по m индексам:
PerBd+1
n = ld(n).
В данных примерах, зная количество перестановок в клас-
се, мы говорили о значении перманента. Но это соотноше-
ние можно использовать и в обратную сторону: вычисляя
(оценивая) перманент многомерной (0, 1)-матрицы, полу-
чать характеристику количества соответствующих много-
мерных перестановок.
3. Заключение
В работе рассмотрено выражение перманента много-
мерных матриц через произведение однородных элемен-
тов коммутативной ассоциативной алгебры с нильпотент-
ными индекса 2 образующими. На основе этой взаимосвя-
зи доказаны некоторые простейшие свойства перманента.
Рассмотрена его связь с перечислением многомерных пе-
рестановок. В частности, более подробно разобран случай
многомерных беспорядков.
Отметим, что перманент обычных (двумерных) матриц
задается сходным образом с определителем, но, по срав-
нению с последним, является менее «удобной» для изуче-
ния функцией, так как обладает значительно меньшей сим-
метрией с точки зрения преобразований матриц. Многие
задачи, связанные с перманентом, не имеют «хорошего»
решения в общем виде и сводятся к рассмотрению частных
случаев. В многомерном варианте сложность, естественно,
еще более возрастает. Тем не менее переход в высшие раз-
мерности полезен с той точки зрения, что помимо самосто-
ятельного интереса позволяет с другого ракурса взглянуть
и на «базовый» двумерный случай.
Автор заявляет об отсутствии конфликта интересов.
1. Минк, Х. Перманенты / Х. Минк. – Москва : Мир, 1982. – 210 с2.
2. Тараненко, А. А. Перманенты многомерных матриц: свойства и приложения / А. А. Тараненко // Дискретный анализ и исследование операций. – 2016. – Т. 23, № 4. – C. 35–101.
3. Шевелев, В. С. Некоторые вопросы теории перечисления перестановок с ограниченными позициями / В. С. Шевелёв // Итоги науки и техники. Серия Теор. вероятн. Мат. стат. Теор. кибернет. – 1992. – Т. 30. – С. 113–177.
4. Zhang, H. Enumeration of factorizable multi-dimensional permutations / H. Zhang, D. Gildea // Journal of Integer Sequences. – 2007. – Vol. 10. 14
5. Linial, N. An upper bound on the number of high-dimensional permutations / N. Linial, Z. Luria // Combinatorica. – 2014. – V. 25, № 4. – P. 471–486.
6. Eriksson, K. A Combinatorial Theory of Higher-Dimensional Permutation Arrays / K. Eriksson, S. Linusson // Advances in Applied Mathematics. – 2000. – V. 25. – P. 194–211.
