京都大学 情報学研究科 知能情報学専攻 2025年8月実施 情報学基礎 F1-1

标签：

• Kyoto-University
• Companion-Matrix-for-Linear-Recurrences
• Eigenvalues-and-Eigenvectors
• Matrix-Inverse
• Matrix-Power
• Matrix-Limit
• Matrix-Rank
• Kernel-and-Image

Author

祭音Myyura

Description

Q.1

Suppose that a sequence $\{x_k \mid k \text{ is a positive integer}\}$ satisfies the recurrence formula,

$$x_1 = 1, x_2 = 2, x_3 = 1, x_m = a x_{m-1} - a x_{m-2} + b x_{m-3}$$

where $a$ and $b$ are real numbers, and $m$ is an integer greater than or equal to 4. Let $\boldsymbol{y}_m = (x_m \ x_{m-1} \ x_{m-2})^{\mathrm{T}}$. Answer the following questions, where $n$ is an integer greater than or equal to 4. $\mathrm{I}$ is the identity matrix of order 3, and $A^{\mathrm{T}}$ stands for the transpose of a matrix $A$.

(1) Find a matrix $A$ which satisfies $\boldsymbol{y}_{m+1} = A \boldsymbol{y}_m$.

(2) Find $a$ and $b$ for which $A - \mathrm{I}$ is invertible. For the values $a$ and $b$, determine $(A - \mathrm{I})^{-1}$.

(3) Let $a = -\frac{1}{2}$ and $b = \frac{1}{4}$. Compute the eigenvalues of $A$, and $\lim_{n \to \infty} A^n$.

(4) With the same condition as (3), express $\sum_{k=1}^n x_k$ using $\sum_{m=4}^n \boldsymbol{y}_m$, and compute $\lim_{n \to \infty} \sum_{k=1}^n x_k$ using the results of (1) – (3).

Q.2

In the following, we assume that all elements of matrices are real numbers. In what follows, a matrix with $m$ rows and $n$ columns is called an $m \times n$ matrix. Let $\mathrm{O}_{m \times n}$ be the zero matrix of $m$ rows and $n$ columns, and $\mathrm{I}_n$ be the identity matrix of order $n$. The rank of a matrix $M$ is denoted by $\mathrm{rank}(M)$. Let $A$ be a $k \times m$ matrix, and $B$ be an $m \times n$ matrix. Prove each of the following statements (1) to (5) if it holds, or if it does not hold, give a counterexample of a pair $(A, B)$ and disprove the statement with it.

(1) $\mathrm{rank}(AB) \leq \mathrm{rank}(B)$.

(2) If $k = m$ and $A$ is non-singular, $\mathrm{rank}(AB) = \mathrm{rank}(B)$.

(3) $\mathrm{rank}(A) + \mathrm{rank}(B) - m \leq \mathrm{rank}(AB)$.

(4) If $AB = \mathrm{O}_{k \times n}$, $\mathrm{rank}(A) + \mathrm{rank}(B) \leq m$.

(5) If $n = k$ and $AB = \mathrm{I}_k$, $\mathrm{rank}(A) = k$.

Kai

Q.1

Let

$$\boldsymbol{y}_m= \begin{pmatrix} x_m\\ x_{m-1}\\ x_{m-2} \end{pmatrix}, \qquad x_m=ax_{m-1}-ax_{m-2}+bx_{m-3}.$$

(1)

$$\boldsymbol{y}_{m+1}=A\boldsymbol{y}_m,$$

with

$$\boxed{ A= \begin{pmatrix} a&-a&b\\ 1&0&0\\ 0&1&0 \end{pmatrix} }.$$

(2)

$$A-I= \begin{pmatrix} a-1&-a&b\\ 1&-1&0\\ 0&1&-1 \end{pmatrix}, \qquad \det(A-I)=b-1.$$

Therefore,

$$\boxed{A-I\text{ is invertible iff }b\ne1}.$$

For $b\neq 1$,

$$\boxed{ (A-I)^{-1} = \frac{1}{b-1} \begin{pmatrix} 1&b-a&b\\ 1&1-a&b\\ 1&1-a&1 \end{pmatrix} }.$$

(3)

For

$$a=-\frac12,\qquad b=\frac14,$$

the characteristic polynomial is

$$\det(\lambda I-A) = \left(\lambda+\frac12\right) \left(\lambda^2-\frac12\right).$$

Hence the eigenvalues are

$$-\frac12,\qquad \frac1{\sqrt2},\qquad -\frac1{\sqrt2}.$$

All have absolute value less than $1$, so

$$\boxed{ \lim_{n\to\infty}A^n=O }.$$

(4)

Since

$$\boldsymbol{y}_{m+1}-\boldsymbol{y}_m = (A-I)\boldsymbol{y}_m,$$

we have

$$\sum_{m=4}^{n}\boldsymbol{y}_m = (A-I)^{-1} \left(\boldsymbol{y}_{n+1}-\boldsymbol{y}_4\right).$$

Here,

$$x_4=\frac34, \qquad \boldsymbol{y}_4= \begin{pmatrix} \frac34\\ 1\\ 2 \end{pmatrix}.$$

Because $\boldsymbol{y}_{n+1}\to\boldsymbol{0}$,

$$\sum_{m=4}^{n}\boldsymbol{y}_m \longrightarrow -(A-I)^{-1}\boldsymbol{y}_4.$$

Taking the first component,

$$\lim_{n\to\infty}\sum_{k=1}^{n}x_k = 4+\frac83.$$

Therefore,

$$\boxed{ \lim_{n\to\infty}\sum_{k=1}^{n}x_k = \frac{20}{3} }.$$

Q.2

Let $A$ be a $k\times m$ matrix and $B$ an $m\times n$ matrix.

(1)

Since

$$\operatorname{Im}(AB) = A(\operatorname{Im}B),$$

a linear map cannot increase dimension. Thus,

$$\boxed{ \operatorname{rank}(AB)\le\operatorname{rank}(B) }.$$

(2)

If $k=m$ and $A$ is invertible, then

$$B=A^{-1}(AB).$$

Using part (1) in both directions,

$$\boxed{ \operatorname{rank}(AB)=\operatorname{rank}(B) }.$$

(3)

Let $U=\operatorname{Im}(B)$. Applying rank-nullity to the restriction $A|_U$,

$$\operatorname{rank}(B) = \operatorname{rank}(AB) + \dim(U\cap\ker A).$$

Since

$$\dim(U\cap\ker A) \le m-\operatorname{rank}(A),$$

we get

$$\boxed{ \operatorname{rank}(A)+\operatorname{rank}(B)-m \le \operatorname{rank}(AB) }.$$

(4)

If $AB=O$, then

$$\operatorname{Im}(B)\subseteq\ker(A).$$

Therefore,

$$\operatorname{rank}(B) \le m-\operatorname{rank}(A),$$

so

$$\boxed{ \operatorname{rank}(A)+\operatorname{rank}(B)\le m }.$$

(5)

If $n=k$ and $AB=I_k$, then

$$k=\operatorname{rank}(AB)\le\operatorname{rank}(A)\le k.$$

Hence,

$$\boxed{ \operatorname{rank}(A)=k }.$$