-

L11 Orthogonality

11.1 Normed vector spaces

Def 1: Normed vector space

$X$ is normed if there is a function $\vert\vert\cdot\vert\vert$, such that \(\begin{aligned} \|x\| &\geq 0 \\ \|x+y\| &\leq \|x\|+\|y\| \end{aligned}\)

Examples

1. When $X=\mathbb{R}^2$ \(\begin{aligned}\|x\|_1=\vert x_1\vert+\vert x_2\vert \\ \|x\|_2=\sqrt{x_1^2+x_2^2}\end{aligned}\)
2. When $X=\lbrace \text{all polynomials on }[0,1]\rbrace$ \(\begin{aligned}\|x\|_1&=\int_0^1 \vert x(t)\vert dt \\ \|x\|_2&=\sqrt{\int_0^1 x^2(t) dt}\end{aligned}\)

11.2 Euclidean norm in $\mathbb{R}^n$

Def 2: Euclidean norm

\(\begin{aligned} \|x\|&=(x\cdot x)^{1/2} \\[5pt] \|x\|^2&=x\cdot x=x^Tx=\sum x_i^2 \end{aligned}\)

11.3 Orthogonality in $\mathbb{R}^n$

Vector $x\perp y$ iff

1. $x\cdot y=0$
2. $\vert\vert x\vert\vert^2+\vert\vert y\vert\vert^2=\vert\vert x+y\vert\vert^2=\vert\vert x-y\vert\vert^2$

Def 3: Orthogonal subspaces

Let $S,T$ be subspaces in $\mathbb{R}^n$, $x\in \mathbb{R}^n$

1. $x\perp S$ if $x$ is orthogonal to any vector from $S$
2. $S\perp T$ if any from $S$ is orthogonal to any from $T$
3. Orthogonal complement $S^{\perp}=\lbrace x:x\perp S\rbrace$

Facts:

1. $T=S^\perp \iff S=T^\perp$
2. $(S^\perp)^\perp=S$

Theorem 1: For $A_{m\times n}$, \(N(A)^\perp=C(A^T)\)

Proof: It’s equal to show $N(A)=C(A^T)^\perp$

1. We know that if we can prove $a\to b, \neg a\to \neg b$, then we get $a=b$
2. For $x\in N(A)\to x\in C(A^T)^\perp$, correct
3. For $x\notin N(A)\to x\notin C(A^T)^\perp$, $x$ 不属于零空间就说明 $x$ 与 $A$ 的某一列相乘不得零

11.3 Projection of a vector onto a subspace in $\mathbb{R}^n$

Theorem 2: For any $S\subset\mathbb{R}^n$, any vector $b\in\mathbb{R}^n$ can be represent as $b=p+e$, where $p\in S,e\in S^\perp$

Def 4: Projection

Denote $p$ in theorem above is the projection of $x$ onto $S$, that \(p=P_Sb\)

Facts:

1. Projection is uniquely defined
2. $P_S$ is a linear transformation in $\mathbb{R}^n$
3. $P_S=P_S^2=P_S^n$
4. $I-P_S=P_{S^\perp}$

Proof: Since $e=P_{S^\perp}b$, plus that $(I-P_S)b=b-P_Sb=(p+e)-p=e$, therefore proven

11.4 Projection onto a span of given vectors

Theorem 3: Let $A=(a_1,…,a_n)\in\mathbb{R}^{m\times n},m>n$, then $A^TA$ is invertible

Proof: For $A^TAx=0\to x^TA^TAx=0\to |Ax|=0\to x=0$

Theorem 4: Let $S=\text{span}(a_1,…,a_n)$, then we have \(S=C(A)=\lbrace Ax,x\in\mathbb{R}^n\rbrace\)

Def 5: Pro jection matrix $P$

The projection $p$ of vector $b$ onto $S=C(A)$ is \(p=Pb,\text{where }P=A(A^TA)^{-1}A^T\)

Proof:

