Linear Algebra 线性代数

一些基础线性代数知识，主要是矩阵相关的知识。

特殊矩阵

酋矩阵，幺正矩阵，Unitary Matrix

与正交矩阵相似的复数矩阵。

埃尔米特矩阵，厄米矩阵，Hermitian Matrix

对厄米共轭保持不变。

正定矩阵与半正定矩阵

一个 $n \times n$ 的实对称矩阵 $M$ 是正定的，当且仅当对于所有非零实系数向量 $z$，有 $z^T M z \gt 0$. 一个 $n \times n$ 的厄米矩阵 $M$ 是正定的，当且仅当对于所有非零复向量 $z$, 有 $z^T M z \gt 0$. 注意 $z^T M z$ 对于厄米矩阵一定是实数。

等价定义：特征值全部为正的矩阵为正定矩阵。 当以上两个定义中的 $\gt$ 改为 $\ge$ 即可得到半正定矩阵定义。 当以上两个定义中的 $\gt$ 改为 $\lt$ 即可得到负定矩阵定义。类似的定义半负定矩阵。 矩阵 $A$ 为正定（半正定）的充要条件是存在（非奇异）矩阵 $Q$ 使得 $A = Q^T Q$.

实对称矩阵

实对称矩阵属于不同特征向量的特征值彼此正交。 实对称矩阵具有 $N$ 个线性无关的特征向量，可以特征分解。 具有 $N$ 个线性无关的特征向量的矩阵实际上代表了一个“拉伸”（无“旋转”）线性变换。

矩阵分解

QR 分解

$A = QR$, $A$ 为任意实数矩阵，$Q$ 为正交矩阵，$R$ 为上三角矩阵。 可以使用 Schmidt 正交化方法进行计算。也可以视为将矩阵进行上三角化的过程。 类似的可以定义 $QL$, $RQ$, $LQ$ 分解。 可以对非方阵类似的定义 $QR$ 分解。

特征分解

方阵的特征值与特征向量满足：$Mx = \lambda x$, 当方阵线性无关特征向量个数等于方阵维数，方阵可以被特征分解：

$Q$ 为满秩矩阵（并不是正交阵），$\Sigma$ 为对角阵，其对角元为特征值。

上式也即：

可以看到该等式可以解读为，$Q$ 的列向量（特征向量）经过线性变换 $M$，等价于乘以对应的特征值。

当特征值按照特定次序排序且特征值不重（每个特征值只有一个对应的特征向量）时，特征值分解唯一。

矩阵并不一定能进行特征值分解。高维随机矩阵几乎总是不能在实数域上进行特征值分解。这是因为特征向量的存在代表该矩阵所代表的线性变换在某个方向上只是拉伸（没有旋转），对于随机矩阵是低可能性的。

import numpy as np

# EIG
for i in range(100):
    M = np.random.random((10, 10))
    w, v = np.linalg.eig(M)

    print(np.allclose(w.imag, 0), end=' ')

# most of outputs is `false`.

奇异值分解

$ m \times n$ 矩阵的奇异值分解为：

上式中 $U, V$ 分别为 $m \times m$ 正交阵（或酋矩阵，若 $M$ 为复矩阵，下同） 和 $n \times n$ 正交阵。$\Sigma$ 为 $m \times n$ 对角阵。$V^*$ 为 $V$ 的厄米共轭运算。

上式也即

与特征值分解类似，这代表对 $V$ 的列向量进行线性变换 $M$，得到的向量是 $U$ 对应的列向量乘以 $\Sigma$ 对应的对角元。

奇异值分解与特征分解

对于 $n \times n$ 矩阵 $M$，特征分解也即寻找空间中的一组线性无关单位向量，在这些单位向量上，线性变换 $M$ 等价于乘对应的特征值。

对于 $m \times n$ 矩阵 $M$，奇异值分解是寻找 $m \times m$ 空间中的一组单位正交基 $U$ 和 $n \times n$ 维空间中的一组单位正交基 $V$，$M$ 作用在 $U$ 的某个列向量 $u$ 上时，得到的是 $V$ 上对应的列向量 $v$，并且长度是 $\Sigma$ 中对应的奇异值。

一个矩阵即使同时可以进行特征值分解和奇异值分解，其两种分解之间也没有必然联系。但如果方阵具有 $N$ 个特征向量，并且这些特征向量彼此正交，则特征分解与奇异值分解是相同的，如随机生成的实对称矩阵。

下面演示 numpy 中进行两种分解的代码示例。

import numpy as np

# EIG
M = np.random.random((4,4))
w, v = np.linalg.eig(M)

w = np.diag(w) # from array to matrix
assert(np.allclose(M.dot(v), v.dot(w)))

# SVD
U, s, V = np.linalg.svd(M)
S = np.diag(s)
# NOTE: M = U * S * V
assert(np.allclose(M, U.dot(S).dot(V)))
assert(np.allclose(M.dot(V.T), U.dot(S)))

下面演示实对称矩阵的 SVD 分解（奇异值分解）和 EIG 分解（特征值分解）等价。使用一个协方差矩阵作为实对称矩阵。

注意，特征向量乘以 $-1$ 仍然是特征向量，因此 $v, U$ 只能在最多差一个 $-1$ 的情况下等价。numpy 的特征值分解算法不会对特征值进行排序，因此特征值与奇异值的排列方式可能不同。

import numpy as np

M = np.random.random((4,4))
M = np.cov(M)

# EIG
w, E = np.linalg.eig(M)
W = np.diag(w) # from array to matrix
assert(np.allclose(M.dot(E), E.dot(W)))

# SVD
U, s, V = np.linalg.svd(M)
S = np.diag(s)
# NOTE: M = U * S * V
assert(np.allclose(M, U.dot(S).dot(V)))
assert(np.allclose(M.dot(V.T), U.dot(S)))

# EIG and SVD
assert(np.allclose(np.sort(s), np.sort(w)))
assert(np.allclose(np.sort(np.abs(E)), np.sort(np.abs(U))))

矩阵快速高次幂算法

无论是矩阵还是实数的高（正整数）次幂都可以使用类二分算法：

// recursive
double pow(double a, int n) {
    if(n == 0) return 1;
    if(n == 1) return a;
    double t = pow(a, n/2);
    return t * t * pow(a, n%2);
}
// non-recursive
double pow(double a, int n) {
    double ret = 1;
    while(n) {
        if(n%2 == 1) ret *= a;
        a *= a; n /= 2;
    }
    return ret; 
}

可对角化的矩阵可以使用更快的高次幂算法（接近 O(1)），但限制较多。

其基本原理是：

从底层完整实现该算法需要实现矩阵特征值分解算法，较为复杂。在实际应用场合，实现矩阵特征值分解的算法为 QR 算法，应检查该算法的复杂度。

在算法竞赛等场合中，二分高次幂算法速度足够快且实现简单。或者对于简单矩阵，手算进行特征值分解，然后再实现高次幂算法。

特殊空间

【欧几里得空间】：直观的欧氏空间。

【希尔伯特空间】 现在我不能完全理解希尔伯特空间。我所能理解的希尔伯特空间的一些特征：

• 定义有内积，由内积定义范数，空间本身可以是无穷维的。