東京大学 情報理工学系研究科 コンピュータ科学専攻 2016年2月実施 問題1

标签：

• Tokyo-University
• Lower-Upper-Decomposition
• Matrix-Inverse

Author

kainoj, 祭音Myyura

Description

A unit lower triangular matrix is a lower triangular matrix whose diagonal elements are all equal to $1$.

Answer the following questions.

(1) Suppose that $L$ and $L'$ are $n \times n$ lower triangular matrices. Prove that the product of them, $LL'$, is also a lower triangular matrix.

(2) Suppose that $L$ and $L'$ are $n \times n$ unit lower triangular matrices. Prove that $LL'$ is also a unit lower triangular matrix.

(3) Compute the inverse matrices of

$$L_1 = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \quad \text{and} \quad L_2 = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \end{pmatrix},$$

respectively.

(4) Suppose that an $n \times n$ invertible matrix $A$ is decomposed in two ways as $A = LU = L'U'$, where $U$ and $U'$ are upper triangular matrices, and $L$ and $L'$ are unit lower triangular matrices. Prove that $L = L'$ and $U = U'$.

You can use the following facts:

• (i) The inverse of an upper triangular matrix, if it exists, is also an upper triangular matrix.
• (ii) The inverse of a unit lower triangular matrix always exists, and it is also a unit lower triangular matrix.

题目描述

若一个下三角矩阵的所有对角元都等于 $1$，则称其为单位下三角矩阵。回答下列问题。

（1）设 $L,L'$ 是两个 $n\times n$ 下三角矩阵，证明乘积 $LL'$ 仍是下三角矩阵。

（2）设 $L,L'$ 是两个 $n\times n$ 单位下三角矩阵，证明 $LL'$ 仍是单位下三角矩阵。

（3）分别求下列矩阵的逆矩阵：

$$L_1=\begin{pmatrix}1&0\\2&1\end{pmatrix},\qquad L_2=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}.$$

（4）设可逆矩阵 $A\in\mathbb{R}^{n\times n}$ 有两种分解

$$A=LU=L'U',$$

其中 $U,U'$ 为上三角矩阵，$L,L'$ 为单位下三角矩阵。证明 $L=L'$ 且 $U=U'$。

可直接使用以下事实：

• 可逆上三角矩阵的逆矩阵仍为上三角矩阵；
• 单位下三角矩阵一定可逆，且其逆矩阵仍为单位下三角矩阵。

Kai

(1)

A lower triangular matrix $M$ has $M_{i,j} = 0$ for $i < j$. Let $L, L' \in \mathbb{R}^{n\times n}$ be a lower triangular matrices. Let's look closer at entries above diagonal of $LL'$, i.e. $(LL')_{i,j}$ for $i<j$:

$$(LL')_{i,j} = \sum_{k=1}^{n} L_{i,k} \cdot L'_{k,j}$$

Every item of the summation yields either $i<k$ or $k<j$. Thus, $(LL')_{i,j} = 0$ for $i<j$.

The same another way:

$$\begin{aligned} (LL')_{i,j} &= \sum_{k=1}^{n} L_{i,k} \cdot L'_{k,j} \\ &= \sum_{k=1}^{j-1} L_{i,k} \cdot L'_{k,j} + \sum_{k=j}^{n} L_{i,k} \cdot L'_{k,j} \\ &= \sum_{k=1}^{j-1} L_{i,k} \cdot 0 + \sum_{k=j}^{n} 0 \cdot L'_{k,j} \\ &= 0 \end{aligned}$$

(2)

Let $L, L' \in \mathbb{R}^{n\times n}$ be a unit lower triangular matrices, i.e $L_{i,j} = L'_{i,j} = 1$ for $i = j$. We know from question (1), that $LL'$ is lower triangular.

Let's examine diagonal items, $(LL')_{i,i}$:

For $k<i$, $L'_{k,i}=0$, and for $k>i$, $L_{i,k}=0$. Hence

$$(LL')_{i,i} =\sum_{k=1}^{n}L_{i,k}L'_{k,i} =L_{i,i}L'_{i,i}=1.$$

(3)

Inverse of a unit lower triangular matrix is also unit lower triangular. So, we need to find only one entry of the inverse of $L1$, such that:

$$L_1 L_1^{-1} = \begin{pmatrix} 1 & 0\\ 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0\\ x & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

Obviously, $x=-2$. Simillary, $L_2$:

$$L_2 L_2^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 \\ a & 1 & 0 \\ b & c & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

Here, $a = -2$, $b = 1$, $c = -2$.

(4)

Prove that if $A$ has two different LU decomposition, that is $A = LU = L_1U_1$ and $L, L_1$ are lower unit matrices, then $L=L_1$ and $U=U_1$.

Since $A$ is invertible and $L,L_1$ are unit lower triangular, $U=L^{-1}A$ and $U_1=L_1^{-1}A$ are invertible. Start with $A= LU = L_1 U_1 = A$ and multiply right-hand by $U^{-1}$ and left-hand by $L_1^{-1}$:

$$\begin{aligned} LU &= L_1 U_1 \\ L_1^{-1} L U U^{-1} &= L_1^{-1} L_1 U_1 U^{-1} \\ L_1^{-1} L &= U_1 U^{-1} \\ \end{aligned}$$

We know from question (2) that left-hand side of the last equation is lower unit triangular matrix. In similar manner, we can show that right-hand is upper triangular. Lower and upper triangular matrices can be equal iff they are both diagonal. Moreover, since $L_1^{-1} L$ has ones on diagonal, so $U_1 U^{-1}$ must have. We conclude:

$$L_1^{-1} L = Id = U_1 U^{-1}$$

That is, $L = L_1$ and $U = U_1$.