Произведение двух нижнетреугольных матриц.

[Sdy]

Хотел бы попросить проверить доказательство следующего утверждения.
Утверждение.
Произведение двух нижнетреугольных матриц есть матрица нижнетреугольная.
Для начала введём следующее
Определение.
Квадратная матрица $A$ называется нижнетреугольной, если $ \forall i,j : i < j \Rightarrow a_{ij} = 0$.
Доказательство.
Пусть имеется две нижнетреугольные матрицы $(a_{ij})$ и $(b_{ij}), i,j = 1..n$.
Матрицу, получающуюся в результате произведение этих матриц обозначим как $(r_{ij})$.
Значит нам нужно доказать, что $ \forall i,j : i < j \Rightarrow r_{ij} = 0 $.
Рассмотрим произвольный элемент матрицы $R$. Из определения матричного произведения он равен:
$r_{ij} = \sum\limits_{k=1}^{n}a_{ik}b_{kj}$.
Докажем, что он равен нулю, как только $i < j$.
Тогда для любого из слагаемых, образующих в сумме такой элемент возможны три варианта:
1)$i < j < k$. Но так как $i < k$,то это слагаемое равно нулю.
2)$k < i < j$. $k < j$, значит и такое слагаемое будет равно нулю.
3)$i < k < j$. $i < k$, следовательно и это слагаемое будет нулевое.
Но это означает, что как только $i < j$, так $r_{ij} = 0$, а значит матрица $R$ - нижнетреугольная.$\triangle$.

[mihaild]

Да, всё так. На самом деле первый и третий случай можно объединить: т.к. $i < j$, то не может быть что $k \leqslant i$ и одновременно $k \geqslant j$. Значит будет либо $k > i$ либо $k < j$.

[Sdy]

mihaild,
Понял, спасибо.

[ewert]

Sdy в сообщении #1410428 писал(а):

возможны три варианта:
1)$i < j < k$. Но так как $i < k$,то это слагаемое равно нулю.
2)$k < i < j$. $k < j$, значит и такое слагаемое будет равно нулю.
3)$i < k < j$. $i < k$, следовательно и это слагаемое будет нулевое.

Чего-то откровенно не хватает: какие-то из неравенств должны быть нестрогими, иначе перебор не полон.
Но дело не в этом -- перебор вообще не нужен. Смысл-то ведь в чём: если $i<j$, то хотя бы один из сомножителей каждого слагаемого нулевой, т.е. или $i<k$, или $k<j$. Ну так тупо от противного: если предположить, что $i\geqslant k$ и одновременно $k\geqslant j$, то $i\geqslant j$, ч.т.д.

И стилистический дефект:

Sdy в сообщении #1410428 писал(а):

$ \forall i,j : i < j \Rightarrow a_{ij} = 0$

-- это тавтология. Надо или $ (\forall i,j\colon i < j) \ a_{ij} = 0$, или просто $i < j \Rightarrow a_{ij} = 0$.

[Munin]

Поделим матрицу $n\times n$ на блоки  $\bigl(\!\begin{smallmatrix}k\times k&k\times m\\m\times k&m\times m\end{smallmatrix}\!\bigr),\quad k+m=n.$

Заметим, что если матрица нижнетреугольная (всё аналогично для верхнетреугольных), то верхний правый блок 0, а диагональные блоки сами нижнетреугольные; и обратное тоже верно. Прямым вычислением:

$$\begin{pmatrix}A&0\\B&C\end{pmatrix}\begin{pmatrix}D&0\\E&F\end{pmatrix}=\begin{pmatrix}AD\!&\,\medspace 0\,\,\,\\\ldots\!&\ldots\end{pmatrix}\!.$$

Теперь по индукции. Положим $k=n-1,$ тогда матрица-произведение будет нижнетреугольной, если $AD$ нижнетреугольная.
Основание индукции: $k=1$ или даже $k=0$ - очевидно.
Шаг индукции: выполнен.

-- 15.08.2019 11:17:37 --

P. S. Как-то странно, что символов ◺ ◹ ◣ ◥ нет в TeX-е. Они очевидно подходили бы для сокращения понятий "нижнетреугольный" и "верхнетреугольный".

[ewert]

Munin в сообщении #1410485 писал(а):

Поделим матрицу $n\times n$ на блоки

Треугольную на треугольные. Это будет любопытно.

Munin в сообщении #1410485 писал(а):

Как-то странно, что символов ◺ ◹ ◣ ◥ нет в TeX-е.

Особенно двух первых треугольных символов.