第十七讲：正交矩阵和Gram-Schmidt正交化法 标准正交矩阵 定义标准正交向量（orthonormal）：$q_i^Tq_j=\begin{cases}0\quad i\neq j\1\quad i=j\end{cases}$ 我们将标准正交向量放入矩阵中，有$Q=\Bigg[q_1 q_2 \cdots q_n\Bigg]$。 上一讲我们研究了$A^A$的特性，现在来观察$Q^TQ=\begin{bmatrix} & q_1^T & \ & q_2^T & \ & \vdots & \ & q_n^T & \end{bmatrix}\Bigg[q_1 q_2 \cdots q_n\Bigg]$ 根据标准正交向量的定义，计 …

阅读更多

第十三讲：复习一 令$u, v, w$是$\mathbb{R}^7$空间内的非零向量：则$u, v, w$生成的向量空间可能是$1, 2, 3$维的。 有一个$5 \times 3$矩阵$U$，该矩阵为阶梯矩阵（echelon form），有$3$个主元：则能够得到该矩阵的秩为$3$，即三列向量线性无关，不存在非零向量使得三列的线性组合为零向量，所以该矩阵的零空间应为$\begin{bmatrix}0\0\0\ \end{bmatrix}$。 接上一问，有一个$10 \times 3$矩阵$B=\begin{bmatrix}U\2U \end{bmatrix}$，则化为最简形式（阶梯矩阵）应为$\begin{bmatrix}U\0 …

阅读更多

第十四讲：正交向量与子空间 在四个基本子空间中，提到对于秩为r的$m \times n$矩阵，其行空间（$dim C(A^T)=r$）与零空间（$dim N(A)=n-r$）同属于$\mathbb{R}^n$空间，其列空间（$dim C(A)=r$）与左零空间（$dim N(A^T)$=m-r）同属于$\mathbb{R}^m$空间。 对于向量$x, y$，当$x^T \cdot y=0$即$x_1y_1+x_2y_x+\cdots+x_ny_n=0$时，有向量$x, y$正交（vector orthogonal）。 毕达哥拉斯定理（Pythagorean theorem）中提到，直角三角形的三条边满足： $$ …

阅读更多

第十五讲：子空间投影 从$\mathbb{R}^2$空间讲起，有向量$a, b$，做$b$在$a$上的投影$p$，如图： 1%matplotlib inline 2import matplotlib.pyplot as plt 3import numpy as np 4import pandas as pd 5 6plt.style.use("seaborn-dark-palette") 7 8fig = plt.figure() 9plt.axis('equal') 10plt.axis([-7, 7, -6, 6]) 11plt.arrow(-4, -1, 8, 2, head_width=0.3, …

阅读更多

第十一讲：矩阵空间、秩1矩阵和小世界图 矩阵空间 接上一讲，使用$3 \times 3$矩阵举例，其矩阵空间记为$M$。 则$M$的一组基为： $ \begin{bmatrix} 1 & 0 & 0 \ 0 & 0 & 0 \ 0 & 0 & 0 \ \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \ 0 & 0 & 0 \ 0 & 0 & 0 \ \end{bmatrix} \begin{bmatrix} 0 & 0 & 1 \ 0 & 0 & 0 \ 0 & 0 & 0 \ \end{bmatrix} \ \begin{bmatrix} 0 & 0 & 0 \ 1 & 0 & 0 \ 0 & 0 …

阅读更多

第四讲：$A$ 的 $LU$ 分解 $AB$的逆矩阵： $$ \begin{aligned} A \cdot A^{-1} = I & = A^{-1} \cdot A\ (AB) \cdot (B^{-1}A^{-1}) & = I\ \textrm{则} AB \textrm{的逆矩阵为} & B^{-1}A^{-1} \end{aligned} $$ $A^{T}$的逆矩阵： $$ \begin{aligned} (A \cdot A^{-1})^{T} & = I^{T}\ (A^{-1})^{T} \cdot A^{T} & = I\ \textrm{则} A^{T} \textrm{的逆矩阵为} & …

阅读更多

第五讲：转换、置换、向量空间R 置换矩阵（Permutation Matrix） $P$为置换矩阵，对任意可逆矩阵$A$有： $PA=LU$ $n$阶方阵的置换矩阵$P$有$\binom{n}{1}=n!$个 对置换矩阵$P$，有$P^TP = I$ 即$P^T = P^{-1} 转置矩阵（Transpose Matrix） $(A^T){ij} = (A){ji}$ 对称矩阵（Symmetric Matrix） $A^T$ = $A$ 对任意矩阵$R$有$R^TR$为对称矩阵： $$ (R^TR)^T = (R)^T(R^T)^T = R^TR\ \textrm{即}(R^TR)^T = R^TR $$ 向量空间（Vector …

阅读更多

第一讲：方程组的几何解释 我们从求解线性方程组来开始这门课，从一个普通的例子讲起：方程组有$2$个未知数，一共有$2$个方程，分别来看方程组的“行图像”和“列图像”。 有方程组$\begin{cases}2x&-y&=0-x&+2y&=3\end{cases}$，写作矩阵形式有$\begin{bmatrix}2&-1-1&2\end{bmatrix}\begin{bmatrix}x\y\end{bmatrix}=\begin{bmatrix}0\3\end{bmatrix}$，通常我们把第一个矩阵称为系数矩阵$A$，将第二个矩阵称为向量$x$，将第三个矩阵称为向量$b$，于是线性方程组可以表示为$Ax=b$。 我们来看行图像，即 …

阅读更多

插入节点 删除堆顶 建堆 复杂度 堆是一棵完全二叉树，使用数组实现堆，堆分为两种： 最大堆：父节点大于任意子节点（因此堆顶为最大值） 最小堆：父节点小于任意子节点（因此堆顶为最小值） 对于第i个节点（i从0开始计数）： 父节点：(i-1)/2 左子节点：2i+1 右子节点：2i+2 若包含sz个节点，则第一个非叶子节点的序号为(sz - 2) / 2 插入节点 插入节点时，进行下列操作： 将元素添加到数组末尾；（相当于叶节点接入堆中） 和父节点进行比较，如果大于父节点(以最大堆为例)，则与父节点交换，一直比较交换到根节点 1/******************************************** 2 * 向堆中插 …

阅读更多

两种特殊二叉树 二叉树定理 前中后序遍历 递归版 迭代版 两种特殊二叉树 满二叉树（下图左）：除叶子节点外的所有分支节点都含有2个非空子节点的二叉树 完全二叉树（下图右）：除了最后一层，其余层都是“满”的，这样的二叉树是完全二叉树 二叉树定理 1）任意二叉树度数为2节点的个数等于叶节点个数减1 当只有1个节点时，度为0。每派生出1度，就会多出1个节点。派生出的度和派生出的节点数一定相等。那么就得出了总度数和节点总数的关系： 节点总数 = 总度数 + 1 设度数为2的节点数为X2，度数为1的节点数为X1，度数为0的节点数为X0。可以得出如下关系式： X2 + X1 + X0 = 2X2 + X1 + 1，推出 X2 = X0 - 1 …

阅读更多