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

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.

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\).