О норме и спектральном радиусе неотрицательных матриц

3. О норме и спектральном радиусе неотрицательных матриц

Хорошо известно, что проблема нахождения нормы линейного оператора, спектрального радиуса оператора являются трудной проблемой и в конечномерном случае. В то же время, иногда важно не вычисляя нормы оператора знать, как она изменится в случае некоторого преобразования.

В данной работе изучается влияние распределения ненулевых элементов неотрицательной матрицы на норму соответствующего оператора и спектрального радиуса.

Определим пространство  как множество всех наборов вида

a=(a₁, a₂,…, a_N)

с нормой

.

Множество Q={(k,l):k,l=1,…,N} назовем решеткой размерности N x N. Любое множество Q₀={(k_i,l_j): , } будет являться подрешеткой размерности r x m.

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

r(A)=,

где l_k- собственные значения оператора A.

Пусть m ≤ N, d₁,…,d_m - положительные числа. Через D_m обозначим множество неотрицательных матриц А, ненулевые элементы которых принимают значения d₁,…,d_m. Через P(A) обозначим множество индексов соответствующих положительным элементам. Пусть AÎD_m. Если D={(k_i,l_j), i=1,…,q, j=1,…,p} подрешетка, содержащая P(A), то для соответствующего оператора А

Как видно из этого определения, от перестановки строк и столбцов матрицы норма не меняется.

Пусть даны положительные числа d₁,…,d_m и натуральное число m < N².

Будем исследовать следующие вопросы:

Как расположить числа d₁,…,d_m в решетке Q, чтобы норма линейного оператора A_Q соответствующего решетке (матрице) Q была максимальной?

Пусть в неотрицательной решетке Q m положительных элементов. Как расположить (m+1)-ый элемент, чтобы норма линейного оператора A_Qсоответствующей полученной решетке была максимальной?

Как расположить числа d₁,…,d_m в решетке Q, чтобы спектральный радиус был минимальным (максимальным)?

Справедливы следующие теоремы:

Теорема 3.1 Пусть d₁,…,d_m положительные числа, D_m- класс неотрицательных матриц, ненулевые элементы которых принимают значения d₁,…,d_m. Если m ≤ N, Q₀ -произвольная подрешетка размерности 1 m, то

.

Доказательство. Воспользуемся определением и неравенством Коши-Буняковского, получаем

Неравенство в обратную сторону очевидно.

Теорема доказана.

Данное утверждение говорит о том, что если ненулевых элементов меньше либо равно N, то своего максимума норма достигается когда все ненулевые элементы расположены в одной строке или в одном столбце.

Теорема 3.2 Пусть d₁=…=d_m=d, то есть D_m– множество всех матриц, имеющие m ненулевых элементов, которые равны числу d. Q₀ -произвольная решетка, симметричная относительно главной диагонали размерности nn, где n=min{r: r² ≥ m}. Тогда

,

где [m^1/2] - целая часть числа m^1/2.

Доказательство. Из свойства спектрального радиуса имеем для AÎD_m

.

Пусть Q₁ -подрешетка, также симметричная относительно главной диагонали размерности . Тогда для AÎD_m, Q₁ÌP(A)ÌQ₀ имеет место представление

А=А₁+А₀, где А₁,А₀ÎD_m, Р(А₁)=Q₁, P(A₀)ÌQ₁\Q₀.

Учитывая, что матрицы А₀ и А₁ неотрицательны, получаем

,

поэтому r(A₀)≤r(A).

С другой стороны А₁ – симметричная матрица и следовательно

.

Таким образом,

.

Теорема доказана.

Теорема 3.3 Пусть множество GÌQ, где Q - решетка размерности nn таково, что, если (k,l)ÎG, то (l,m),(n,k)ÏG для всех n,mÎ{1,2,…,N}.

Тогда, если P(A)ÌG, то r(P(A))=0.

Доказательство. Не трудно проверить, что для матрицы А с ненулевыми элементами из G (т.е. P(A)ÌG) имеет место равенство А²=0, т.е. А – нильпотентная матрица индекса 2 и следовательно у нее единственное собственное значение 0.

Теорема доказана.

Теорема 3.4 Пусть AÎD_m. Пусть Q₀ -минимальная подрешетка содержащая P(A), (Q₀ÉP(A)) такая, что в каждой строке и в каждом столбце находится хотя бы один элемент соответствующий нулевому элементу матрицы A.

Пусть A_d – матрица, полученная из матрицы A добавлением элемента со значением d>0 в одно из свободных мест, тогда

Доказательство.

Так как норма оператора не зависит от перестановки строк и столбцов матрицы, то можно считать, что решетка A₀={(i,j), i=1,…,l; j=1,…,m} расположена в левом верхнем углу матрицы A. Пусть добавлен еще один ненулевой элемент d с координатами (i₀,j₀) вне решетки Q₀. Возможны три случая:

1)  1 ≤ i₀ ≤ l, j₀ > m;

2)  i₀ > l, 1 ≤ j₀ ≤ m;

3)  i₀ > l, j₀ > m.

Рассмотрим первый случай. Не уменьшая общности положим, что этот ненулевой элемент соответствует индексу (1, m+1). По условию теоремы в каждой строке и в каждом столбце имеется хотя бы один нулевой элемент и мы можем предположить, что a_1m=0. Получаем:

Используя неравенства

,

имеем:

Пусть z₁=x₁, z₂=x₂,…,z_m= и

,

тогда

где элемент  имеет координаты (1,m).

Следовательно

Рассмотрим второй случай. Пусть добавленный ненулевой элемент соответствует индексу (l+1,1). Учитывая, что в каждой строке и в каждом столбце решетки есть хотя бы один ненулевой элемент и то, что от перестановки строк норма матрицы не меняется, мы можем предположить, что a_l1=0. Аналогично первому случаю имеем:

.

Используя неравенства

,

получаем:

.

Пусть z₁=y₁, z₂=y₂,…,z_m= и

,

тогда

где элемент  имеет координаты (l,1). Следовательно

Рассмотрим последний случай. Не уменьшая общности положим, что этот ненулевой элемент соответствует индексу (l+1, m+1). В этом случае нужно учесть, что от перестановки строк и столбцов норма матрицы не изменится, поэтому можно положить, что a_lm=0. Рассуждая также, как и в предыдущих случаях, получаем:

где элемент  имеет координаты (l,m).

Теорема доказана. Аналогичные задачи для интегральных операторов были рассмотрены в работах [1], [5].