Весовые свойства примитивных матриц | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/2

Весовые свойства примитивных матриц

Для неотрицательных матриц порядка n > 2 представлены результаты, характеризующие зависимость свойства примитивности от веса (количества положительных элементов) матрицы: 1) любая матрица веса k ^ n непримитивная; 2) для k = n + 1,...,n2 - n + 1 существует и непримитивная матрица веса k, и примитивная матрица веса k с экспонентом 7, где n + 2 |_д/2(n - 1)J ^ 7 + k ^ n2 - n + 3; 3) любая матрица веса k = n2 - n + 2,...,n2 - 1 примитивная, её экспонент 7 = 2. Установлено, что при возведении в степень некоторых примитивных матриц вес степеней матрицы изменяется немонотонно.

Weight properties of primitive matrices.pdf Введение Неотрицательная матрица A называется примитивной, если существует такое натуральное число y, что для любого t ^ y матрица A является положительной. Наименьшее такое y называется экспонентом матрицы A и обозначается exp A. Количество положительных элементов неотрицательной матрицы A порядка n назовём весом матрицы A и обозначим через ||A||. 1. Зависимость свойства примитивности от веса матрицы Примитивная матрица называется минимальной, если после замены любого положительного элемента нулём она не является примитивной. Такие матрицы представляют интерес с точки зрения экономной реализации систем, описываемых с помощью примитивных матриц. В [1, 2] исследованы некоторые свойства минимальных примитивных матриц, в том числе связанные с весом матрицы. В частности, в [2] для любой неотрицательной матрицы A порядка n > 3 показано: а) любая примитивная матрица A веса n + 1 является минимальной; б) для любого k £ {n+2,... , n2} существует неминимальная примитивная матрица A веса k; в) для любого k £ {n + 2,... , 2n - 3} существует минимальная примитивная матрица A веса k. Следующая теорема характеризует связь веса и экспонента неотрицательных матриц, в том числе минимальных примитивных матриц. Теорема 1. Пусть A - неотрицательная матрица порядка n > 2. Тогда: а) любая матрица A веса k ^ n непримитивная, для любого k £ {n + 1,..., n2 - n + 1} существует непримитивная матрица A веса k; б) любая матрица A веса k £ {n2 - n + 2,...,n2 - 1} является примитивной, при этом exp A = 2, для любого k £ {2n - 1,...,n2 - n + 1} существует такая примитивная матрица A веса k, что exp A = 2; в) для любого k £ {n + 1, . . . , n2 - n + 1} существует такая примитивная матрица A веса k, что n + 2|_^2(n - 1)J ^ exp A + ||A|| ^ n2 - n + 3. 2. Монотонность зависимости веса степени матрицы от показателя степени Множество неотрицательных матриц разбивается на 2 класса: для первого класса свойство монотонности зависимости веса степени матрицы от показателя степени выполняется, для второго класса -не выполняется. Критерий такого разбиения пока не установлен, его определение является перспективной задачей. Установлен ряд свойств. Вычислительный эксперимент показал, что для всех примитивных матриц порядка n ^ 4 верна гипотеза о монотонной зависимости веса примитивной матрицы от её степени. Однако уже для n = 5 гипотеза опровергается. Обозначим: U - матрица порядка n, состоящая из положительных элементов; U(i j) (U(ij))-матрица порядка n, где в i-й строке (i-м столбце) все элементы, кроме j-го, положительные, остальные элементы нулевые; E(ij) -матрица порядка n, где элемент с номером (i, j) положительный, остальные элементы нулевые. Теорема 2. Пусть для матрицы A порядка n > 4 выполнено одно из условий: A = Ufa + U(j j) + E(j , i) для некоторых i, j G {1,... , n}, i = j; A = U(ti) + U(jj) + E(j,i) + E(pq) для некоторых i, j,p, q G {1, . . . , n} i = j, p = j, q = i,j или q = ^ p = i,j; а) б) (j j) + U(i ,) + E(p,q) для некоторых i,p, q G {1,..., n}, p, q = i; U(^i) + U(i;i) + E(pq) + E(r,s) для некоторых i,p, q, r, s G {1,... , n}, p, q = i, r = p, s = i, q или s = q, r = i,p. Тогда A примитивная, 7 = exp A = 5 для случаев п. а, б, 7 = 4 для случаев п. в, г; существует такое t < 7, что неравенство ||A*|| ^ ||At+11| неверно. Замечание 1. По результатам вычислительного эксперимента установлено, что для n = 5 указанные в теореме 2 классы полностью покрывают множество примитивных матриц порядка n, для которых свойство монотонности веса нарушается. При n ^ 6 имеются другие классы. Например, значения весов матриц A1, t = = 1,... , 9, где A1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 образуют последовательность {11,12, 22, 21, 20, 30, 31, 30, 36}. Используем отношение частичного порядка на множестве неотрицательных матриц порядка n. Пусть A = (a, j), B = (bi,j), положим A ^ B тогда и только тогда, когда i j A2 ^ bi,j для всех пар (i, j). Опишем частный класс матриц первого класса. Утверждение 1. Если A > P, где P - некоторая подстановочная матрица, то ||A*|| ^ ||At+1||, t = 1, 2,... Замечание 2. Обратное утверждение в общем случае неверно. Например, значения весов матриц A2, t = 1,... , 4, где A A U (i,i) 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 образуют последовательность {12,17, 32, 36}, однако не существует такой подстановочной матрицы P, что A2 > P.

Ключевые слова

weight of matrix, exponent of matrix, primitive matrix, вес матрицы, экспонент матрицы, примитивная матрица

Авторы

ФИООрганизацияДополнительноE-mail
Кяжин Сергей НиколаевичНациональный исследовательский ядерный университет «МИФИ»ассистент Института интеллектуальных кибернетических системs.kyazhin@kaf42.ru
Всего: 1

Ссылки

Фомичев В. М. Свойства минимальных примитивных орграфов jj Прикладная дискретная математика. 2015. №2(28). С. 86-96.
Бар-Гнар Р. И., Фомичев В. М. О минимальных примитивных матрицах jj Прикладная дискретная математика. Приложение. 2014. №7. С. 7-9.
 Весовые свойства примитивных матриц | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/2

Весовые свойства примитивных матриц | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/2