IS Math-2018-01

题目来源：Problem 1 日期：2024-07-21 题目主题：Math-线性代数-线性方程组与广义逆矩阵

具体题目

Consider to solve the following simultaneous linear equation:

$$\mathbf{Ax}=\mathbf{b}$$

where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$ are a constant matrix and a vector, and $\mathbf{x}\in {\mathbb{R}}^n$ is an unknown vector. Answer the following questions.

(1) An $m\times (n+1)$ matrix $\bar{\mathbf{A}}=(\mathbf{A}|\mathbf{b})$ is made by adding a column vector after the last column of matrix $\mathbf{A}$. In the case of $\mathbf{A}=\left(\begin{array}{ccc}1& 0& -1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$ and $\mathbf{b}=\left(\begin{array}{c}2\\ 4\\ 2\end{array}\right)$,

$$\bar{\mathbf{A}}=\left(\begin{array}{cccc}1& 0& -1& 2\\ 1& 1& 0& 4\\ 0& 1& 1& 2\end{array}\right)$$

is obtained. Let the $i$-th column vector of the matrix $\bar{\mathbf{A}}$ be ${\mathbf{a}}_i$ $(i=1,2,3,4)$.

(i) Find the maximum number of linearly independent vectors among ${\mathbf{a}}_1,{\mathbf{a}}_2$ and ${\mathbf{a}}_3$.

(ii) Show that ${\mathbf{a}}_4$ can be represented as a linear sum of ${\mathbf{a}}_1,{\mathbf{a}}_2$ and ${\mathbf{a}}_3$, by obtaining scalars $x_1$ and $x_2$ that satisfy ${\mathbf{a}}_4=x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+{\mathbf{a}}_3$.

(iii) Find the maximum number of linearly independent vectors among ${\mathbf{a}}_1,{\mathbf{a}}_2,{\mathbf{a}}_3$ and ${\mathbf{a}}_4$.

(2) Show that the solution of the simultaneous linear equation exists when $\mathrm{rank}\bar{\mathbf{A}}=\mathrm{rank}\mathbf{A}$ for arbitrary $m,n,\mathbf{A}$ and $\mathbf{b}$.

(3) There is no solution when $\mathrm{rank}\bar{\mathbf{A}}>\mathrm{rank}\mathbf{A}$. When $m>n$, $\mathrm{rank}\mathbf{A}=n$ and $\mathrm{rank}\bar{\mathbf{A}}>\mathrm{rank}\mathbf{A}$, obtain $\mathbf{x}$ that minimizes the squared norm of the difference between the left hand side and the right hand side of the simultaneous linear equation, namely $\Vert \mathbf{b}-\mathbf{Ax}{\Vert }^2$.

(4) When $m<n$ and $\mathrm{rank}\mathbf{A}=m$, there exist multiple solutions for the simultaneous linear equation for arbitrary $\mathbf{b}$. Obtain $\mathbf{x}$ that minimizes $\Vert \mathbf{x}{\Vert }^2$ among them, by adopting the method of Lagrange multipliers and using the simultaneous linear equation as the constraint condition.

(5) Show that there exists a unique $\mathbf{P}\in {\mathbb{R}}^{n\times m}$ that satisfies the following four equations for arbitrary $m,n$ and $\mathbf{A}$.

$$\mathbf{APA}=\mathbf{A}$$ $$\mathbf{PAP}=\mathbf{P}$$ $$(\mathbf{AP}{)}^T=\mathbf{AP}$$ $$(\mathbf{PA}{)}^T=\mathbf{PA}$$

(6) Show that both $\mathbf{x}$ obtained in (3) and $\mathbf{x}$ obtained in (4) are represented in the form of $\mathbf{x}=\mathbf{Pb}$.

正确解答

(1)

(i) Find the maximum number of linearly independent vectors among ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, and ${\mathbf{a}}_3$.

To determine the linear independence of ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, and ${\mathbf{a}}_3$, we form the matrix $\mathbf{A}$:

$$\mathbf{A}=\left(\begin{array}{ccc}1& 0& -1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$$

We can perform row reduction on $\mathbf{A}$ to determine its rank.

Row reduction steps:

1. Swap rows 1 and 2:

$$\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& -1\\ 0& 1& 1\end{array}\right)$$

1. Subtract row 1 from row 2:

$$\left(\begin{array}{ccc}1& 1& 0\\ 0& -1& -1\\ 0& 1& 1\end{array}\right)$$

1. Add row 2 to row 3:

$$\left(\begin{array}{ccc}1& 1& 0\\ 0& -1& -1\\ 0& 0& 0\end{array}\right)$$

The rank of $\mathbf{A}$ is 2, so the maximum number of linearly independent vectors among ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, and ${\mathbf{a}}_3$ is 2.

(ii) To represent ${\mathbf{a}}_4$ as a linear sum of ${\mathbf{a}}_1,{\mathbf{a}}_2$ and ${\mathbf{a}}_3$, we need to solve:

$$x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+{\mathbf{a}}_3={\mathbf{a}}_4$$

This gives us the system of equations:

$$\{\begin{array}{l}{x}_1-x_2=2\\ x_1+x_2=4\\ x_2+1=2\end{array}$$

Solving this system:

$x_2=1$

$x_1=3$

Therefore, ${\mathbf{a}}_4=3{\mathbf{a}}_1+{\mathbf{a}}_2+{\mathbf{a}}_3$.

(iii) Find the maximum number of linearly independent vectors among ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, ${\mathbf{a}}_3$, and ${\mathbf{a}}_4$.

Since ${\mathbf{a}}_4$ can be expressed as a linear combination of ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, and ${\mathbf{a}}_3$, adding ${\mathbf{a}}_4$ does not increase the number of linearly independent vectors. Therefore, the maximum number of linearly independent vectors among ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, ${\mathbf{a}}_3$, and ${\mathbf{a}}_4$ is 2.

(2)

To show that the solution exists when $\mathrm{rank}\bar{\mathbf{A}}=\mathrm{rank}\mathbf{A}$, we use the Rouché-Capelli theorem.

If $\mathrm{rank}\bar{\mathbf{A}}=\mathrm{rank}\mathbf{A}$, it means that the augmented matrix $\bar{\mathbf{A}}$ has the same rank as the coefficient matrix $\mathbf{A}$. This implies that the vector $\mathbf{b}$ lies in the column space of $\mathbf{A}$.

In other words, there exists a linear combination of the columns of $\mathbf{A}$ that equals $\mathbf{b}$. This linear combination is precisely the solution $\mathbf{x}$ to the equation $\mathbf{Ax}=\mathbf{b}$.

Therefore, when $\mathrm{rank}\bar{\mathbf{A}}=\mathrm{rank}\mathbf{A}$, a solution exists for the simultaneous linear equation.

(3)

When $\mathrm{rank}\bar{\mathbf{A}}>\mathrm{rank}\mathbf{A}$, $m>n$, and $\mathrm{rank}\mathbf{A}=n$, we are dealing with an overdetermined system with no exact solution. We need to find the least squares solution.

To minimize $\Vert \mathbf{b}-\mathbf{Ax}{\Vert }^2$, we differentiate with respect to $\mathbf{x}$ and set it to zero:

$$\frac{\partial }{\partial \mathbf{x}}(\mathbf{b}-\mathbf{Ax}{)}^T(\mathbf{b}-\mathbf{Ax})=-2{\mathbf{A}}^T(\mathbf{b}-\mathbf{Ax})=0$$

This gives us the normal equation:

$${\mathbf{A}}^T\mathbf{Ax}={\mathbf{A}}^T\mathbf{b}$$

Since $\mathrm{rank}\mathbf{A}=n$, ${\mathbf{A}}^T\mathbf{A}$ is invertible. Therefore, the least squares solution is:

$$\mathbf{x}=({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T\mathbf{b}$$

(4)

When $m<n$ and $\mathrm{rank}\mathbf{A}=m$, there exist multiple solutions for the simultaneous linear equation for arbitrary $\mathbf{b}$. Obtain $\mathbf{x}$ that minimizes $\Vert \mathbf{x}{\Vert }^2$ among them, by adopting the method of Lagrange multipliers and using the simultaneous linear equation as the constraint condition.

We need to minimize $\Vert \mathbf{x}{\Vert }^2$ subject to the constraint $\mathbf{Ax}=\mathbf{b}$. The Lagrangian is:

$$L(\mathbf{x},\lambda )=\Vert \mathbf{x}{\Vert }^2+{\lambda }^T(\mathbf{Ax}-\mathbf{b})$$

Taking the gradient and setting it to zero:

$$\frac{\partial L}{\partial \mathbf{x}}=2\mathbf{x}+{\mathbf{A}}^T\lambda =0\Rightarrow \mathbf{x}=-\frac{1}{2}{\mathbf{A}}^T\lambda$$ $$\frac{\partial L}{\partial \lambda }=\mathbf{Ax}-\mathbf{b}=0$$

Substitute $\mathbf{x}$:

$$\mathbf{A}\left(-\frac{1}{2}{\mathbf{A}}^T\lambda \right)=\mathbf{b}\Rightarrow -\frac{1}{2}\mathbf{A}{\mathbf{A}}^T\lambda =\mathbf{b}\Rightarrow \lambda =-2(\mathbf{A}{\mathbf{A}}^T{)}^{-1}\mathbf{b}$$

Thus,

$$\mathbf{x}=({\mathbf{A}}^T(\mathbf{A}{\mathbf{A}}^T{)}^{-1})\mathbf{b}$$

(5)

To show the uniqueness of the matrix $\mathbf{P}\in {\mathbb{R}}^{n\times m}$ that satisfies the following four equations for arbitrary $m$, $n$, and $\mathbf{A}$:

$$\mathbf{APA}=\mathbf{A}$$ $$\mathbf{PAP}=\mathbf{P}$$ $$(\mathbf{AP}{)}^T=\mathbf{AP}$$ $$(\mathbf{PA}{)}^T=\mathbf{PA}$$

Assume there are two matrices $\mathbf{P}$ and $\mathbf{Q}$ that satisfy the above equations. Then, we have:

$$\mathbf{AP}=(\mathbf{AQA})\mathbf{P}=(\mathbf{AQ}{)}^T(\mathbf{AP}{)}^T={\mathbf{Q}}^T{\mathbf{A}}^T{\mathbf{P}}^T{\mathbf{A}}^T={\mathbf{Q}}^T(\mathbf{APA}{)}^T={\mathbf{Q}}^T{\mathbf{A}}^T=(\mathbf{AQ}{)}^T=\mathbf{AQ}$$

Similarly, we can show that $\mathbf{PA}=\mathbf{QA}$.

Then, we can obtain:

$$\mathbf{P}=\mathbf{PAP}=\mathbf{PAQ}=\mathbf{QAQ}=\mathbf{Q}$$

Therefore, the matrix $\mathbf{P}$ that satisfies the given equations is unique.

(6)

For the solution in (3), we have:

$$rank(A)=n$$ $$\mathbf{x}=({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T\mathbf{b}$$

This is indeed in the form $\mathbf{x}=\mathbf{Pb}$ where $\mathbf{P}=({\mathbf{A}}^T\mathbf{A}{)}^{-1}{\mathbf{A}}^T$, which is the Moore-Penrose pseudoinverse for the case when $\mathbf{A}$ has full column rank, i.e., $rank(\mathbf{A})=n$.

For the solution in (4), we have:

$$rank(A)=m$$ $$\mathbf{x}={\mathbf{A}}^T(\mathbf{A}{\mathbf{A}}^T{)}^{-1}\mathbf{b}$$

This is also in the form $\mathbf{x}=\mathbf{Pb}$ where $\mathbf{P}={\mathbf{A}}^T(\mathbf{A}{\mathbf{A}}^T{)}^{-1}$, which is the Moore-Penrose pseudoinverse for the case when $\mathbf{A}$ has full row rank, i.e., $rank(\mathbf{A})=m$.

Thus, both solutions can be represented as $\mathbf{x}=\mathbf{Pb}$, where $\mathbf{P}$ is the Moore-Penrose pseudoinverse of $\mathbf{A}$.

知识点

线性代数线性方程组矩阵秩最小二乘法拉格朗日乘数法广义逆矩阵

难点解题思路

1. 理解矩阵的秩与线性方程组解的关系（Rouché-Capelli 定理）
2. 掌握最小二乘法求解超定方程组
3. 使用拉格朗日乘数法求解欠定方程组的最小范数解
4. 理解 Moore-Penrose 广义逆矩阵的性质及其在求解线性方程组中的应用

解题技巧和信息

1. 矩阵秩：通过行变换和高斯消元法计算矩阵的秩，可以判断向量组的线性无关性。
2. 最小二乘解：当线性方程组无解时，可以通过最小化残差平方和来找到最优解，使用正规方程。
3. 拉格朗日乘子法：用于在约束条件下优化问题，通过构建拉格朗日函数并求导得到最优解。
4. Moore-Penrose 伪逆：用于求解一般矩阵方程的最优解，满足多个特定性质。

重点词汇

• Simultaneous linear equation 联立线性方程组
• Augmented Matrix - 增广矩阵
• Rank 秩
• Linearly independent 线性无关
• Gaussian elimination 高斯消元法
• Rouché-Capelli theorem Rouché-Capelli 定理
• Least squares solution 最小二乘解
• Normal equation 正规方程
• Lagrange multipliers 拉格朗日乘数
• Moore-Penrose pseudoinverse 摩尔-彭若斯广义逆
• Overdetermined system 超定系统
• Underdetermined system 欠定系统

参考资料

1. Linear Algebra and Its Applications by Gilbert Strang, Chapter 4 (Orthogonality) and Chapter 7 (Symmetric Matrices and Quadratic Forms)
2. Matrix Analysis by Roger A. Horn and Charles R. Johnson, Chapter 5 (Norms for Vectors and Matrices) and Chapter 6 (The Singular Value Decomposition and Its Applications)
3. Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III, Lecture 11 (Least Squares Problems) / Chap. 5
4. David C. Lay, “Linear Algebra and Its Applications”, Chap. 4