Ноав. Прикладная дискретная математика теоретические основы прикладной дискретной математики 4(18) теоретические основы прикладной дискретной математики

• Название: Прикладная дискретная математика теоретические основы прикладной дискретной математики 4(18) теоретические основы прикладной дискретной математики
• Дата: 03.12.2021
• Размер: 0.51 Mb.
• Имя файла: 23_noav.pdf
• Тип: Документы; #290712

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
Теоретические основы прикладной дискретной математики
№4(18)
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК ПОЛОЖИТЕЛЬНЫЕ СВОЙСТВА НЕОТРИЦАТЕЛЬНЫХ МАТРИЦ
К. Г. Когос
∗
, В. М. Фомичев
∗∗
∗
Национальный исследовательский ядерный университет (МИФИ), г. Москва, Россия
∗∗
Финансовый университет при Правительстве Российской Федерации, г. Москва, Россия Дан обзор результатов исследования примитивности графов (неотрицательных матриц) и некоторых направлений обобщения. Приведены оценки экспонентов различных классов графов и систем графов (матриц и систем матриц).
Ключевые слова примитивный граф, примитивная матрица, экспонент, суб- экспонент.
Одним из положительных криптографических свойств преобразований векторных пространств является хорошее перемешивание, то есть зависимость каждой координатной функции от всех переменных. Перемешивающие свойства преобразования пространства P
n над полем P , заданного системой координатных функций {g
1
(x
1
, . . . , x n
), . . . , g n
(x
1
, . . . , x n
)}, определяются системой множеств, . . . , S(g n
)}, где S(g j
) — множество номеров существенных переменных координатной функции g j
(x
1
, . . . , x n
), j = 1, . . . , n. Наилучшее перемешивание достигается,
если каждая из координатных функций преобразования g зависит от всех переменных,
то есть S(g j
) = {1, . . . , n}, j = 1, . . . , n. Такие преобразования принято называть совершенными. Обобщениями свойства совершенности функций являются такие свойства,
как строгий лавинный критерий, критерии распространения, свойство «бент».
Почти все преобразования векторного пространства P
n над конечным полем P являются совершенными при n → ∞. Однако подобный вывод неприменим к функциям,
используемым в криптографических системах, так как они выбираются неслучайно, а из отображений с рядом заданных свойств. Поэтому изучение перемешивающих свойств криптографических функций — актуальная задача криптографического ана- лиза.
Некоторые функции с полным перемешиванием обладают свойством распространения искажений входных данных, что позволяет использовать их в криптосистемах аутентификации. С другой стороны, к функциям шифрования с неполным перемешиванием входов применимы методы определения ключа типа последовательного опробования, что делает привлекательным использование в криптосистеме шифрования совершенных преобразований.
Аппаратная или программная реализация совершенных преобразований затруднена в связи с необходимостью реализации функций от большого числа переменных.
Поэтому для хорошего перемешивания используются итерации (возведение в степень)
преобразования с относительно слабыми перемешивающими свойствами. Показатель степени преобразования, при которой достигается хорошее перемешивание, является