1. Since $C(A)=N(A^T)^\perp\to C(A^\perp=N(A^T)$, therefore $p\in C(A),e\in N(A^T)$
2. To find $P$, assume $\hat{x}$ that $A\hat{x}=p$, then we have $A\hat{x}-b=-e\in N(A^T)$
3. From 2, we get $A^T(A\hat{x}-b)=0$, then $\hat{x}=(A^TA)^{-1}A^Tb$
4. Finally, $p=A\hat{x}=A(A^TA)^{-1}A^Tb$

Corollary: $P_S^T=P_S$

L12

12.1 Least squares approximation

For a model \(b\approx a_1x_1+a_2x_2+...+a_nx_n\)

where $\lbrace a_i\rbrace$ are paramters and $\lbrace x_i\rbrace$ are variables

When $\lbrace x_i,b\rbrace$ are given, we want to estimate a set of $\lbrace a_i\rbrace$ to make $\sum a_ix_i$ close to $b$ as possible, that’s why we need LSA (least squares approximation)

Def 1: Fitting error $e_k$

\(e_k=b_k-\sum_{i=1}^na_{ki}x_i\)

Def 2: Quadratic criterion

\(\text{Minimize }e_1^2+...+e_n^2\text{ over }x_1,...,x_n\in\mathbb{R}\)

Example: Find a line $y=C+Dx$ that is closest to $(0,6),(1,0),(2,0)$ \(\begin{aligned} e_1&=6-(C+0) \\ e_2&=0-(C+D) \\ e_3&=0-(C+2D) \end{aligned}\)

then we get $f(C,D)=e_1^2+e_2^2+e_3^2$

After solveing $f’_C=0$ and $f’_D=0$, we get $C=5,D=-3$

12.2 Matrix reformulation

For $A_{m\times n}$, we can reformulate the probelm before into \(\text{Minimize }\|Ax-b\|\text{ over }x\in\mathbb{R}^n\)

From L11, it is obvious that the optimal solution $\hat{x}$ of the problem is $\hat{x}=(A^TA)^{-1}A^Tb$, which makes \(\|A\hat{x}-b\|=\|p-b\|=\|e\|\)

12.3 Alternative solution

Def 3: 矩阵求导

\(\begin{aligned} \frac{d}{dx}(Ax)&=A^T \\ \frac{d}{dx}(x^TA)&=A \\ \frac{d}{dx}(x^TAx)&=(A^T+A)x \end{aligned}\)

Since \(\min\|Ax-b\|\iff\min\|Ax-b\|^2\iff\min(Ax-b)^T(Ax-b)\)

therefore \(f(x)=(x^TA^T-b^T)(Ax-b)=x^TA^TAx-2x^TA^Tb+b^Tb\)

then from Def 3, we get \(\frac{df}{dx}=2x^TA^TA-2b^TA\)

finally from $\frac{df}{dx}=0$, we get $x=(A^TA)^{-1}A^Tb$, as in L12.2

12.4 Orthogonal and orthonormal matrices and bases

Def 4: Orthogonal matrix

A matrix $Q_{n\times n}$ is orthogonal if $Q^TQ=I$ or $Q^{-1}=Q^T$

Examples:

1. Permutation matrix
2. Rotation matrix

Def 5: Orthonormal vectors

1. A system of vectors $\lbrace q_i\rbrace$ is orthogonal if $q_i^Tq_j=0$ when $i\neq j$
2. A system of vectors $\lbrace q_i\rbrace$ is orthonormal if $q_i^Tq_j=0$ when $i\neq j$ and $\vert\vert q_i\vert\vert=1$

Corollary: Let matrix $A_{m\times n}=[a_1,…,a_n]$, if $\lbrace a_I\rbrace$ is orthonormal, then $A$ is orthogonal ($A^TA=I$)

12.5 Gram-Schmidt procedure

能够由一组相互独立的向量，生成一组相互正交的向量 Example: Generate orthogonal vectors $[A,B,C]$ from independent vectors $[a,b,c]$

1. $A=a$
2. $B=b-\frac{A^Tb}{A^TA}A$
3. $C=c-\frac{A^Tc}{A^TA}A-\frac{B^Tc}{B^TB}B$

12.6 QR-factorization and application to least squares

For matrix $A_{m\times n}$, we can use GS procedure in L12.5, to generate a matrix $Q$, in which $\lbrace q_i\rbrace$ are orthonormal vectors

then we get factorization $A=QR$

In least squares, we have \(\begin{aligned} A^TA\hat{x}=A^Tb&\to R^TQ^TQR\hat{x}=R^TQ^Tb \\ R^TR\hat{x}=R^TQ^Tb&\to \hat{x}=R^{-1}Q^Tb \end{aligned}\)

L13 Determinants

Facts

1. 不可逆矩阵的行列式等于 $0$
2. For a $2\times 2$ matrix $A$ \(\det(A)=|A|=\begin{vmatrix} a & b \\ c & d \end{vmatrix}=ad-bc\)

13.1 Definition of the determinant (Big formula)

Def 1: Permutation and $\text{sgn}(\pi)$

对数组 $(1, 2, …, n)$ 进行排列组合，共可以得到 $n!$ 个不同的数组 我们定义 $\text{sgn}(\pi’)$ 来表示 $\pi’$ 相较于 $\pi$ 变化的程度 \(\text{sgn}(\pi)=\begin{cases} 1 &\text{number of permutations is even} \\ -1 &\text{number of permutations is odd} \end{cases}\)

例如, $\text{sgn}([3, 2, 1])=-1,\text{sgn}([3, 1, 2])=1$

Def 2: Determinant

\(\det(A)=\sum_{\pi}\text{sgn}(\pi)a_{1\pi(1)}a_{2\pi(2)}...a_{n\pi(n)}\)

For $n=2$ we have $\pi_1=[1,2],\pi_2=[2,1], \text{sgn}(\pi_1)=1,\text{sgn}(\pi_2)=-1$, then \(\begin{aligned} \det(A)&=\text{sgn}(\pi_1)a_{1\pi_1(1)}a_{2\pi_1(2)}+\text{sgn}(\pi_2)a_{1\pi_2(1)}a_{2\pi_2(2)} \\ &=1\cdot a_{11}a_{22}+(-1)\cdot a_{12}a_{21} \\ &=ad-bc \end{aligned}\)

Fact

• Let a permutation matrix $P$ transfers matrix $A$ consisting of rows $a_1, …, a_n$, into matrix $PA$ with rows ordered as $a_{\pi(1)}, …., a_{\pi(n)}$, then \(\det(P) = \text{sgn}(P)\)

13.2 Laplace formula for determinant

这里要用到在 L14.1 中定义的 Minor and Cofactor

Def 3: Laplace formula

\(\det(A)=\sum_{j=1}^n a_{ij}C_{ij}\)

Example: When we choose $i=1$

13.3 Properties of determinants

Basic properties of determinant

1. For triangular matrix $A_{n\times n}$, $\det(A)=a_{11}a_{22}…a_{nn}$
2. $\det(AB)=\det(A)\det(B)$
3. $\det(A^{-1})=(\det(A))^{-1}$
4. $\det(A^T)=\det(A)$

2, 3, 4 这三点从矩阵行列式的几何属性的角度非常好理解，详见 Math415 Week-02 Appendix

Properties related to matrix transformations

1. 对矩阵的任意一行、列乘上 $c$，那么其行列式也会变成原先的 $c$ 倍
2. 每做一次行、列交换，其行列式就需要变一次号
3. 对矩阵进行的高斯消元不改变其行列式的值
4. 对任意一行的操作可以这样分开 \(\begin{vmatrix} a + a' & b + b' \\ c & d \end{vmatrix}=\begin{vmatrix} a & b \\ c & d \end{vmatrix}+\begin{vmatrix} a' & b' \\ c & d \end{vmatrix}\)

$\det(A)=0\iff A$ is singular

具体表现例如：

1. $A$ 的任意一行、一列的所有元素均为 $0$
2. $A$ 有两个一样的行或两个一样的列
3. $A$ 行或列线性相关, linearly dependent

至于证明当 $A$ 可逆时 $\det(A)\neq 0$，可以由 $PA=LU$ 得到 ($\det(P), \det(L), \det(U)$ 均不为 $0$)

13.4 Pivot formula for determinant

Theorem 1: If $A=LU$, then $\det(A)=\det(U)=u_{11}…u_{nn}$

Theorem 2: If $PA=LU$, then $\det(A)=\det(U)/\det(P)=\pm u_{11}…u_{nn}$

L14

14.1 Representation of $A^{-1}$ via cofactors

\(A^{-1}=\frac{1}{|A|}C^{T},C=\lbrace C_{ij}\rbrace ^n_{i,j=1}\)

具体证明在 Def 3 之后

Def 1: Minor 余子式

将 $A_{i,j}$ 的余子式记做 $M_{i,j}$，等于是将第 $i$ 行第 $j$ 列去掉后剩下矩阵的行列式。 例如下图中 $M_{1,1}=5\times9-6\times8=-3$

进一步可得矩阵 $M_A$

Def 2: Cofactor

\(C_{i,j}=(-1)^{i+j}M_{i,j}\)

承接上边的例子，可得 $C$

Def 3: Adjugate Matrix 伴随矩阵

\(adj(A)=C^T \to A^{-1}=\frac{1}{|A|}adj(A)=\frac{1}{|A|}C^T\)

• Proof 以三阶矩阵为例 \(AC^T=\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\begin{bmatrix} c_{11} & c_{21} & c_{31} \\ c_{12} & c_{22} & c_{32} \\ c_{13} & c_{23} & c_{33} \end{bmatrix}\)

1. 先看对角线部分， \([a_{11}, a_{12}, a_{13}] \begin{bmatrix} c_{11} \\ c_{12} \\ c_{13} \end{bmatrix}=\det(A)\)
2. 再看非对角线部分，例如 \([a_{21}, a_{22}, a_{23}] \begin{bmatrix} c_{11} \\ c_{12} \\ c_{13} \end{bmatrix}\) 由于这三个 $c_{1j}$ 为矩阵 $A$ 第二行和第三行的行列式，而 $a_{2j}$ 恰为原矩阵第二行，因此非对角线部分的乘积式就相当于一个两行相同的矩阵的行列式，因此这个式子等于 $0$
3. 由此可得 $AC^T=\vert A\vert$，得证

14.2 Cramer’s rule

Consider equation $Ax=b$ for invertible $A\in\mathbb{E}^{n\times n}$ \(x=A^{-1}b=\frac{1}{|A|}\beta\)

where, $\beta=C^Tb$

剩下的本课件中有关矩阵特征根、特征值以及特征分解等部分，会结合书本呈现在 Chapter-6.md 中

L15

Similar matrices and Jordan forms

15.1 Similarity

Def 1: Similarity

$A$ is similar to $B$ if for some invertible $Q$
\(A=QBQ^{-1}\) Similar matrices share the following same:

• Sets of eigenvalues
• Dimension of null and column spaces
• ranks
• trace and determinent
• Jordan forms

DO NOT share the same Eigensapces and 四个子空间

Theorem 1.1: Similarity is an equivalence relation: \(\begin{aligned} A\sim B&\to B\sim A \\ A\sim B, B\sim C&\to A\sim C\end{aligned}\)

Theorem 1.2: Similar matrices have the same characteristic polynomials (特征多项式)

• Lemma: $A\sim B\to A-\lambda I\sim B-\lambda I$ $\small{ QAQ^{-1}=B\to Q(A-\lambda I)Q^{-1}=QAQ^{-1}-\lambda QQ^{-1}=B-\lambda I }$

then it’s easy to get $\vert A-\lambda I\vert=\vert B-\lambda I\vert$

Def 2: Algebraic multiplicity 代数重数

Algebraic multiplicity of eigenvalue $\lambda$ of $A$ is $d$, where \(\delta_A(\lambda)=\prod(\lambda-\lambda_k)^d\)

Def 3: Geometric multiplicity 几何重数

Algebraic multiplicity of eigenvalue $\lambda$ of $A$ is $\dim(N(A-\lambda I))$

例如，对于 $A=I_n$，$\lambda=1$ 的几何重数等于 $n$

15.2 Jordan form and Spectrum

Def 4: Jordan form

Any $A$ is similar to a specific matrix $J$ \(J=\begin{bmatrix} J_1 & 0 & ... & 0 \\ 0 & J_2 & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... & J_s \end{bmatrix}\)

where \(J_i=\begin{bmatrix} \lambda_k & 1 & 0 \\ 0 & \lambda_k & 1 \\ 0 & 0 & \lambda_k \end{bmatrix}\)

$J_i$ 被称作 Jordan block，是一个以特征值为对角线、对角线元素的上一个元素等于 $1$、其他元素均为 $0$ 的矩阵 (注意：这里的 $J_i$ 并不对应 $\lambda_i$，例如下面这个矩阵有两个 $J_i$ 但只有一个 $\lambda_k$) \(J=\begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{bmatrix}\)

Theorem 4.1: 由 Jordan form 表示重数

1. $\lambda_k$ 的代数重数，是 $J$ 中以 $\lambda_k$ 为主对角线元素的各 Jordan 子块的阶数之和
2. $\lambda_k$ 的几何重数，是 $J$ 中以 $\lambda_k$ 为主对角线元素的各 Jordan 子块的个数

Corallary 4.1: Two matrices are similar if and only if they have the same Jordan form (up to permutation of Jordan blocks)

Corollary 4.2: $\text{rank}(A)$ = number of nonzero eigenvalues

• Proof: $A\sim J\to \text{rank}(A)=\text{rank}(J)$，而 $J$ 由于近乎于一个对角矩阵，因此 $J$ 的秩取决于其非零对角线元素的个数

Corollary 4.3: If $A\in\mathbb{C}^{n\times n}$ has eigenvalues $\lambda_1,…,\lambda_n$, then $p(A)$ has eigenvalues $p(\lambda_1),…,p(\lambda_n)$ for any polynomial $p$.

• Proof:
  1. $A=QJQ^{-1}\to A^2=QJ^2Q^{-1}=…$
  2. Then from $p(A)=\sum c_kA^k$, we can get $p(A)=\sum c_kJ^k$
  3. Since $p(J)$ has eigenvalues $p(\lambda_1),…,p(\lambda_n)$, same for $p(A)$

Def 5: Spectrum 矩阵的谱

矩阵的谱又叫矩阵的谱半径，定义为 \(\rho(A)=\max|\lambda_i|\)

即特征值模的最大值

Corollary 5.1: 具有相同谱的矩阵不一定相似

例如对于矩阵 \(A=\left[\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix}\right],B=\left[\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix}\right]\) 它们具有相同的谱（特征根均为 $2$），但是 $A$ 的几何重数为 $2$，$B$ 为 $1$，也意味着 $A$ 有两个特征根而 $B$ 只有一个。因此 $A,B$ 不相似

Ex 1: If knowing \(A=\left[\begin{matrix} 0 & -1\\ 1 & 0 \end{matrix}\right]\) $B=A^{10}-3A+1$, find the spectrum of $B$

from $A$, we can solve $\lambda_A=\pm i$, then $\lambda_B=\lambda_A^{10}-3\lambda_A+1$, 从而易得 spectrum of $B$

Ex 2: Is it true that matrices with the same spectrum are similar? \(\text{No.} \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix},\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\text{ has same spectrum but not similar}\)