格密码笔记三

一、线性空间

线性空间(vector spaces)：一个线性空间 $V$，是 $R^m$ 的一个子集，它满足$α_1v_1+α_2v_2∈V,\ for\ all\ v_1,v_2∈V,α_1,α_2∈R$

即，一个线性空间，是对向量加法、标量乘法封闭的 $R^m$ 的子集。

常见线性空间：
- $R^2$就是一个线性空间，图形表示就是一个平面直角坐标系。任取向量 $\begin{bmatrix}{0}\\{1}\\\end{bmatrix}$ 和 $\begin{bmatrix}{1}\\{0}\\\end{bmatrix}$ 做线性组合$ k_1 $\begin{bmatrix}{0}\\{1}\\\end{bmatrix}$ +k_1 $\begin{bmatrix}{1}\\{0}\\\end{bmatrix}$ =$$\begin{bmatrix}{k_1}\{k_2}\\end{bmatrix}$∈$R^2$
- {0} 也是一个线性空间，并且是最简单的线性空间。

二、线性组合

线性组合(linear combinations)：$v_1,v_2,…,v_k∈V $的一个线性组合是满足以下形式的向量：$w=α_1v_1+α_2v_2+⋯+α_kv_k,\ α_1,…,α_k∈R$

并将上述向量构成的集合：${α_1v_1+⋯+α_1v_k\ :\ α_1,…,α_k∈R}$称为 ${v_1,…,v_k} $的张成空间(span).

例如：

定义标量为2，4，1，5，权重为0.1，0.4，0.25，0.25。

则其线性组合：$s=0.12+0.44+0.251+0.255=3.3$

三、线性无关

线性无关(linearly independence) ：称一个向量集合$ v_1,…,v_k∈V$ 线性无关，当且仅当方程$α_1v_1+α_2v_2+⋯+α_kv_k=0$的唯一解是 $α_1=α_2=⋯=a_k=0$。

反之则称这个向量集合线性相关(linearly dependent)。

在线性代数中，一般来说，在N维的空间中，线性无关的最大数是N，第N+1个向量肯定能用前N个向量的线性方程来表示的。

四、基

基(bases) ：向量空间 $V $的一个基，是可以张成 $V$ 的线性无关向量集合 $v_1,…,v_n$。

即任何一个向量$ \omega∈V $都可以写成 $v_1,…,v_n$ 的线性组合的形式，其线性组合的系数是唯一的。

（一）维度

不同的基之间的关系

任何一个线性空间 $V$ 都有基
任何两个基，含有的向量个数是相同的。基的向量个数称为 $V$ 的维度(dimension)
设$ v_1,…,v_n$是 $V$ 的一个基$\omega_1,…,\omega_n$是 $V$ 中的一个向量组。我们把 $\omega_j$写成$v_i$ 的线性组合的形式：

$\omega1=α{11}v1+α{12}v2+⋯+α{1n}v_n$

$\omega2=α{21}v1+α{22}v2+⋯+α{2n}v_n$

⋮ ⋮

$\omegan=α{n1}v1+α{n2}v2+⋯+α{nn}v_n$

那么$\omega_1,…,\omega_n$也是$V $的一个基，当且仅当下面矩阵的行列式不为 0：
$\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{pmatrix}$

五、向量的长度&&向量的夹角

（一）点积

略

（二）欧几里得范数

欧几里得范数(Euclidean norm) ：向量 v 的长度，或称欧几里得范数，为$‖v‖=\sqrt{x_1^2+x_2^2+⋯+x_m^2}$，显然有$ v⋅v=‖v‖^2$.

（三）角度

设 $v,w∈V⊂R^m$。

记 θ 为向量 v,w 之间的角（这里我们把 v,w 的起始点都放在原点 0）。

则$v⋅w=‖v‖ ‖w‖cos⁡θ$
Cauchy-Schwarz 不等式¹：

两向量的点积的绝对值，不大于向量长度的积。

$|v⋅w|≤‖v‖ ‖w‖$

（四）正交基

正交基(orthogonal basis) ：线性空间 V 的一个正交基，是满足以下条件的基 $v_1,…,v_n$：

$v_i⋅v_j=0\ for\ all\ i≠j$
若这个基还满足 $‖v_i‖=1$，称这个基为规范正交(orthonormal)

关于利用此进行化简：

若$v1,…,v_n$是正交基，一个向量$v=a_1v_1+⋯+a_nv_n$ 是这个基的线性组合，则有$‖v‖^2=‖a_1v_1+⋯+a_nv_n‖^2=(a_1v_1+⋯+a_nv_n)⋅(a_1v_1+⋯+a_nv_n)=\sum{i=1}^{n}\sum{j=1}^{n}a_ia_j(v_i⋅v_j)=\sum{i=1}^{n}a_i^2‖v_i‖^2$

若这是一个规范正交基，式子可以进一步化简为：

$‖v‖^2=\sum a_i^2$.

五、生成规范正交基的算法 (Gram-Schmidt)

从任何一个向量组生成规范正交基，其张成空间不变。²

In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process is a method for orthonormalizing a set of vectors in an inner product space, most commonly the Euclidean space $R^n$ equipped with the standard inner product. The Gram–Schmidt process takes a finite, linearly independent set of vectors $S = {v_1, …, v_k}$ for k ≤ n and generates an orthogonal set $S′ = {u_1, …, u_k}$ that spans the same k-dimensional subspace of $R^n$ as S.

The application of the Gram–Schmidt process to the column vectors of a full column rank matrix yields the QR decomposition (it is decomposed into an orthogonal and a triangular matrix).

一个matlab实现：

function [U]=gramschmidt(V)
[n,k] = size(V);
U = zeros(n,k);
U(:,1) = V(:,1)/norm(V(:,1));
for i = 2:k
    U(:,i)=V(:,i);
    for j=1:i-1
        U(:,i)=U(:,i)-(U(:,j)'*U(:,i)) * U(:,j);
    end
    U(:,i) = U(:,i)/norm(U(:,i));
end
end

¹:Cauchy—Schwarz不等式及其常见证法 - 知乎 (zhihu.com)
²:Gram–Schmidt process - Wikipedia