Russian Federation
UDK 519.1 Комбинаторный анализ. Теория графов
The permanent of multidimensional matrices is expressed in terms of operations on elements of commutative algebra with nilpotent index 2 generators. Using a technique based on this relationship, several properties of the permanent have been proved. Various types of multidimensional permutations are considered. The permanent of multidimensional matrices is considered from the point of view of the enumeration function of multidimensional permutations.
multidimensional matrix, permanent, multidimensional permutation
Введение
Перманент матрицы 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. Minc, H. Permanents / H. Minc. – Cambridge University Press, 1984. – 205 p.
2. Taranenko, A. A. Permanenty mnogomernyh matrits: svojstva i prilozhenija [Permanents of multidimensional matrices: properties and applications] / A. A. Taranenko // Diskretnyj analiz i issledovanie operacij [Discrete Analysis and Operations Research]. – 2016. – Vol. 23., № 4. – P. 35–101.
3. Shevelev, V. S. Some problems of the theory of enumerating the permutations with restricted positions / V. S. Shevelev // Journal of Soviet Mathematics. – 1992. – Vol. 61, № 4. – P. 2272–2317.
4. Zhang, H. Enumeration of factorizable multi-dimensional permutations / H. Zhang, D. Gildea // Journal of Integer Sequences. – 2007. – Vol. 10.
5. Linial, N. An upper bound on the number of high-dimensional permutations / N. Linial, Z. Luria // Combinatorica. – 2014. – Vol. 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. – Vol. 25. – P. 194–211.
