CBMS-2019-08

题目来源：[[做题/文字版题库/CBMS/2019#Question 8|2019#Question 8]] 日期：2024-07-26 题目主题：Math-线性代数-正定矩阵

解题思路

本题涉及正定矩阵的性质以及特征值和特征向量的计算。通过这些性质，可以推导出正定矩阵的对角元素为正数、对称矩阵的特征值为实数、正定矩阵的特征值为正数等结论。最后一问利用特征向量的正交性质，计算出次大特征值。

Solution

1. Show the diagonal elements $A_{kk}(k=1,\dots ,n)$ of real positive definite matrix $\mathbf{A}$ are positive

Consider the standard basis vector ${\mathbf{e}}_k$ where the $k$-th element is 1 and all other elements are 0. Then,

$${\mathbf{e}}_k^T\mathbf{A}{\mathbf{e}}_k=A_{kk}.$$

Since $\mathbf{A}$ is positive definite, we have:

$${\mathbf{e}}_k^T\mathbf{A}{\mathbf{e}}_k>0.$$

Thus,

$$A_{kk}>0.$$

2. Show the eigenvalues of real symmetric matrix $\mathbf{A}$ are real

For a real symmetric matrix $\mathbf{A}$, consider its eigenvalue equation:

$$\mathbf{Ax}=\lambda \mathbf{x},$$

where $\mathbf{x}$ is an eigenvector and $\lambda$ is the corresponding eigenvalue. Since $\mathbf{A}$ is symmetric, we have:

$${\mathbf{x}}^T\mathbf{Ay}={\mathbf{y}}^T\mathbf{Ax}$$

for any vectors $\mathbf{x}$ and $\mathbf{y}$. Setting $\mathbf{y}=\mathbf{x}$, we get:

$${\mathbf{x}}^T\mathbf{Ax}={\mathbf{x}}^T(\lambda \mathbf{x})=\lambda ({\mathbf{x}}^T\mathbf{x}).$$

Since ${\mathbf{x}}^T\mathbf{x}>0$ (as $\mathbf{x}\ne 0$), $\lambda$ must be real.

3. Show the eigenvalues of positive definite matrix $\mathbf{A}$ are positive

Let $\mathbf{A}$ be a positive definite matrix and $\lambda$ be an eigenvalue with corresponding eigenvector $\mathbf{x}$:

$$\mathbf{Ax}=\lambda \mathbf{x}.$$

Taking the transpose of $\mathbf{x}$, we have:

$${\mathbf{x}}^T\mathbf{Ax}=\lambda {\mathbf{x}}^T\mathbf{x}.$$

Since $\mathbf{A}$ is positive definite, ${\mathbf{x}}^T\mathbf{Ax}>0$ and ${\mathbf{x}}^T\mathbf{x}>0$. Thus,

$$\lambda >0.$$

4. Let $S=\{\mathbf{v}\in {\mathbb{R}}^n\mid {\mathbf{v}}^T\mathbf{v}=1\}$ be the set of non-zero $n$-dimensional real column vectors $\mathbf{v}$ of unit length. Show ${\lambda }_1={\max }_{\mathbf{v}\in S}{\mathbf{v}}^T\mathbf{Av}$ is the largest eigenvalue of positive definite matrix $\mathbf{A}$

Definitions and Setup

• Let $\mathbf{A}$ be an $n\times n$ real symmetric positive definite matrix.
• The set $S=\{\mathbf{v}\in {\mathbb{R}}^n\mid {\mathbf{v}}^T\mathbf{v}=1\}$ represents the set of unit vectors in ${\mathbb{R}}^n$.
• We aim to show that the maximum value of the quadratic form ${\mathbf{v}}^T\mathbf{Av}$ over the set $S$ is the largest eigenvalue ${\lambda }_1$ of $\mathbf{A}$.

Step-by-Step Proof

1. Spectral Theorem Application: Since $\mathbf{A}$ is a real symmetric matrix, by the spectral theorem, it can be diagonalized as:

$$\mathbf{A}=\mathbf{Q\Lambda }{\mathbf{Q}}^T,$$

where $\mathbf{Q}$ is an orthogonal matrix (i.e., ${\mathbf{Q}}^T={\mathbf{Q}}^{-1}$) and $\mathbf{\Lambda }$ is a diagonal matrix containing the eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ of $\mathbf{A}$, with ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n>0$ since $\mathbf{A}$ is positive definite.

1. Quadratic Form Transformation: For any unit vector $\mathbf{v}\in {\mathbb{R}}^n$ (i.e., $\mathbf{v}\in S$), we can express $\mathbf{v}$ in terms of the orthonormal basis formed by the columns of $\mathbf{Q}$:

$$\mathbf{v}=\mathbf{Qy},$$

where $\mathbf{y}$ is a unit vector (${\mathbf{y}}^T\mathbf{y}=1$) in ${\mathbb{R}}^n$. Substituting this into the quadratic form gives:

$${\mathbf{v}}^T\mathbf{Av}=(\mathbf{Qy}{)}^T\mathbf{A}(\mathbf{Qy})={\mathbf{y}}^T{\mathbf{Q}}^T\mathbf{AQy}={\mathbf{y}}^T\mathbf{\Lambda y}.$$

1. Maximization over Unit Vectors: The expression ${\mathbf{y}}^T\mathbf{\Lambda y}$ can be written as:

$${\mathbf{y}}^T\mathbf{\Lambda y}=\sum _{i=1}^n{\lambda }_i{y}_i^2,$$

where $y_i$ are the components of the vector $\mathbf{y}$. Given that ${\sum }_{i=1}^n{y}_i^2=1$ (since $\mathbf{y}$ is a unit vector), we need to maximize the weighted sum of the eigenvalues with respect to $y_i^2$.

1. Eigenvalue Maximization:

   To maximize ${\sum }_{i=1}^n{\lambda }_i{y}_i^2$, note that the maximum value occurs when $y_1^2=1$ and $y_2^2=y_3^2=\cdots =y_n^2=0$ (because ${\lambda }_1$ is the largest eigenvalue). Hence,

$$\underset{{\mathbf{y}}^T\mathbf{y}=1}{\max }\sum _{i=1}^n{\lambda }_i{y}_i^2={\lambda }_1.$$

Therefore,

$$\underset{\mathbf{v}\in S}{\max }{\mathbf{v}}^T\mathbf{Av}={\lambda }_1.$$

1. Conclusion: The maximum value of the quadratic form ${\mathbf{v}}^T\mathbf{Av}$ over the unit sphere $S$ is indeed the largest eigenvalue ${\lambda }_1$ of the positive definite matrix $\mathbf{A}$.

5. Suppose the eigenvectors of positive definite matrix $\mathbf{A}$ are all different. Furthermore, suppose you know the largest eigenvalue ${\lambda }_1$ and its associated eigenvector ${\mathbf{v}}_1$. Explain how to compute the second largest eigenvalue ${\lambda }_2$ using ${\lambda }_1$ and ${\mathbf{v}}_1$ without computing the third largest or smaller eigenvalues

Given:

• $\mathbf{A}$ is a positive definite matrix.
• $\mathbf{A}$ has distinct eigenvalues ${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_n>0$.
• The largest eigenvalue ${\lambda }_1$ and its associated eigenvector ${\mathbf{v}}_1$ are known.

We aim to find the second largest eigenvalue ${\lambda }_2$ using ${\lambda }_1$ and ${\mathbf{v}}_1$.

Orthogonal Projection Method

1. Orthogonality of Eigenvectors: Since $\mathbf{A}$ is symmetric, its eigenvectors corresponding to distinct eigenvalues are orthogonal. Thus, ${\mathbf{v}}_1$ is orthogonal to all other eigenvectors of $\mathbf{A}$.

2. Defining the Subspace Orthogonal to ${\mathbf{v}}_1$: Let $S_1$ be the subspace of ${\mathbb{R}}^n$ consisting of vectors orthogonal to ${\mathbf{v}}_1$:

$$S_1=\{\mathbf{v}\in {\mathbb{R}}^n\mid {\mathbf{v}}^T{\mathbf{v}}_1=0\}.$$

1. Rayleigh Quotient in the Subspace: The Rayleigh quotient $R(\mathbf{v})$ for a vector $\mathbf{v}$ is given by:

$$R(\mathbf{v})=\frac{{\mathbf{v}}^T\mathbf{Av}}{{\mathbf{v}}^T\mathbf{v}}.$$

We need to maximize this quotient over the subspace $S_1$.

1. Projection Method: To find ${\lambda }_2$, we consider the effect of ${\mathbf{v}}_1$ and deflate $\mathbf{A}$ by projecting it onto the subspace orthogonal to ${\mathbf{v}}_1$.

   Define the matrix ${\mathbf{A}}^{\prime }$ as:

$${\mathbf{A}}^{\prime }=\mathbf{A}-{\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^T.$$

This matrix ${\mathbf{A}}^{\prime }$ removes the influence of ${\lambda }_1$ and ${\mathbf{v}}_1$. The matrix ${\mathbf{A}}^{\prime }$ still has the same eigenvectors as $\mathbf{A}$, but the eigenvalue ${\lambda }_1$ associated with ${\mathbf{v}}_1$ is replaced with 0.

1. Finding ${\lambda }_2$: The second largest eigenvalue ${\lambda }_2$ of $\mathbf{A}$ will be the largest eigenvalue of ${\mathbf{A}}^{\prime }$ in the subspace orthogonal to ${\mathbf{v}}_1$.

   To find ${\lambda }_2$, consider any vector $\mathbf{u}$ in $S_1$:

$$\mathbf{u}=\mathbf{v}-({\mathbf{v}}^T{\mathbf{v}}_1){\mathbf{v}}_1.$$

Here, $\mathbf{u}$ is the projection of $\mathbf{v}$ onto the subspace orthogonal to ${\mathbf{v}}_1$. Since $\mathbf{v}$ is in $S_1$, $\mathbf{u}=\mathbf{v}$.

1. Maximizing the Rayleigh Quotient: The Rayleigh quotient in the subspace $S_1$ for the matrix ${\mathbf{A}}^{\prime }$ becomes:

$$R^{\prime }(\mathbf{v})=\frac{{\mathbf{v}}^T{\mathbf{A}}^{\prime }\mathbf{v}}{{\mathbf{v}}^T\mathbf{v}}=\frac{{\mathbf{v}}^T(\mathbf{A}-{\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^T)\mathbf{v}}{{\mathbf{v}}^T\mathbf{v}}.$$

Since $\mathbf{v}\perp {\mathbf{v}}_1$, we have ${\mathbf{v}}^T{\mathbf{v}}_1=0$, and thus:

$$R^{\prime }(\mathbf{v})=\frac{{\mathbf{v}}^T\mathbf{Av}}{{\mathbf{v}}^T\mathbf{v}}.$$

Therefore, the maximum value of $R^{\prime }(\mathbf{v})$ in the subspace $S_1$ gives ${\lambda }_2$:

$${\lambda }_2=\underset{\mathbf{v}\in S_1}{\max }\frac{{\mathbf{v}}^T\mathbf{Av}}{{\mathbf{v}}^T\mathbf{v}}.$$

1. Conclusion: By maximizing the Rayleigh quotient in the subspace orthogonal to the eigenvector ${\mathbf{v}}_1$ associated with ${\lambda }_1$, we find the second largest eigenvalue ${\lambda }_2$.

知识点

正定矩阵特征值特征向量Rayleigh商正交性

难点思路

计算次大特征值的过程可能是一个难点，尤其是如何正确地使用正交性和 Rayleigh 商。

解题技巧和信息

• 正定矩阵的定义和性质非常重要，尤其是对特征值的影响。
• 计算特征值时，Rayleigh 商是一个有效工具。
• 正交性在分解和简化问题中非常有用。

重点词汇

• Positive definite matrix 正定矩阵
• Eigenvalue 特征值
• Eigenvector 特征向量
• Rayleigh quotient Rayleigh 商
• Orthogonal 正交的

参考资料

1. Linear Algebra and Its Applications by Gilbert Strang, Chapter 6.
2. Introduction to Linear Algebra by Gilbert Strang, Chapter 7.