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

标签：

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

Author

kainoj

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'$。

可直接使用以下事实：

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

考点

• 三角矩阵的封闭性：用矩阵乘法的元素表达式证明下三角结构及单位对角线在乘法下保持。
• 三角矩阵求逆：计算具体单位下三角矩阵的逆，并运用逆矩阵仍为同类三角矩阵的性质。
• LU 分解唯一性：由两种分解推出一个矩阵同时为单位下三角和上三角矩阵，从而证明各因子唯一。

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}$:

$$(LL')_{i,i} = \sum_{k=1}^{n} L_{i,k} \cdot L'_{k,i} = L_{i,1} L'_{1,i} + L_{i,2} L'_{1,i} + \dots + L_{i,i} L'_{i,i} + \dots + L_{i,n} L'_{n,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$.

Assume that inverses of $U, U_1$ exist. 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$.