======Matrix Algebra for Engineers======
//Week 3 Notes//
----
====Vector Spaces====
===Definiation===
**向量空间** //Vector space// 由一系列的向量（//Vector//）和一系列的标量（//Scalar//）组成。向量空间必须是**封闭的**（//closed//），也就是，通过缩放向量（//scalar multiplication//），相加向量（//vector addition//），得到的向量最终也属于该向量空间。比如在一个 $3 \times 1$ 的向量空间中，选取任意一个向量与任意标量相乘，然后再加到任意另外一个向量上，得到的结果必定是一个 $3 \times 1$ 的向量。
===Linear Independence===
//Linear Independence// 的正式定义如下：
>Let $\{v_0,..., v_{n−1}\} ⊂ \mathbb{R}^m$. Then this set of vectors is said to be **linearly independent** if $χ_0v_0 + χ_1v_1 + ··· +χ_{n−1}v_{n−1} = 0$ implies that $χ_0 = ··· = χ_{n−1} = 0$.
==Linear Independence 的含义==
上面的定义实际上讨论的问题是，向量空间中，是否至少存在一个向量，**可以用其他的向量来表示**。而 //Linear Independence// 意味着所有的向量都**无法**用任何其他向量来表示。换句话说，只有在所有向量的系数都为 $0$ 的情况下，向量的和才能为 $0$。如果有可以互相表示的向量，他们就可以通过更改自身的系数来进行相互抵消。
==判断 Linear Independence==
判断 //Linear Independence// 可以通过 //RREF// 来进行判断：
- 首先将向量空间中的向量组成矩阵
- 求该矩阵的 //RREF//
- 如果 //RREF// 是 //Indentiy Matrix//，那么该组向量是线性无关的。
下面的向量空间就是线性无关的：
$$
\left (\begin{pmatrix}
3\\
3\\
2
\end{pmatrix}
\begin{pmatrix}
2\\
1\\
1
\end{pmatrix}
\begin{pmatrix}
1\\
2\\
0
\end{pmatrix}
\right )
\Rightarrow
\begin{pmatrix}
3& 2& 1\\
3& 1& 2\\
2& 1&0
\end{pmatrix}
\Rightarrow
\begin{pmatrix}
1& 0& 0\\
0& 1&0 \\
0& 0 &1
\end{pmatrix}
$$
===Span, Basis and Dimension===
* **Span**（张成空间），指基于给定的向量空间中的几个向量所能**生成**的向量空间
* **Basis**：该向量空间仅由 //Basis// 即可张成（即任意向量空间中任意向量都可以由 //Basis// 得到）。//Basis// set 中的向量必须是**线性无关**的。
* **Dimension**：向量空间中的 //Basis// 的数量（唯一）
常见习题的解法：
* **//什么样的向量组不是向量空间？//**
只需要验证该向量空间是否封闭即可。通常情况下，如果需要适应加法和乘法，那么命题中存在的关系大概率是**相对**关系，而不是**绝对**关系。比如 “向量的第一个分量和第三个分量之和等于 1” 此类的绝对关系，经过缩放后是基本不可能得到与原来向量有相同规则的向量的 (0 可以，缩放无效)。
* **//如何查看一组向量是否线性无关？//**
可以先进行观察是否存在加法 / 乘法的关系。如果不确定，可以写出 RRef 形式，看是否是单位矩阵。
* **//如何求某个向量空间中的 orthonomal basis?//**
这个问题需要分成两步：
* 首先要求出适合条件的 //orthagonal basis// 。
这一步中，我们首先可以随机找一个满足条件的向量；比如所有向量分量和为 0 的向量组，可以选一个：
$$
\begin{pmatrix}
1\\
-1\\
0
\end{pmatrix}
$$
根据这个向量，由 //orthagonal// 的定义，可知其对应向量与其点积为 0；可以求出如下向量：
$$
\begin{pmatrix}
1\\
1\\
-2
\end{pmatrix}
$$
* 其次再对其进行 normalize，也就是对每个分量除以其范数即可。以第二个向量为例，其范数在这里等于 $\sqrt{1^2 + 1^2 + (-2)^2} = \sqrt{6}$，因此标准化后的向量为：
$$
\frac{1}{\sqrt{6}}
\begin{pmatrix}
1\\
1\\
-2
\end{pmatrix}
$$
====Gram-Schmidt process====
//Gram-Schmidt process// 是一种通用的，将非 orthonormal basis 转换为 orthonormal basis 的算法。其主要的步骤分两步：
- 以源 basis 所在向量空间中的某一个 basis 作为基准，构造与其垂直的向量
- 将该向量进行 Normalize，则可得到对应的 orthonormal basis。
===orthogonal basis 的构造===
{{ :math:linear_algebra:matrix_engineers:gs_process_2.svg?400 |}}
如上图，假设初始两个 basis 为 $V_1$ 和 $V_2$：
==选择新的 basis==
首先选择其中一个 basis 作为 orthonormal basis 的基准，这里选择 $V_1$，令新 basis $u_1 = V_1$
==基于选择的 basis 构造 orthagonal basis(geometrically)==
确定了新的基准 basis 后，需要求出与其垂直的向量的表达式。通过观察发现，如果做 $V_2$ 到 $u_1$ 上的投影，那么垂直方向上的向量 $u_2$ 是与 $u_1$ 垂直的。
\\ \\
令 $V_2$ 在 $u_1$ 上的投影向量为 $s_1$，根据向量的加减法，可得：
$$
u_2 = V_2 - s_1
$$
由于 $s_1$ 是 $V_2$ 在 $V_1$ 上的投影向量，因此可以写成：
$$
ks_1 = u_1
$$
因此，只需求出标量（//magnitude//） $k$，即可得到 $s_1$。因为 $u_2$ 与 $u_1$ 正交，因此 $u_2 \cdot u_1 = 0$。将 $u_2 = V_2 - s_1$ 带入该式，有：
\[
\begin{align*}
&(V_2 - u_1) \cdot u_1 = 0 \\
\Rightarrow & (V_2 - ks_1) \cdot u_1 = 0 \\
\Rightarrow & V_2 \cdot u_1 - ku_1\cdot u_1 = 0 \\
\Rightarrow & k = \frac{V_2 \cdot u_1}{u_1 \cdot u_1}
\end{align*}
\]
带入之前的 $u_2$ 表达式，最终可以得到 $u_2$ 如下：
>$$u_2 = V_2 - \frac{(V_2 \cdot u_1)u_1}{u_1 \cdot u_1} $$
==从代数上进行验证==
代数上，点积一般表达为行向量与列向量的相乘形式。因此，上面的公式可以将点积部分进行改写（因为得到的都是常数，因此书写方式不影响结果）
>$$u_2 = V_2 - \frac{(u_1^T \cdot V_2)u_1}{u_1^T \cdot u_1} $$
在代数上，如果 $u_1$ 与 $u_2$ 正交，那么有：
$$
u_1^T \cdot u_2 = 0
$$
根据该性质，我们对本节第一个公式的两边同时乘以 $u_1^T$，有：
\[
\begin{align*}
u_1^Tu_2 & = u_1^TV_2 - \frac{u_1^T(u_1^T \cdot V_2)u_1}{u_1^T \cdot u_1} \\
&=u_1^TV_2 - \frac{(u_1^T \cdot V_2)(u_1^Tu_1)}{u_1^T \cdot u_1} \\
&=u_1^TV_2 - u_1^TV_2 \\
& = 0
\end{align*}
\]
因此，这样的 $u_2$ 表达式可以确保 $u_1$ 和 $u_2$ 是 orthagonal basis。
==多维度上的扩展==
求 orthagonal basis 在多维度的向量上的操作也是相同的；我们只需要将向量按二维空间进行拆分讨论即可。比如处于 $x,y,z$ 的三维向量，如果以 $x$ 为基准求一个新的 orthagonal basis，那么只要分别求 $x,y$ 与 $x,z$ 平面中的 orthagonal basis 即可；也就是就是已知 $u_1$，分别用 $u_1$ 表示 $u_2$ 和 $u_3$。从计算上来看，就是使用基准向量分别减去不同的 $s_1$，即：
\\ \\
{{ :math:linear_algebra:matrix_engineers:1702258856138.jpg?200 |}}
\\ \\
\[
\begin{align*}
u_3 & = V_3 - \frac{(u_1^T \cdot V_3)u_1}{u_1^T \cdot u_1} - \frac{(u_2^T \cdot V_3)u_2}{u_2^T \cdot u_2} \\
\end{align*}
\]
==normalize==
标准化向量的过程套用 norm 公式即可：
$$
u_n = \frac{u_n}{\sqrt{u_n^Tu_n}}
$$
====Fundamental Subspaces of a Matrix====
===Null Space===
矩阵 $A$ 的//Null Space// 指对于矩阵 $A$，满足 $Ax = 0$ 的所有 $x$ 组成的向量空间。//Null Space// 中的向量同样是初等变换下封闭的，即其内部的向量通过乘法和加法得到的向量也在 //Null Space// 中。
==Null Space 的求解过程==
求 //Null Space//，只需要知道它的 basis 就可以了。从代数上来上，我们可以从 $Ax = 0$ 的非特殊解入手（也就是 //free variable//，即取什么值都不会影响 $Ax=0$ 的那一部分未知数）
* 将 $A$ 转化为 //RREF//
* 根据 //RREF// 的结果，找出 $Ax = 0$ 的非特殊解与特殊解（也就是我们说的 //basic variable//)之间的关系。通常，//pivot// 所在位置的未知数是特殊解。因此：
* 找到 //pivot//
* 由 $Ax = 0$，可知 $A$ 中任意一行与 $x$ 的点乘结果均为 0。利用该关系，列出 //basic variable// 与 //free variable// 的关系。
* 按该关系，最终得到的，以 //free variable// 表示的 $x$，其对应的向量即为 //Null space// 的 basis。
==Null Space 的求解例子==
假设有如下矩阵 $A$，其 //Rref// 形式为：
\\
\[
A=
\begin{pmatrix}
1& 1& 1& 0\\
1& 1& 0& 1\\
1& 0& 1& 1
\end{pmatrix}
\Rightarrow
Rref(A)=
\begin{pmatrix}
1& 1& 1& 2\\
0& 1& 0& -1\\
0& 0& 1& -1
\end{pmatrix}
\]
根据 $Ax = 0$ 列式。要使乘法有意义，可知 $x$ 是一个 $4 \times 1$ 的向量。设其分量为 $x_1,x_2,x_3,x_4$，有：
\\
\[
\begin{pmatrix}
1& 0& 0& 2\\
0& 1& 0& -1\\
0& 0& 1& -1
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3\\
x_4
\end{pmatrix}=0
\]
观察 //Rref(A)// 的 //pviot//，发现 $x_4$ 是唯一的 //free variable//。因此，根据 $Ax = 0$，将 $x_1,x_2,x_3$ 用 $x_4$ 表示：
\\
\[
\begin{cases}
& x_1 + 2x_4 &= 0\\
& x_2 - x_4 &=0\\
& x_3 - x_4 &=0
\end{cases}
\Rightarrow
\begin{cases}
& x_1 = -2x_4\\
& x_2 = x_4 \\
& x_3 = x_4
\end{cases}
\]
最后根据上面的关系，将向量 $x$ 以 $x_4$ 表示：
\\
\[
x=
\begin{pmatrix}
-2x_4\\
x_4\\
x_4\\
x_4
\end{pmatrix}
=
x_4
\begin{pmatrix}
-2\\
1\\
1\\
1
\end{pmatrix}
\]
此时求得的向量即为需要求得 basis。也就是说，$A$ 的 //Null space// 是由上述向量张成的向量空间。
===Null Space 的应用===
//Null Space// 的一个重要应用是求解 //underdetermined system//。我们知道，在一个 system 中，如果关系（row）少于未知数（column），那么这个系统就是 //underdetermened// 的。换句话说，该系统没有特殊解，只有一系列的通用解。
\\ \\
那么 //Null space// 在里面起到什么样的作用呢？先说结论：
>//let $u$ be a general vector in $Null(A)$, let $v$ be any vector that solves $Ax = b$, then//
>$$
x = u + v
$$
>//is the gerneral solution to $Ax = b$//
==x = u + v推导过程==
假设 $x = u + v$，那么：
$$
Ax = A(u+v) = Au + Av
$$
因为 $u$ 属于 $Null(A)$，因此 $Au= 0$。那么：
$$
Ax = Av = b
$$
到此得证。
==实例求解过程==
以下面的 augument matrix 为例。为了求 $x$，我们需要分开求 $u$ 和 $v$。对于 $u$，过程与之前求 basis 的过程一致.先求出其 //Rref//：
\\
\[
\left ( \begin{array}{cccc|c}
-3& 6& -1& 1&-7 \\
1& -2& 2& 3&-1 \\
2& -4& 5& 9&-4
\end{array}
\right )
\Rightarrow
\left ( \begin{array}{cccc|c}
1& -2& 0& -1&-3 \\
0& 0& 1& 2&-2 \\
0& 0& 0& 0&0
\end{array}
\right )
\]
根据 //Rref// 可以求出 //u//。注意，//u// 只需要各个变量之间的关系，因此用不到增广矩阵最后一列：
\\
\[
\begin{pmatrix}
2u_2+u_4\\
u_2\\
-2u_4\\
u_4
\end{pmatrix}
=
u_2\begin{pmatrix}
2\\
1\\
0\\
0
\end{pmatrix}
+
u_4
\begin{pmatrix}
1 \\
0\\
-2\\
1
\end{pmatrix}
\]
之后我们再来求 $v$。与求 $u$ 不同，$v$ 是一定程度上的特殊解，也就是能确定下来的变量都需要确定下来。因此，需要代入增广矩阵的结果部分：
\\
\[
\begin{cases}
v_1-2v_2-v_4&=3 \\
v_3+2v_4&=-2
\end{cases}
\]
由于 $v_2$ 和 $v_4$ 是 //free variable//，因此可以取任何值。我们在这里取 $0$，根据上面的等式即可算出 $v_1$ 和 $v_3$，有：
\\
\[
v=\begin{pmatrix}
3\\
0\\
-2\\
0
\end{pmatrix}
\]
到此，整个结果可以写为：
\\
\[
x=a
\begin{pmatrix}
2\\
1\\
0\\
0
\end{pmatrix}
+b
\begin{pmatrix}
1\\
0\\
-2\\
1
\end{pmatrix}
+\begin{pmatrix}
3\\
0\\
-2\\
0
\end{pmatrix}
\]
其中 $a$，$b$ 代表了 $u_2$, $u_4$ 的解，为任意值。
===Column Space===
//Colmun Space// 是一种将 $Ax$ 以列向量表达出来的方式，比如下面的例子：
\\ \\
{{ :math:linear_algebra:matrix_engineers:column_space.svg?400 |}}
\\
通过这样的整理，不难发现矩阵与列向量的乘法，实际上是矩阵中**各列的线性组合**。通过矩阵 $A$ 各列张成的空间，我们称为矩阵 $A$ 的 //colmun space// ，记作 $C(A)$
==计算 Column Space==
虽然 //Column Space// 由 $A$ 中列向量张成，但有时 $A$ 中的各个向量并不是 linear independent 的。因此，//Column Space// 的结果需要用 //basis// 和**维度**来体现。我们通过如下两步来进行：
- 计算 $A$ 的 //Rref//
- $Rref(A)$ 中拥有 //pivot point// 的列都是线性无关的。因此其对应的 $A$ 中的列，则是张成 //Column space// 的 basis
比如下面的例子：
\\
\[
\begin{pmatrix}
1& 1& 1& 0\\
1& 1& 0& 1\\
1& 0& 1&1
\end{pmatrix}
\Rightarrow
Rref(A)
\begin{pmatrix}
1& 0& 0& 2\\
0& 1& 0& -1\\
0& 0& 1&-1
\end{pmatrix}
\]
\\
将得到的 $Rref(A)$ 对应回 $A$，即可得到张成 $A$ 的 basis：
\\
\\
{{ :math:linear_algebra:matrix_engineers:cal_col_space.svg?200 |}} \\
因此，可知 ：
\[
C(A)=span
\left \{ \begin{pmatrix}
1\\
1\\
1
\end{pmatrix}
\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
\begin{pmatrix}
1\\
0\\
1
\end{pmatrix}
\right \} \]
其空间的维度为 $3$。
===Row Space, Left Null Space and Rank===
==Row space==
与 //column space// 类似，//row space// 是以矩阵 $A$ 中的行向量进行线性组合而张成的空间。因为线性组合以列向量为标准，因此 //row space// 可以被视作矩阵 $A$ 的转置矩阵的 //column space//，记作 $Col(A^T)$
==Left Null Space==
//Left null space// 的概念延伸自 //null space//，指将向量 $x$ 至于 矩阵 $A$ 左边，产生的线性组合结果为 $0$ 的向量所张成的空间，也就是满足 $x^TA = 0$。该等式也可以视作 $x$ 与 $A$ 的转置的相乘，即 $xA^T=0$
==Rank==
* 无论是 //row space// 还是 //column space//，他们的维度是不变的。我们将该维度大小称为矩阵的 //rank//。
* //rank// 同样可以被视作矩阵中线性无关向量（列）的数量。
===Subspaces 的关联性===
假设 $A$ 为 $m \times b$ 的矩阵：
* //null space// 为 $n \times 1$ 的向量空间的 //sub space//，因为 //null space// 是由 $n \times 1$ 的向量 $x$ 进行线性组合得到的。
* //column space// 为 $m \times 1$ 的向量空间的 //sub space//，因为其由 $A$ 中列向量线性组合得到。
* //row space// 为 $n \times 1$ 的向量空间的 //sub space//。将 //row space// 考虑为 $Col(A^T)$ 即可。
* //left null space// 为 $m \times 1$ 的向量空间的 //sub space//，将 //left null space// 考虑为 $A^Tx$ 的 //null space// 即可
==Orthagonal Complements==
//Null space// 与 //Row space// 被称为 //Orthagonal Complements//，因为:
* //null space// 的维度等于 //Non-pivot column// 的数量，//row space// 的维度等于 //pivot column// 的数量，这两者的维度之和等于 $A$ 中列向量的总数
* 任意 //row space// 中向量与 //null space// 中向量**垂直**。因为 $Ax = 0$，因此 $A$ 中每个行向量与对应 $x$ 向量的点积必然为 0.
* 同时满足以上两个条件的两个向量空间，被称为 //Orthagonal Complements//。同理可以推断出 //left null space// 与 //column space// 也互为 //Orthagonal Complements//。
====Orthogonal Projections====
===Orthogonal Projections===
//Orthogonal Projection// 指将一个在较大的向量空间中的向量，投影到该向量空间的某个 sub space 中的操作。具体来讲，假设我们有：
* $n$ 维的向量空间 $V$
* $p$ 维的向量空间 $W$，$W$ 为 $V$ 的 sub space
* $W$ 的 orthonormal basis ${s_1,s_2,..s_p}$
* $v$ 为 $V$ 中的一个向量
那么 //Orthogonal Projection// 可以被定义为：
>$$
v_{proj_w} = (v^Ts_1)s_1 + (v^Ts_2)s_2+....(v^Ts_p)s_p
$$
==扩展视角==
如果将 orthonormal basis 扩展到基于 $V$，而不是 $W$。假设该 Basis 为：${s_1,s_2,..s_p, t_1, t_2, ...t_{n-p}}$，$t$ 为 $V$ 中额外的 basis。因为 $V$ 为 $n$ 维，因此 $t$ 的总数为 $n-p$。同样设 $v$ 为 $V$ 中向量，那么 $v$ 可以表示为：
$$
v = a_1s_1 + a_2s_2... + a_ps_p + b_1t_1+b_2t_2...+b_{n-p}t_{n-p}
$$
其中 $a$ 和 $b$ 为标量。
\\ \\
如果将上面的 $v$ 带入到之前的公式中，那么可以发现，只要 $v$ 中与当前分量不同的项，都会被取消掉。比如 $(v^Ts_1)s_1$，只有在 $v$ 分量为 $a_1s_1$ 时，才会有乘积的结果不为 0。该结果为 $a_1s_1^Ts_1 = a_1$。因为 $s_1$ 与其他项的向量同属一个 orthnormal basis 中，因此只要不是与自身相乘的项均为 $0$，也就是：
$$
(v^Ts_1)s_1 = a_1s_1
$$
那么 $v$ Orthogonal Projection 就可以写成：
$$
v_{proj_w} = a_1s_1+a_2s_2...+a_ps_p
$$
这与之前的公式是等价的。
推论：$v_{proj_w}$ is the **CLOSEST** vector to the $v$
===The Least-squares problem===
统计学里面有一个经典的问题：//The least-sqares problem//（linear）。该问题描述的是：给定的一系列点，是否能找到一条直线，使得所有的点到直线距离的平方之和最小？
\\ \\
{{ :math:linear_algebra:matrix_engineers:linear_least_squares.svg?150 |}}
\\ \\
这个问题实际上可以转换为线性代数的问题。以上图为例，假设图中点有 $n$ 个，都是我们的 data。令每一个点的坐标为：
$$
(x_1, y_1), (x_2, y_2)...(x_n,y_n)
$$
假设蓝色直接代表了所有 $x,y$ 的关系，可以设该直线的方程为：
$$
\beta_0 + \beta_1x = y
$$
其中 $\beta_0$ 为直线与 $y$ 轴的交点，$\beta_1$ 为斜率。现在将所有的点都带入方程，可得：
\[
\begin{align*}
y_1=& \beta_0 +\beta_1x_1 \\
y_2=& \beta_0 +\beta_1x_2 \\
...\\
y_n=& \beta_0 +\beta_1x_n&
\end{align*}
\]
很明显，这是一个 linear system。在这个 Linear system 中，$x$, $y$ 都是已知的，而 $\beta_0, \beta_1$ 是未知的。因此可以做下面的变型：
\\ \\
{{ :math:linear_algebra:matrix_engineers:least_problem_axb.svg?200 |}}
\\ \\
则整个问题就转化为了 $Ax=b$ 的问题。
\\ \\
不过，在上述描述的关系中，未知数只有 2 个 $\beta_0, \beta_1$，但相关的等式有 $n$ 个。这种情况被称为 //over determined//；这种情况下，$\beta_0, \beta_1$ 显然是没有解的。
\\ \\
因此，我们退而求次，希望找一条 “最适合” 的直线来表示所有 $x,y$ 的关系。由于 $Ax$ 的结果必定处于 $A$ 的 column space 中（colmun space 代表 $Ax$ 中的列项量的线性组合，也就是所有可能的解，显然 $b$ 不处于该列空间中），因此，我们将 $b$ （也就是所有 $y$ 组成的向量）投射到 $A$ 的列空间中。根据我们之前根据 //Orthogonal Projection// 得出的结论，具体的来说，我们应该将 $b$ 投射到 $b_{proj_{col(A)}}$上（该向量与被投射的向量最近，因此得到的误差最小），也就是求下面的解：
$$
Ax = b_{proj_{col(A)}}
$$
==Normal Equation==
为了求解上述的等式，我们需要对 $Ax=b$ 做一些变形。如果我们将 $b$ 分解为在 $col(A)$ 上的投影 $b_{proj_{col(A)}}$，和另外一个分量，也就是：
\[
\begin{align}
Ax & = b_{proj_{col(A)}} + b -b_{proj_{col(A)}}
\end{align}
\]
由于 $b_{proj_{col(A)}}$ 是在 $col(A)$ 的投影，那么 $ b -b_{proj_{col(A)}}$ 显然垂直于 $col(A)$。而通过基础空间之间的关系可知，$col(A) =row(A^T)$。而 row space 恰好又与对应的 null space 互相垂直（互为 Orthagonal completement），因此：
* $ b -b_{proj_{col(A)}}$ 与 $col(A)$ 垂直，因此与 $row(A^T)$ 垂直
* 也就是说， $b -b_{proj_{col(A)}}$ 属于 $null(A^T)$
现在我们对 $Ax=b$ 的两边同时乘以 $A^T$。由于 $A^Tb_{proj_{col(A)}}$ 属于 $null(A^T)$，因此该分量与 $A^T$ 的乘积为 $0$。由此可以得到以下的推论：
\\ \\
\[
\begin{align*}
A^TAx & = A^Tb_{proj_{col(A)}} + A^T(b -b_{proj_{col(A)}})\\
&=A^Tb_{proj_{col(A)}}
\end{align*}
\]
记作：
>$$
A^TAx=A^Tb
$$
这个公式被称为 //Normal Equation//，是计算 Best fit line 的重要手段。
==Projection matrix==
当 $col(A)$ 中的向量是线性无关的时候，$A^TA$ 的结果是一个方阵，是可逆的。因此，对 //Normal Equation// 可以做出进一步的变形：
\\
\[
\begin{align*}
&A^TAx = A^Tb \\
\Rightarrow &x = (A^TA)^{-1}A^Tb \\
\Rightarrow &Ax = {\color{Red} A(A^TA)^{-1}A^T} b = b_{proj_{Col(A)}}
\end{align*}
\]
标红的部分被称为 //Projection matrix//。该矩阵将 $b$ 投影到 $Col(A)$ 上。
==利用 normal equation 计算 best fit line==
//假设有数据点：$(1,1), (2,3),(3,2)$，求过这几点的 best fit line。//\\ \\
首先，根据数据点，以 $y = \beta_0 + \beta_1x$ 为模板，建立 linear system。通过 linear system 确定 $A$：
\[
\begin{pmatrix}
1&1 \\
1& 2\\
1&3
\end{pmatrix}
\begin{pmatrix}
\beta_0\\
\beta_1
\end{pmatrix}
=
\begin{pmatrix}
1\\
3\\
2
\end{pmatrix}
\]
将 $A$ 带入 normal equation：
\[
\begin{pmatrix*}
1& 1& 1\\
1& 2&3
\end{pmatrix*}
\begin{pmatrix*}
1&1 \\
1& 2\\
1&3
\end{pmatrix*}
\begin{pmatrix*}
\beta_0\\
\beta_1
\end{pmatrix*}
=
\begin{pmatrix*}
1& 1& 1\\
1& 2&3
\end{pmatrix*}
\begin{pmatrix*}
1\\
3\\
2
\end{pmatrix*}
\]
\\
计算后得到关于 $\beta_0$ 和 $\beta_1$ 的 linear system。此时的未知数与等式数量相同，因此可以求解：
\\
\[
\begin{pmatrix*}
3 &6 \\
6 &14
\end{pmatrix*}
\begin{pmatrix*}
\beta_0\\
\beta_1
\end{pmatrix*}
=
\begin{pmatrix*}
6\\
13
\end{pmatrix*}
\]
\\ 解得 $\beta_0 = 1$，$\beta_1 = 1/2$，因此得到的直线方程为 $y = 1 + 1/2 * x$