КГ. Когос, В. М. Фомичев важной криптографической характеристикой. В частности, показатель степени раун- довой подстановки блочного шифра, при которой достигается хорошее перемешивание,
является определяющим при выборе разработчиком числа циклов шифрования.
Матрицу A над полем действительных чисел называют положительной (неотрицательной, если положительны (неотрицательны) все её элементы, при этом пишут > 0 (A > 0). Носителем неотрицательной матрицы A = (a i,j
) называется 0, матрица, где v(a i,j
) = 1, если a i,j
> 0, и v(a i,j
) = 0, если a i,j
= 0, при всех допустимых i, j. Заметим, что v есть гомоморфизм мультипликативного моноида неотрицательных матриц над полем действительных чисел на мультипликативный моноид 0, матриц, где v(AB) = v(A) · Точное определение множества {S(g
1
), . . . , S(g n
)} является во многих случаях сложной вычислительной задачей. Поэтому при исследовании перемешивающих свойств степеней преобразований применяется оценочный теоретико-графовый или матричный подход. Обозначим Γ(g) перемешивающий вершинный орграф преобразования, в котором пара (i, j) является дугой тогда и только тогда, когда i ∈ S(g j
),
i, j ∈ {1, . . . , n}. Матрицу M (g) смежности вершин графа Γ(g) называют перемешивающей матрицей преобразования g. Суть оценочного подхода состоит в исследовании степеней матрицы M (g) и определении наименьшего натурального числа t, такого, что (g))
t
> 0. Корректность такого подхода вытекает, например, из следствия 2 теоремы если матрица (M (g))
t не положительна, то преобразование g несовершенно. Оценочный теоретико-графовый или матричный подход реализуется существенно проще сточки зрения сложности вычислений, чем точное вычисление множеств существенных переменных.
При исследовании перемешивающих свойств часто используется эпиморфизм мультипликативного моноида неотрицательных матриц порядка n на моноид вершинных орграфов, где умножение графов определено как умножение бинарных отношений. При эпиморфизме ϕ матрице M соответствует орграф Γ с множеством вершин, . . . , n} и множеством дуг U , где (i, j) ∈ U ⇔ m i,j
> 0. При эпиморфизме ϕ выполнено, если и только если граф Γ = ϕ(M ) полный. Эпиморфизм ϕ всякой неотрицательной матрице A ставит в соответствие орграф Γ = ϕ(A), матрица смежности вершин которого есть v(A). В частности, ϕ(M (g)) = Γ(g) для графа Γ. Следовательно, орграф Γ = ϕ(A) полный в томи только в том случае, если A > 0. И вообще,
система понятий, связанных с изучением перемешивающих свойств преобразований,
применима как для неотрицательных матриц, таки для графов.
Ограничение эпиморфизма ϕ на подмоноид симметричных матриц (для них m
i,j
= m j,i при всех допустимых i, j) есть эпиморфизм на подмоноид вершинных неориентированных графов.
Настоящий обзор посвящён положительным свойствам неотрицательных матриц,
под которыми понимаются свойства, связанные со способностью порождения тем или иным способом положительной матрицы. Обзор содержит известные результаты по оценке таких характеристик систем неотрицательных матриц (графов и орграфов, как экспоненты, множественные экспоненты, субэкспоненты. Экспонент системы неотрицательных матриц Ω есть наименьшая длина записи положительной матрицы в системе образующих Ω мультипликативной полугруппы. Множественный экспонент определяет наименьшую длину произведений образующих матриц, при которой каждое произведение данной длины есть положительная матрица. Субэкспонент неотрицательной матрицы есть наименьшее число первых членов мультипликативной циклической полугруппы, порождённой данной матрицей, сумма которых положительна

Положительные свойства неотрицательных матриц 1. Примитивность неотрицательных матриц
Неотрицательную матрицу A называют примитивной, если A
t
> 0 при некотором натуральном t, а наименьшее натуральное γ, при котором A
γ
> 0, называют экспонен- томили показателем примитивности матрицы A и обозначают как exp A. Если такого t не существует, то exp A = Абсолютная оценка экспонента примитивной матрицы A порядка n дана Виланд- том [2]:
exp A 6 n
2
− 2n + В [3, c. 409] получены выражения экспонента примитивной матрицы через характеристики матрицы (в частности, через число положительных элементов на главной диагонали. Пусть A — примитивная матрица порядка n, а матрица A
h имеет не менее d > 0 положительных элементов на главной диагонали для любого h > k прицелом неотрицательном k. Тогда exp A 6 2n − d + k − Отсюда следует, что если матрица A имеет не менее d > 0 положительных элементов на главной диагонали, то exp A 6 2n − d − и если положительны все элементы на главной диагонали, то exp A 6 n − Пусть матрица A примитивна и матрица A + . . . + A
h
, h
> 1, имеет не менее d > положительных элементов на главной диагонали. Тогда [3, c. 409]
exp A 6 n − d + h(n − Экспонент примитивной симметричной матрицы [3, c. 409] удовлетворяет оценке exp A 6 2(n − Замечание 1 [4, c. 140]. В связи с абсолютной оценкой (1) отметим, что Далмей- джем (Dulmage A. L.) и Мендельсоном (Mendelsohn N. S.) выделены лакуны, то есть некоторые числа, не превышающие n
2
− 2n + 2 и не являющиеся показателями примитивности какой-либо матрицы порядка n. Таковы, например, числа из интервалов 3n + 4, (n − 1)
2
) и (n
2
− 4n + 6, n
2
− 3n + 2). Прич тном n лакуной является интервал, объединяющий оба предыдущих. В [5] данные результаты усилены. Показано, что для любых целых n, t не существует примитивной матрицы порядка n, экспонент которой удовлетворяет неравенствам n
2
− tn +
1 4
(t + 1)
2
< exp A < n
2
− (t − 1)n + t − Замечание 2 [2, c. 243]. При n → ∞ случайная равновероятная 0, матрица порядка с вероятностью, стремящейся к единице, является примитивной и имеет экспонент равный двум.
Матрица A порядка n называется частично разложимой, если у нее есть нулевая подматрица размера r × s, r + s = n. Матрица A вполне неразложима, если она не является частично разложимой.
Известно [3, c. 300], что вполне неразложимая матрица A примитивна и exp A 6 n − Критерий примитивности матрицы A дан ниже в связи с рассмотрением орграфа = ϕ(A).

КГ. Когос, В. М. Фомичев
2. Примитивность графов
Примитивность графа определяется естественным образом граф Γ примитивен,
если примитивна матрица смежности его вершин, то есть неотрицательная матрица и орграф Γ = ϕ(A) одновременно примитивны или не примитивны, в случае примитивности их экспоненты равны. При исследованиях примитивности матриц и графов применяется как матричный, таки теретико-графовый язык.
Связь между графами и неотрицательными матрицами устанавливает следующая теорема [6]: пусть M — матрица смежности вершин графа Γ и M
t
= (m
(t)
ij
), тогда число путей длины t изв в графе Γ равно m
(t)
ij
, i, j ∈ {1, . . . , Таким образом, примитивность графа и величина экспонента определяются свойствами путей в графе. В частности, любой примитивный орграф Γ является сильно- связными не меньше диаметра графа Напомним, что абсолютная оценка диаметра сильносвязного вершинного орграфа имеет вид diam Γ
6 n.
2.1. Свойства экспонент о вор иен тированных графов В [7] указаны примитивные орграфы, на которых достигается абсолютная оценка. При n > 2 рассмотрим вершинный орграф Γ, состоящий из гамильтонова контура C = (1, 2, . . . , n), к которому добавлена дуга (i, j), где вершины i, j расположены на контуре C на расстоянии 2, i, j ∈ {1, . . . , n}. Множество вершинных орграфов, изоморфных орграфу Γ, назовём вершинными графами Виландта и обозначим это множество Γ
W
(n). При любом n > 2 множество Γ
W
(n) состоит из n! изоморфных графов абсолютная оценка Виландта достигается на графах Виландта, и только на них.
Для остальных примитивных вершинных орграфов Γ при нечётном n > 3 верна достижимая оценка (в соответствии с известными лакунами Γ 6 n
2
− 3n + Верхняя граница экспонента примитивного орграфа может быть понижена с. 227], если в орграфе известна длина простого контура. Пусть Γ — примитивный орграф с n вершинами, l — длина кратчайшего простого контура в Γ, тогда exp Γ 6 n + l(n − В частности, если в примитивном орграфе имеется петля, то exp Γ
6 2n − Граница (2) экспонента примитивного орграфа может быть понижена [7], если вор- графе известны длины l и λ двух простых контуров, где (l, λ) = 1. Пусть в вершинном орграфе Γ имеются простые контуры C и длины соответственно l и λ, где n > 2,
1 < λ < l 6 n и (l, λ) = 1. Обозначим C ∩ пересечение множеств вершин контуров и C
0
. Тогда) если C ∩ C
0
= ∅, то exp Γ 6 lλ − 2l − 3λ + 3n;
2) если C ∩ C
0
= H, где |H| = h > 0, то exp Γ 6 lλ − l − 3λ + h + Отсюда следует, что для любого примитивного вершинного орграфа Γ при n > верно) если контуры C и не имеют общих вершин, то exp Γ 6
 n + 1 2
  n + 1 2

6
n
2 4
+
n
2
+
1 4
;

Положительные свойства неотрицательных матриц 2) если контуры C и имеют h общих вершин, где 1 6 h 6 λ, то exp Γ 6
 n + h + 2 2
  n + h + 2 2

− 2h − n 6 n
2
− 2n + В [8] получена оценка диаметра и экспонента вершинного перемешивающего графа Γ(ϕ) обратимого преобразования ϕ регистра сдвига длины n надмножеством двоичных мерных векторов, где n, r — натуральные (такие графы возникают при рассмотрении обобщения блочных шифров Фейстеля). Подстановка ϕ такого регистра сдвига имеет вид, . . . , y n
) = (y
2
, . . . , y n
, ψ(y
2
, . . . , y n
) ⊕ где y
1
, . . . , y n
∈ V
r
; ψ(y
2
, . . . , y n
) называется функцией усложнения.
Пусть подстановка ϕ задается системой булевых координатных функций {ϕ
1
(x
1
, x
2
,
. . . , x nr
), ϕ
2
(x
1
, x
2
, . . . , x nr
), . . . , ϕ
nr
(x
1
, x
2
, . . . , x nr
)}. Тогда функции усложнения ψ(y
2
,
. . . , y n
) соответствует вершинный граф Γ
ψ
: пара (v, w) образует дугу тогда и только тогда, когда функция ϕ
(n−1)r+w зависит существенно от некоторой переменной из множества {x v
, x r+v
, . . . , x
(n−1)r+v
}. Показано, что перемешивающий граф Γ(ϕ) сильно связен тогда и только тогда, когда сильно связен граф Получено, что если граф Γ
ψ
сильносвязный и diam Γ
ψ
6 d, то) diam Γ(ϕ)
6 (n − 1) · min{d, r − 1} + n;
2) если граф Γ(ϕ) примитивный ив этом случае алгоритм блочного шифрования инволютивен), то diamΓ(ϕ)
6 n/2·min{d, r −1}+n;
3) если граф Γ(ϕ) примитивный, то exp Γ(ϕ)
6 n
2
r + nr − В [3, сдана оценка экспонентов турнира, то есть ориентированного вершинного орграфа T
n без петель, в котором каждая пара i, j различных вершин соединена ровно одной дугой. Турнир T
n называется приводимым, если существует такое разбиение множества вершин на два подмножества, что в T
n присутствуют все дуги,
направленные из первого блока разбиения во второй блок. В противном случае турнир называется неприводимым. Показано, что при n
> 4 турнир T
n примитивен тогда и только тогда, когда он неприводим. Экспонент турнира T
n оценивается при n
> через его диаметр d:
d 6 exp T
n
6 d + В общем случае 6 exp T
n
6 n − При n
> 6 и 3 < γ < n+2 существует неприводимый турнир T
n
, экспонент которого равен Для вершины i ориентированного вершинного графа, i = 1, . . . , n, обозначим через число дуг, входящих в вершину i, и через q i
— число дуг, исходящих из вершины i
(полустепень захода и полустепень исхода вершины i). Граф называется псевдосиммет- рическим, если p i
= q при i = 1, . . . , n (дихотомическим при p i
= q i
= 2, i = 1, . . . , В [9] получены верхние оценки экспонентов примитивных псевдосимметрических иди- хотомических графов, при этом рассматриваемые графы классифицированы по длине обхвата (кратчайшего контура. Класс сильносвязных псевдосимметрических графов с n вершинами, каждая из которых имеет не менее k (в точности k) входящих и исходящих дуг, с обхватом не менее p (в точности p) обозначается H(n, k, p) (G(n, k, p)). Класс

КГ. Когос, В. М. Фомичев примитивных графов из G(n, k, p) с обхватом в точности p обозначается P (n, k, Справедлива цепочка включений (n, k, p) ⊂ G(n, k, p) ⊂ H(n, k, В [9, § 3, ч. 3] описаны структурные свойства графов из множества G(n, 2, (При нечётном n > 12 доказано, что G(n, 2, (n − 1)/2) = P (n, 2, (n − 1)/2) и для любого ∈ P (n, 2, (n − 1)/2)
exp Γ 6
(n − 1)
2 4
+ Верхние оценки экспонентов дихотомических графов получены в [9, § 4, ч. Для любого орграфа Γ ∈ P (n, 2, p), где 3 6 p 6 dn/2e, доказано, что exp Γ 6
(p + 1)n
2p − 1
+ p(n − 2) + В [9, § 5, ч. 3] получены верхние оценки экспонентов графов из классов P (n, k, p) при p = 1, 2. В частности, для любого Γ ∈ P (n, k, 2), где k > 2, справедливо неравенство exp Γ 6











1 2

29
n − 1
k + 1
− 5

,
k > 6
n − 1
n + 1
− 1,
n +
1 2
 11n − 6
k + 1
− 3

, k 6 6
n − 1
n + 1
− Для любого Γ ∈ P (n, k, 1), где k > 2, выполнено exp Γ 6 3
 n − 1
k + 1
+
n − 2
k

− Универсальный критерий примитивности орграфа Γ [3, с. 226] определяется длинами его простых контуров. Если C
1
, . . . , C
k есть все простые контуры орграфа Γ длин l
1
, . . . , l соответственно, то сильносвязный орграф Γ примитивный, если и только если, . . . , l k
) = Периодом вершины i орграфа называется наибольший общий делитель таких чисел, что a
(k)
i,i
> 0, i = 1, . . . , n. Иными словами, период d вершины i равен наибольшему общему делителю длин всех контуров, проходящих через вершину i в орграфе Неотрицательная матрица A = (a i,j
) порядка n > 1 называется неразложимой (или неприводимой, если для всех i, j = 1, . . . , n существует t ∈ N , такое, что a
(t)
i,j
> 0, где (a
(t)
i,j
). Это означает, что орграф Γ = ϕ(A) сильносвязный: в орграфе Γ для любой пары вершин (i, j), i, j = 1, . . . , n, существует путь изв. Неразложимая матрица называется периодической (или циклической, если период любой вершины орграфа равен d > 1. Если d = 1 для некоторой вершины орграфа Γ, то матрица называется апериодической (или ациклической).
Универсальный критерий примитивности на матричном языке имеет вид [3, с. неотрицательная матрица A примитивна тогда и только тогда, когда A неразложима и апериодична.
Сумма неразложимой матрицы A и единичной матрицы I является примитивной матрицей (ей соответствует граф с n петлями, и exp(A + I)
6 n − Достаточные условия примитивности орграфа Γ(ϕ) подстановки ϕ регистра сдвига длины n надмножеством двоичных мерных векторов получены в [8]. Сильносвяз- ный граф Γ(ϕ) примитивен, если выполнено любое из следующих условий

Положительные свойства неотрицательных матриц 1) координатная функция ϕ
m зависит существенно от переменной x при некотором, в этом случае exp Γ(ϕ)
6 2nr − 2;
2) ψ(y
2
, . . . , y n
) = ψ(y n
, . . . , y
2
) и при некоторых m ∈ {(n−1)r+1, (n−1)r+2, . . . , и µ ∈ {1, . . . , r} координатная функция ϕ
m зависит существенно от переменной при n − 2j = 1, в этом случае exp Γ(ϕ)
6 (ln/2)
2
+ n(r − l) − 2, где l длина кратчайшего цикла графа Γ
ψ
, проходящего через дугу (µ, В [10] исследован алгоритм поискав глубину, используемый для определения длин всех простых циклов сильносвязного вершинного орграфа. Вычислительная сложность алгоритма оценивается величиной порядка O(n
2
log n), где элементарной операцией считается обращение к памяти и распознавание смежности двух вершин.
В [10] исследован также алгоритм распознавания примитивности вершинного орграфа и вычисления его экспонента, основанный на быстром возведении в степень матрицы смежности вершин. Алгоритм требует O(n
3
log n) операций сложения и умножения в поле GF(2).
2.2. Свойства экспонент о вне ориентированных графов В [7] сформулированы равносильные критерии примитивности неориентированных графов (далее просто графов) при условии, что ребро можно считать циклом длины 2:
1) связный вершинный граф G примитивен тогда и только тогда, когда в имеется простой цикл нечётной длины) связный вершинный граф G примитивен тогда и только тогда, когда G не является двудольным.
Универсальная оценка экспонента примитивного графа [3, с. 409] значительно ниже аналогичной оценки для примитивных орграфов. Если вершинный граф G примитивен, то exp G 6 2(n − Рассмотрим вершинный граф G. Обозначим при i 6= j, где i, j ∈ {1, . . . , n}:
w(i, j) — путь изв кратчайший путь изв кратчайший цикл, проходящий через вершину i; len[i, j] — длина пути [i, j], измеряемая числом рёбер графа составляющих путь.
Обозначим через e(C) эксцентриситет цикла C в неориентированном графе G, те, Верхнюю границу (3) экспонента графа G при n > 1 можно уточнить [7]: если l длина длиннейшего простого цикла C нечётной длины в примитивном вершинном графе G, 1 6 l 6 n, то exp Γ 6 2e(C) + l − 1 6 2n − l − Если простые циклы нечётных длин покрывают множество вершин графа G, то exp Γ 6 n − Построено множество графов [7], на которых достигается верхняя граница неравенства. Обозначим через Γ
P
(n) множество примитивных вершинных графов,
состоящих из гамильтонова пути и петли, инцидентной одной из концевых вершин.
При любом n > 1 множество Γ
P
(n) состоит из n! изоморфных графов абсолютная оценка exp Γ = 2n − 2 достигается на графах G из множества Γ
P
(n), и только на них

КГ. Когос, В. М. Фомичев
3. Оценки субэкспонентов и множественных экспонентов систем матриц
Неотрицательную матрицу A называют субпримитивной, если A
[1,t]
> 0, где t ∈ N ,
A
[1,t]
= A + A
2
+ . . . + A
t
. Субэкспонентом матрицы A называется наименьшее ∈ N , такое, что A
[1,σ]
> 0, и обозначается sbxp A. Если матрица A не субприми- тивна, то положим sbxp A = Понятия экспонента и субэкспонента могут быть обобщены на систему квадратных неотрицательных матриц Ω = {M
1
, . . . , M
p
} одинакового размера. Пусть N
p
=
= {1, . . . , p}, N
∗
p
— множество всех слов в алфавите N
p
. Слову w = s
1
. . . s из N
∗
p при заданной системе матриц Ω соответствует матрица M
s
1
. . . M
s l
, являющаяся элементом мультипликативной полугруппы hΩi неотрицательных матриц, порождённой системой. Обозначим M
s
1
. . . M
s l
= M (w) = (m i,j
(w)).
Экспонентом системы матриц Ω (обозначается exp Ω) называется наименьшая длина слова w ∈ N
∗
p
, при котором M (w) > 0. Если такого слова не существует, то полагаем exp Ω = ∞.
Cубэкспонентом системы матриц Ω (обозначается sbxp Ω) называется наименьшая длина l слова w ∈ N
∗
p
, при котором M
[1,l]
(w) > 0, где M
[1,l]
(w) = M
s
1
+ M
s
1
M
s
2
+ . . . +
+M (w). Если такого слова не существует, то полагаем sbxp Ω = Известно [11], что для любой системы Ω квадратных неотрицательных матриц одинакового размера справедливо sbxp Ω
6 exp Пусть G
s
— орграф с множеством вершин {1, . . . , n}, где все дуги помечены числом, а M
s
= (m ij
(s)) — матрица смежности вершин орграфа G
s
, s = 1, . . . , p. Тогда объединение графов G
(p)
= G
1
∪ . . . ∪ G
p есть либо орграф, либо мультиграф (в зависимости от множества объединяемых дуг, которому соответствует система матриц смежности Ω = {M
1
, . . . , M
p
}. При этом любой путь длины l в мультиграфе (графе) помечен словом в алфавите N
∗
p длины l. Отсюда система неотрицательных матриц Ω и соответствующий ей мультиграф одновременно примитивны (субпри- митивны) или не примитивны (не субпримитивны), в случае примитивности (субпри- митивности) их экспоненты (субэкспоненты) равны.
Для любого мультиграфа справедливо [11]
diam G
(p)
6 sbxp Ω,
причём если G = G
1
= . . . = G
p
, то diam G = sbxp В [11] показано, что мультиграф сильно связен тогда и только тогда, когда он субпримитивен. Если вершинный мультиграф сильно связен, то при n
> 4
sbxp Ω
6
(n
2
− 2)(n − Система квадратных неотрицательных матриц одинакового размера называется множественно примитивной, если существует натуральное l, такое, что для любого слова длины l в алфавите N
∗
p имеет место неравенство M (w) > 0. Минимальное число, обладающее таким свойством, называется множественным экспонентом системы матриц В [12] доказано, что множество вполне неразложимых матриц порядка n является множественно примитивными для множественного экспонента k имеет место оценка k 6 n − 1.

Положительные свойства неотрицательных матриц
13
Известна достижимая оценка множественного экспонента любой множественно примитивной системы Ω квадратных неотрицательных матриц порядка n: k
6 2
n
− Неотрицательная матрица A порядка n называется неразложимой, 0 6 r 6 если она не содержит нулевой подматрицы размера p × q, p + q = n − r + 1, 0 < p,
q 6 n − r. Наибольшее из чисел r, при которых матрица A является r-неразложимой,
называется индексом неразложимости Пусть Ω = {M
1
, . . . , M
p
} — система квадратных неотрицательных матриц порядка, где индекс неразложимости каждой матрицы M
i
, i = 1, . . . , p, не меньше некоторого фиксированного числа r, r
> 1. Тогда система Ω множественно примитивна [13],
причём для множественного экспонента k системы Ω справедливо k 6





n − 1
r
,
(n − 1) mod r = 0,
 n − 1
r

+ 1, (n − 1) mod r 6= ЛИТЕРАТУРА. Фомичев В. М. Методы дискретной математики в криптологии. М Диалог-МИФИ, 2009.
2. Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. S. 642–648.
3. Сачков В. Н, Тараканов В. Е. Комбинаторика неотрицательных матриц. М ТВП, 2000.
4. Носов В. А, Сачков В. Н, Тараканов В. Е. Комбинаторный анализ. Неотрицательные матрицы, алгоритмические проблемы // Итоги науки и техники. Сер. теория вер., матем.
статист., теорет. киберн. 1983. Т. 21. С. 120–178.
5. Lewin M. and Vitek Y. A system of gaps in the exponent set of primitive matrices // Illinois
J. Math. 1981. Issue 1. No. 25. P. 87–98.
6. Берж К. Теория графов и её применение. МИЛ. Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. № 2(12). С. 101–112.
8. Коренева А. М, Фомичев В. М. Об одном обобщении блочных шифров Фейстеля // Прикладная дискретная математика. 2012. № 3(17). С. 34–40.
9. Князев А. В. Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов дис. ... докт. физмат. наук. Мс. Кяжин С. Н, Фомичев В. М. О примитивных наборах натуральных чисел // Прикладная дискретная математика. 2012. № 2(16). С. 5–14.
11. Фомичев В. М. Свойства путей в графах и мультиграфах // Прикладная дискретная математика. 2010. № 1(7). С. 118–124.
12. Сачков В. Н. Вероятностные преобразователи и правильные мультиграфы // Труды по дискретной математике. 1997. Т. 1. С. 227–250.
13. Сачков В. Н, Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5. Вып. 2. С. 150–159.