← К списку задач

Задача 16

Условие задачи

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

Решение задачи

Пусть $A$ — квадратная матрица порядка $n$, такая что $A$ обратима, все элементы $A$ неотрицательны, и все элементы $A^{-1}$ неотрицательны.

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

Рассмотрим произведение $AA^{-1} = I$. Обозначим $A = \left(a_{ij}\right)$, $A^{-1} = \left(b_{jk}\right)$. Тогда для элементов произведения $AA^{-1} = \sum\limits_{j=1}^n a_{ij} b_{jk}$. Но так как $AA^{-1} = I$, имеем

$$\sum\limits_{j=1}^n a_{ij} b_{jk} = \begin{cases} 1, & \text{при } i = k \\ 0, & \text{при } i \neq k \end{cases} \tag{1}$$

По условию $a_{ij} \geqslant 0$, $b_{jk} \geqslant 0$ для всех $i$, $j$, $k$. Следовательно, каждое слагаемое в сумме $\left(1\right)$ неотрицательно. Пусть $i \neq k$. Тогда из $\left(1\right)$: $\sum\limits_{j=1}^n a_{ij} b_{jk} = 0$. Т.к. сумма неотрицательных чисел равна нулю, это возможно только тогда, когда $a_{ij} b_{jk} = 0$ для всех $j$. Фиксируем строку $i$ матрицы $A$, тогда из этого следует, что для любого $j$, если $a_{ij} > 0$, то $b_{jk} = 0$ для всех $k \neq i$.

Т.е. если в строке $i$ матрицы $A$ элемент $a_{ij}$ положителен, то $j$-й столбец матрицы $A^{-1}$ имеет единственный (может не иметь) ненулевой элемент — в строке $i$. $\left(2\right)$

Т.к. матрица $A^{-1}$ обратима, её столбцы линейно независимы и, в частности, не равны нулевому вектору. Предположим противное: пусть некоторый столбец, скажем, $c_j$, равен нулевому вектору: $c_j = 0$. Тогда существует нетривиальная линейная комбинация, равная нулю: $1 \cdot c_j + 0 \cdot c_1 + \ldots + 0 \cdot c_{j-1} + 0 \cdot c_{j+1} + \ldots + 0 \cdot c_n = 0$. Это противоречит линейной независимости столбцов. Следовательно, каждый столбец $A^{-1}$ содержит хотя бы один ненулевой элемент.

Теперь предположим, что в строке $i$ матрицы $A$ существует два различных индекса $j_1 \neq j_2$, такие что $a_{ij_1} > 0$, $a_{ij_2} > 0$. Тогда

Рассмотрим столбцы $c^{\left(1\right)} = \left(0 \, \ldots \, \alpha \, \ldots \,0\right)^{\mathrm{T}}$ и $c^{\left(2\right)} = \left(0 \, \ldots \, \beta \, \ldots \,0\right)^{\mathrm{T}}$, где $\alpha > 0$, $\beta > 0$, и оба ненулевых элемента стоят в одной и той же строке $i$. Далее рассмотрим линейную комбинацию $\beta c^{\left(1\right)} - \alpha c^{\left(2\right)}$. Посчитаем её элементы: во всех строках, кроме $i$-й, обе компоненты равны нулю, поэтому разность равна нулю, а в строке $i$: $\beta \alpha - \alpha \beta = 0$. Следовательно, $\beta c^{\left(1\right)} - \alpha c^{\left(2\right)} = 0$. При этом коэффициенты $\beta$ и $\alpha$ не равны нулю. По определению это означает, что векторы $c^{\left(1\right)}$ и $c^{\left(2\right)}$ линейно зависимы.

Таким образом, столбцы матрицы $A$ с номерами $j_1$ и $j_2$ линейно зависимы, что противоречит обратимости матрицы $A^{-1}$. Противоречие. Следовательно, в каждой строке матрицы $A$ ровно один ненулевой элемент.

Применяя те же рассуждения к равенству $A^{-1} A = I$, получаем: в каждом столбце матрицы $A$ ровно один ненулевой элемент.

Итак, матрица $A$ обладает следующими свойствами: в каждой строке ровно один ненулевой элемент, в каждом столбце ровно один ненулевой элемент, все ненулевые элементы положительны. Следовательно, существует перестановка строк, при которой все ненулевые элементы окажутся на главной диагонали. $\square$