Задача 16

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

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

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

Пусть матрица $A = \begin{bmatrix}a_{ij}\end{bmatrix}$ обратима, порядка $n$, и $B := A^{-1} = \begin{bmatrix}b_{jk}\end{bmatrix}$. По условию $a_{ij} \geqslant 0$ и $b_{jk} \geqslant 0$ при всех $i, \, j, \, k$. Элементы единичной матрицы $I$ удобно записывать одним символом: обозначим через $\delta_{ik}$ её $\left(i, k\right)$-элемент, то есть $\delta_{ik} = 1$ при $i = k$ и $\delta_{ik} = 0$ при $i \ne k$. Поэлементно

$$\left(AB\right)_{ik} = \sum\limits_{j=1}^n a_{ij} b_{jk} = \delta_{ik} \ \text{,} \tag{1}$$

$$\left(BA\right)_{ik} = \sum\limits_{j=1}^n b_{ij} a_{jk} = \delta_{ik} \ \text{,} \tag{2}$$

Матрица $A$ обратима, значит по утверждению из §2.14 её столбцы линейно независимы, а по задаче 12 – и строки. Нулевой вектор не входит в линейно независимую систему, поэтому у $A$ нет ни нулевого столбца, ни нулевой строки. Матрица $B = A^{-1}$ тоже обратима, поэтому те же рассуждения дают: у $B$ нет ни нулевого столбца, ни нулевой строки.

Зафиксируем $i \ne k$. В $\left(1\right)$ правая часть равна $0$, а слева стоит сумма неотрицательных слагаемых $a_{ij} b_{jk} \geqslant 0$; сумма неотрицательных чисел равна нулю лишь тогда, когда каждое слагаемое нулевое, поэтому

$$a_{ij} b_{jk} = 0 \quad \text{для всех } j \text{, если } i \ne k \ \text{.} \tag{3}$$

Точно так же из $\left(2\right)$ при $i \ne k$

$$b_{ij} a_{jk} = 0 \quad \text{для всех } j \text{, если } i \ne k \ \text{.} \tag{4}$$

Докажем, что в каждой строке $A$ ровно один ненулевой элемент. Предположим противное: пусть в строке $i$ матрицы $A$ есть два ненулевых (а из-за неотрицательности – положительных) элемента $a_{ip} > 0$ и $a_{iq} > 0$, $p \ne q$. По $\left(3\right)$ (берём слагаемое $j = p$, затем $j = q$; первый индекс совпадает с нашей строкой $i$): для каждого $k \ne i$

$$a_{ip} b_{pk} = 0 \Rightarrow b_{pk} = 0 \ \text{,} \\ a_{iq} b_{qk} = 0 \Rightarrow b_{qk} = 0 \ \text{.}$$

Значит строки p и q матрицы B обнуляются во всех столбцах $k \ne i$: у каждой из них единственный возможный ненулевой элемент стоит в $i$-м столбце. Выше доказано, что строки $B$ ненулевые, поэтому $b_{pi} > 0$ и $b_{qi} > 0$. Но тогда строки $p$ и $q$ матрицы $B$ пропорциональны: во всех столбцах $k \ne i$ обе имеют нули ($b_{pk} = b_{qk} = 0$), а в $i$-м столбце $b_{pi} = \dfrac{b_{pi}}{b_{qi}} b_{qi}$; поэтому строка $p$ равна строке $q$, умноженной на число $\dfrac{b_{pi}}{b_{qi}}$. Значит, строки $p$ и $q$ матрицы $B$ линейно зависимы. Но $B$ обратима, значит по §2.14 её столбцы независимы, а по задаче 12 – и её строки; противоречие. Следовательно, в строке $i$ не более одного ненулевого элемента. Но так как нулевых строк нет, в каждой строке $A$ ровно один ненулевой элемент, и он положителен.

Докажем, что в каждом столбце $A$ ровно один ненулевой элемент. Проведём зеркальное рассуждение, поменяв в нём роли строк и столбцов и опираясь на $\left(4\right)$ вместо $\left(3\right)$. Предположим, что в столбце $k$ матрицы $A$ есть два положительных элемента $a_{rk} > 0$ и $a_{sk} > 0$, $r \ne s$. По $\left(4\right)$ (берём слагаемое $j = r$, затем $j = s$; второй индекс совпадает с нашим столбцом $k$): для каждого $i \ne k$

$$b_{ir} a_{rk} = 0 \Rightarrow b_{ir} = 0 \ \text{,} \\ b_{is} a_{sk} = 0 \Rightarrow b_{is} = 0 \ \text{.}$$

Значит столбцы $r$ и $s$ матрицы $B$ обнуляются во всех строках $i \ne k$: у каждого единственный возможный ненулевой элемент стоит в $k$-й строке. Выше доказано, что столбцы B ненулевые, поэтому $b_{kr} > 0$ и $b_{ks} > 0$. Но тогда столбцы $r$ и $s$ матрицы $B$ пропорциональны: во всех строках $i \ne k$ оба имеют нули ($b_{ir} = b_{is} = 0$), а в $k$-й строке $b_{kr} = \dfrac{b_{kr}}{b_{ks}} b_{ks}$; поэтому столбец $r$ равен столбцу $s$, умноженному на число $\dfrac{b_{kr}}{b_{ks}}$. Значит столбцы $r$ и $s$ матрицы $B$ линейно зависимы. Но $B$ обратима и по §2.14 её столбцы линейно независимы; противоречие. Значит в столбце $k$ не более одного ненулевого элемента, но ненулевых столбцов нет, значит в каждом столбце $A$ ровно один ненулевой элемент.

Получили, что у $A$ в каждой строке и в каждом столбце стоит ровно по одному ненулевому (положительному) элементу. Значит эти $n$ ненулевых элементов занимают $n$ различных строк и $n$ различных столбцов – по одному в каждой строке и по одному в каждом столбце.

Переставим строки $A$ так: на $m$-е место поставим ту строку, единственный ненулевой элемент которой стоит в $m$-м столбце. Для каждого $m = 1, \, \ldots, \, n$ такая строка существует и единственна, потому что в $m$-м столбце ровно один ненулевой элемент; при этом каждая строка $A$ используется ровно один раз (у неё единственный ненулевой элемент, отвечающий одному столбцу). Поэтому мы действительно лишь переставили строки $A$; полученную матрицу обозначим $\widetilde{A}$.

По построению в $m$-й строке матрицы $\widetilde{A}$ единственный ненулевой элемент стоит в $m$-м столбце, то есть на главной диагонали, а все элементы вне диагонали равны нулю. Значит $\widetilde{A}$ – диагональная матрица (и даже с положительной диагональю). $\square$