Question

Matrix

“矩阵”。大家应该学过吧？

[ 1 2 -5 ]
[ 2 4  6 ]
[ 3 1  7 ]

其中
A1,1 = 1    A1,2 = 2   A1,3 = -5
A2,1 = 2    A2,2 = 4   A2,3 = 6
A3,1 = 3    A3,2 = 1   A3,3 = 7

一个矩阵由许多个数字构成，排列整齐，呈现矩形。我们习惯把数字改称为“元素 element”。

水平一整条元素叫做 row，垂直一整条元素叫做 column。元素的编号，先编 row，次编 column。

Matrix 资料结构

第一种方式，用一个二维阵列当作矩阵。如果你喜欢的话，也可以用一维阵列当作矩阵，然后自己算索引值。

另一种方式，把矩阵元素一个一个列出来。如果矩阵元素为零则不列出来。就这麽简单。

UVa 10855 11360 11149

Linear Transformation

好久好久以前，矩阵是用来存放大量数字的。然而自从线性代数开始流行之后，矩阵的地位完全改变了──矩阵其实是函数。

一个函数，仅由变数的加减、变数的倍率所组成，称作“线性变换”。

【注：照理应该称作“线性函数”，不过这个词彙已经被古人当作是“函数图形是直线的函数”，只好另起一名。】

是线性变换的例子：
f(x,y,z) = 1 x + 2 y - 5 z
f(x,y,z) = 1 x + (2 y - 5 z) * 2   乘开就是了

不是线性变换的例子：
f(x,y) = xy      不包含变数乘法
f(x) = x²        不包含变数乘法
f(x,y) = x / y   不包含变数除法
f(x) = sqrt(x)   不包含变数的其他运算
f(x) = x + 2     不包含常数项

可以套用线性变换作为模型的例子：
f(x) = 1 x + 2 x² - 5 x³   把 x² 与 x³ 重新看作是变数 y 和 z
f(x) = x + 2               2 后面乘上一个变数 y，让 y 永远是 1

人类习惯将线性变换呈现为矩阵的模样。

f(x,y,z) = 1 x + 2 y - 5 z

                      [ x ]
f(x,y,z) = [ 1 2 -5 ] [ y ]
                      [ z ]

通常会把各个变数改名成 x₁ x₂ x₃ ...
所有输入变数拼在一起，成为一个向量 x
输出变数叫做 y

                      [ x₁ ]
    y    = [ 1 2 -5 ] [ x₂ ]
                      [ x₃ ]

    y    =     A        x
    y    =     f      ( x  )

一般提到函数，输入可以是多重变数，但是输出一定是单一变数。一旦有了矩阵相助，输入与输出都可以是多重变数。

[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

  y    =     A        x
  y    =     f      ( x  )

约定俗成，我们会把 x 与 y 排列成向量，而非矩阵。如此一来，只要知道了线性变换的矩阵，就能完全确定函数的变数有多少个、完全确定函数是什麽。

输出变数、输入变数排列成矩阵：
[ y₁ y₃ ]   [ 1 2 -5 ] [ x₁ x₄ ]
[ y₂ y₄ ] = [ 2 4  6 ] [ x₂ x₅ ]
                       [ x₃ x₆ ]

    y     =     A          x
    y     =     f      (   x   )

输出变数、输入变数排列成向量：
[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
                    [ x₃ ]

  y    =     A        x
  y    =     f      ( x  )

一个矩阵就代表一个函数、一个线性变换。

A x ⇔ f(x)

A ⇔ f   省略 x 的部分

Linear Transformation 的排版方式

线性变换的排版方式，源自于线性方程组的排版方式。

遥想当年，古人为了节省纸张空间，尝试用矩阵表示线性方程组，并且抽出变数排成直的。

{ 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
{ 2 x + 4 y - 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
{ 3 x + 1 y - 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]

于是线性变换的排版方式，就模仿了这个排版方式。

因为这个排版方式，让高斯消去法，变成横的相消。

因为这个排版方式，让向量变成直的。

因为这个排版方式，让线性变换，变成横的配直的。

因为这个排版方式，让矩阵乘法，变成横的配直的。

因为这个排版方式，连续的线性变换，是从式子的右端到左端。

因为这个排版方式，有些线性代数课本劈头就介绍线性方程组，讲解一堆解方程式的技巧。然而线性方程组跟线性变换其实是两码子事，不适合参杂在一起。

Matrix Operation

矩阵运算本质上是函数运算，又额外增加了许多细项。

求值　　evaluation
求解　　resolution　（除法 division）
加法　　addition
减法　　subtraction
倍率　　scaling
複合  　composition　（乘法 multiplication）
分解  　decomposition
叠代  　iteration　　（次方 exponentiation）
反函数　inverse
转置　　transpose
秩　　　rank
行列式　determinant
迹　　　trace
积和式　permanent
微分　　differentiation
范数　　norm
梯度　　gradient

求值

A x ⇔ f(x)

Basis

Linear Transformation 的第一种观点

数学家发明了两种看待线性变换的观点：一种是矩阵切成直条、另一种是矩阵切成横条。先谈直条吧！

[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

         [ 1 ]          [ 2 ]          [ -5 ]
       = [ 2 ] ⋅ x₁  +  [ 4 ] ⋅ x₂  +  [  6 ] ⋅ x₃
         [ 3 ]          [ 1 ]          [  7 ]

外观看起来，彷彿是向量乘上倍率、再相加。我想大家已经相当熟悉向量的作图方式了。

以这些向量当作座标轴，画出座标格线。“向量乘上倍率、再相加”就变成了数格子。

线性变换可以看成：给定座标轴、座标值，然后求向量。座标轴是矩阵裡面的各个向量，座标值是输入向量。

有时候座标轴刚好是零向量、共线、共面、共空间、……，无法画出座标格线。儘管如此，线性变换仍然可以朦胧地看成：给定座标轴、座标值，然后求向量。

这样的座标轴，称做“基底 basis”。

Inverse

“反函数”。一般是入境随俗翻译为“反矩阵”。求反矩阵的演算法，请参考“ 高斯消去法 ”。

[ 1 2 -5 ]   inverse   [  22/80 -19/80  32/80 ]
[ 2 4  6 ]  -------->  [   4/80  22/80 -16/80 ]
[ 3 1  7 ]  <-------- 0="" 5="" 80="" [="" -10="" ]="" inverse="" a="" a⁻¹="" <="" pre="">

採用第一种观点，反矩阵可以看成是：以原本矩阵的直条当作座标轴，给定座标轴、向量，然后求座标值。

y = A⁻¹ x

Inverse 的存在条件

原函数拥有反函数的条件是一对一函数：

一、输入与输出一样多。

二、不同输入得到不同输出。

原函数是如此，反函数亦是如此。

原矩阵拥有反矩阵的条件也是一对一函数：

一、输入变数与输出变数一样多。矩阵是方阵。

二、座标轴没有零向量、共线、共面、共空间、……，得以顺利画出座标格线，让不同座标值得到不同向量。

简单来说：一个座标轴产生一个维度，必须刚好产生所有维度。

原矩阵是如此，反矩阵亦是如此。

Linear Transformation 的第二种观点

[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

         [ (1 2 -5) ∙ (x₁ x₂ x₃) ]
       = [ (2 4  6) ∙ (x₁ x₂ x₃) ]
         [ (3 1  7) ∙ (x₁ x₂ x₃) ]

线性变换也可以看成：以横条当作座标轴，然后求出输入向量与各座标轴的“ 点积 ”。换句话说，就是输入向量在各座标轴上面的投影量、另乘上座标轴长度。

因为已经规定直条是座标轴，所以横条当作座标轴挺彆扭。数学家就想到，把矩阵翻转一下、继续讨论。

Transpose

“转置矩阵”。以左上右下对角线为对称轴，所有矩阵元素对称地调换位置。也可以想成是横的变直的。也可以想成是直的变横的。

[ 1 2 -5 ]   transpose   [  1 2 3 ]
[ 2 4  6 ]  ---------->  [  2 4 1 ]
[ 3 1  7 ]  <---------- 6="" 7="" [="" -5="" ]="" transpose="" a="" aᵀ="" <="" pre="">

[ 1 2 3 ]   transpose   [ 1 0 9 5 ]
[ 0 0 7 ]  ---------->  [ 2 0 8 4 ]
[ 9 8 7 ]  <---------- 3="" 4="" 5="" 6="" 7="" [="" ]="" transpose="" a="" aᵀ="" <="" pre="">

採用第二种观点，转置矩阵可以看成：以原本矩阵的直条当作座标轴，将输入向量分别投影到各座标轴，求投影量（另乘上座标轴长度）。

y = Aᵀ x

UVa 10895 11349

Inverse 与 Transpose 的差别

转置矩阵跟反矩阵有些相似，主要有三个地方不同：

一、转置矩阵是垂直投影；反矩阵是沿著座标轴平行投影。

二、转置矩阵的输出，受到座标轴的单位长度影响，单位长度越长则输出数值越大；反矩阵刚好颠倒，是越小。

三、转置矩阵可以是一对一函数，也可以是收束的函数；反矩阵只能是一对一函数。

当转置矩阵和反矩阵一样的时候，座标轴必须互相垂直、座标轴的单位长度都是一、矩阵是方阵，就是所谓的（实数版本）正规正交矩阵 orthonormal matrix、（複数版本）么正矩阵 unitary matrix。此时转置矩阵和反矩阵都是垂直投影、都是在求座标值。

Transformation

Transformation

先前在计算几何领域，已经详细介绍过“ Transformation ”。本篇文章从线性变换的角度，再度介绍一次。顺便藉此机会，让读者更加瞭解线性变换的功效。

这些二维平面上的动作，其实都是线性变换，每种动作都有对应的矩阵。想要实施动作，那就乘上矩阵（函数的求值）。想要还原动作，那就乘上反矩阵（反函数）。想要实施一连串的动作，那就乘上一连串的矩阵。

new        step 3             step 2  step 1  original
coordinate rotate             scale   shear   coordinate
[ x' ]  =  [ cos45° -sin45° ] [ 2 0 ] [ 1 1 ] [ x ]
[ y' ]     [ sin45°  cos45° ] [ 0 3 ] [ 0 1 ] [ y ]

甚至可以预先把一连串的矩阵相乘起来（函数的複合），变成一个矩阵，一个矩阵就能代表一连串的动作，相当方便！

new        step 1 & 2 & 3              original
coordinate shear, scale, rotate        coordinate
[ x' ]  =  [ 2cos45° 2cos45°-3sin45° ] [ x ]
[ y' ]     [ 2sin45° 2sin45°+3cos45° ] [ y ]

以座标轴的观点来思考

线性变换常常用座标轴的观点来思考。以座标轴为主角，缩放、旋转、投影这些动作其实都是在改动座标轴。

先从最基础的纹风不动开始介绍起吧！以原点为中心，座标轴方向设定为 X 轴正向和 Y 轴正向，座标轴长度是 1。

[ 1 0 ]
[ 0 1 ]

Scale

“缩放”，以原点为中心，缩放座标轴。X 轴、Y 轴可以分别缩放不同倍率。

[ sx   0 ]
[  0  sy ]

Shear（Skew）

“歪斜”，以原点为中心，改变其中一个座标轴。

[  1 0 ] upward / downward
[ ty 1 ]

[ 1 tx ] rightward / leftward
[ 0  1 ]

另一种方式是设定歪斜角度。

[    1 0 ] upward / downward
[ tanθ 1 ]

[ 1 tanθ ] rightward / leftward
[ 0    1 ]

Rotate

“旋转”，以原点为中心，旋转座标轴。

[ cosθ -sinθ ]
[ sinθ  cosθ ]

Project

“投影”，一个座标轴当作投影线，另一个座标轴变成零向量。

[ 1 0 ]
[ 0 0 ]

Reflect

“镜射”，一个座标轴当作对称线，另一个座标轴颠倒方向。

[ 1  0 ]
[ 0 -1 ]

Translate

“位移”不是线性变换！不过“位移”可以套用线性变换：座标增加一个维度，数值固定为 1；矩阵增加一个维度，将位移量填在新维度。

用几何的角度解释，就是把二维位移变成三维歪斜：将原本的 xy 平面固定放在 z=1 的高度，沿著平面滑动。

[ x' ]   [ 1 0 tx ] [ x ]
[ y' ] = [ 0 1 ty ] [ y ]
[ 1  ]   [ 0 0 1  ] [ 1 ]

前面介绍的矩阵，通通跟著改成三维，如此一来位移矩阵就能和其他矩阵相乘了。增加一个维度，以便让位移融入大团体──这个手法称作“齐次座标 Homogeneous Coordinates”。

线性变换、位移，合称“仿射变换 Affine Transformation”。

Unitary Matrix

Indentity Matrix

“单位矩阵”。第一座标轴的第一个值是 1，其馀是 0；第二座标轴的第二个值是 1，其馀是 0；以此类推。它是标准的座标轴。

所有向量经过单位矩阵变换之后，纹风不动，完全不变。（identity 是指相同个体。）

逆向变换（反矩阵）显然还是单位矩阵，不必另外计算。

Orthonormal Matrix / Unitary Matrix

“正规正交矩阵”是实数版本。“么正矩阵”是複数版本。

座标轴长度皆为 1、互相垂直。（ortho-是指垂直，normal 是指一单位量，unitary 是指基本单元。）

想要判断一个矩阵是不是正规正交矩阵、么正矩阵，可以利用点积：长度为 1，自己与自己的点积为 1；互相垂直，点积为 0。

所有向量们经过正规正交矩阵、么正矩阵变换之后，长度不变、夹角不变。即是形状不变。相当好用！

逆向变换（反矩阵）恰好是转置，不必另外以高斯消去法计算。

举例来说，单位矩阵、旋转矩阵、镜射矩阵是正规正交矩阵，缩放矩阵、歪斜矩阵、投影矩阵不是正规正交矩阵（除非恰好等于单位矩阵）。

正规正交矩阵的功效是旋转暨镜射。

Rank

座标轴所构成的超平行体的维度。消除导致零向量、共线、共面、共空间、……的座标轴，剩下的座标轴数量就是维度。

尝试将各个座标轴乘上倍率、互相加减抵消，就能消除多馀的座标轴了。通常会有许多种消除方式。

Rank 相关定理

rank(AB) ≤ min(rank(A), rank(B))。矩阵複合，消失的维度回不来了。

rank(A⁻¹) = N。反矩阵的条件就是座标轴必须刚好产生所有维度，维度显然是 N。前提是有反矩阵。

rank(Aᵀ) = rank(A)。矩阵转置，维度一样。

Determinant

座标轴所构成的超平行体的容积。一维是长度、二维是平行四边形的面积、三维是平行六面体的体积。

一、消灭分量，令座标轴互相垂直，此时所有座标轴的长度相乘，就是容积。简单来说，这就是中学数学“底乘以高”的概念。

二、座标轴所构成的维度、即超平行体的维度，必须跟空间维度一致，否则容积被定义为 0。这跟反矩阵的条件是一样的。

当座标轴有零向量、共线、共面、共空间、……，容积是 0。当座标轴数量大于或小于空间维度，容积是 0。只有 N×N 方阵、且 rank 为 N，才有讨论意义。

因此 inverse、rank、determinant 总是被相提并论：有反矩阵，维度是 N，容积不是 0；无反矩阵，维度小于 N，容积是 0。

三、容积有正负号。当其中一个座标轴颠倒方向，容积将变号。当其中两个座标轴交换次序，容积将变号。

举例来说，单位矩阵的容积是 1。正规正交矩阵、么正矩阵可能是 1、可能是-1。旋转矩阵是 1。镜射矩阵是-1。缩放矩阵、歪斜矩阵是左上右下对角线元素的乘积。投影矩阵是 0。

Determinant 相关定理

det(AB) = det(A) det(B)。矩阵複合，容积相乘。

det(A⁻¹) = 1/det(A)。反矩阵的容积是倒数。如果有反矩阵的话。

det(Aᵀ) = det(A)。矩阵转置之后，容积不变！几何意义：依序取出每个向量的 X 座标组成一个新向量、依序取出每个向量的 Y 座标组成一个新向量、……，所形成的容积仍然相同！我想不出直观的证明方式，也想不出如何应用。

求得 Rank 和 Determinant

消灭分量，令座标轴互相垂直，以求得容积与维度。例如稍后提到的“QR 分解”可以求得容积与维度。

另外，转置矩阵的容积与维度不变，于是原本矩阵的横条，亦得视作座标轴。这使得“ 高斯消去法 ”也可以求得容积与维度。

另外，由于高斯消去法的关係，容积、维度、反矩阵经常被联繫到线性方程组的唯一解、多解、无解判定。

Timus 1041

QR Decomposition

把一个矩阵的座标轴扳成互相垂直的单位向量，让座标轴长得正、长得帅。

把一个矩阵 A 分解成矩阵 Q 与矩阵 R 的乘积，A = QR。Q 是互相垂直的单位向量（么正矩阵），R 是扳动量（上三角矩阵）。

演算法（Gram-Schmidt Orthonormalization）

https://en.wikipedia.org/wiki/Gram–Schmidt_process

一、从中随便挑出一个向量（通常是第一个，以便让 R 成为上三角矩阵），
　　作为第一座标轴，向量长度调整成 1。
二、所有剩馀向量们，各自减掉在第一座标轴上的分量，彻底消灭该维度。
　　所有剩馀向量们，现在显然都垂直于第一座标轴。
三、所有剩馀向量们，递迴处理下去。

藉由投影、相减、缩放，逐步调整矩阵 A 的每个向量，直到变成正规正交矩阵 Q。

时间複杂度 O(N^3)。

演算法（Householder Triangularization）

http://faculty.ucmerced.edu/mhyang/course/eecs275/lectures/lecture12.pdf

镜射矩阵有一个特殊用处，把一个向量镜射到标准座标轴上（镜子位于角平分线），让该向量变成只有一个元素有值（其值是向量长度），其馀元素都是零。

不断套用镜射矩阵，逐步调整矩阵 A 的每个向量，直到变成上三角矩阵 R。优点是向量的长度变化比较少、误差比较小。

时间複杂度 O(N^3)。

演算法（Givens Triangularization）

http://www.cs.nthu.edu.tw/~cherung/teaching/2011anm/note07.pdf

Givens 旋转：在标准座标轴当中，选择其中两个轴，在其平面上旋转。

不断套用 Givens 旋转矩阵，逐步调整矩阵 A 的每个向量，直到变成上三角矩阵 R。优点是容易设计平行演算法。

时间複杂度 O(N^3)。

Polar Decomposition

把一个矩阵 A 分解成矩阵 U 与矩阵 P 的乘积，A = UP。U 是互相垂直的单位向量（么正矩阵）。P 是非负的缩放倍率（正半定矩阵）。

U 是旋转暨镜射，P 是缩放。P 设定为正半定矩阵，是为了把镜射（缩放倍率为负值）的部分，硬是移动到 U。

【待补文字】

Eigenbasis (I)

Function

本站文件“ Function ”，介绍了“输入有很多个变数，输出只有一个变数”的函数，也画出了函数图形。

此处要介绍“输入有很多个变数，输出有很多个变数”的函数，并且画出函数图形。

此处以ℝ² ⇨ ℝ²函数为例，输入是两个变数、输出是两个变数的函数，可以画在二维平面上。因为绘图结果往往是一片满，看不出任何意义，所以把输入改成等距取样、保持间隔。

Linear Transformation

线性变换是一种特别的函数，函数图形有著一种难以言喻的整齐。有时是一致朝外，有时是一致螺旋。

这样的函数图形，可以用来解释真实世界的物理现象！例如磁场、气旋等等。甚至数学家还把输入输出推广到複数，发明“複变函数”的学问，发掘更多样化的函数图形──不过这是后话了。先让我们专注于线性变换吧！

Linear Transformation 的本质：朝著目标向前进

整齐的原因是什麽呢？数学家已经初步解决了这个问题！

数学家猜测，所谓的整齐，也许是指：“大家有著共识，方向一致。”再进一步猜测：“这当中有没有堪称表率，让大家群起效尤的输入输出呢？是不是有人一路以来始终如一，坚持走在正确的道路上？”于是数学家尝试寻找：“有哪些输入向量，经过线性变换之后，方向保持不变。”

Eigenvector 与 Eigenvalue

数学家尝试解 A x = λ x 这道式子。A 是线性变换；x 是向量，方向保持不变，称作“特徵向量 eigenvector”；λ是缩放倍率，称作“特徵值 eigenvalue”。

A x = λ x，移项得 A x - λ x = 0，合併得(A - λI) x = 0。

如果是唯一解，得到 x 是零向量。缺乏讨论意义。

如果要有其他解，那麽令 det(A - λI) = 0。把 det(A - λI) 展开，形成λ的多项式，称作“特徵多项式 characteristic polynomial”。特徵多项式求根，即得λ。

求得 eigenvalue，代入到(A - λI) x = 0，求得 eigenvector。

A = [ 1 -1 ]   A - λI = [ (1-λ)  -1   ]      det(A - λI) = 0
    [ 2  4 ]            [   2   (4-λ) ]   => (1-λ)(4-λ) + 2 = 0
                                          => λλ - 5λ + 6 = 0
                                          => λ = 2 or 3

when eigenvalue λ = 2        |   when eigenvalue λ = 3        
                             |                                
    (A - λI)      x  =  0    |       (A - λI)      x  =  0    
                             |                                
[ (1-2)  -1   ] [x₁] = [0]   |   [ (1-3)  -1   ] [x₁] = [0]   
[   2   (4-2) ] [x₂]   [0]   |   [   2   (4-3) ] [x₂]   [0]   
                             |                                
get { x₁ = 1k                |   get { x₁ = -1k               
    { x₂ = 1k                |       { x₂ =  2k               
                             |                                
then eigenvector x = [-1]    |   then eigenvector x = [-1]    
                     [ 1]    |                        [ 2]    

eigenvector 的任何一种倍率也都是 eigenvector。大家习惯取长度为 1 的 eigenvector 当作代表，方向则是随意。

如果有许多个 eigenvector 拥有相同的 eigenvalue，那麽这些 eigenvector 构成的平面、空间、……当中的任何一个向量都是 eigenvector。大家习惯取互相垂直的 eigenvector 当作代表，方向则是随意。

eigenvector 的推导过程冗长複杂，不太讨喜。然而数学家尚未想到其他导致整齐的原因，也说不定没有其他原因了。因此大家很重视 eigenvector，所有线性代数的课本都会仔细介绍 eigenvector。

特殊现象

一、eigenvector 不存在。

例如歪斜矩阵，eigenvector 不足 N 个。

二、eigenvalue 必是 N 个。

数学家藉由 determinant 与 characteristic polynomial 来定义 eigenvalue。N 次多项式必有 N 个根，必得 N 个 eigenvalue。这个定义方式，有时候产生了多馀的 eigenvalue。

例如歪斜矩阵，eigenvector 不足 N 个，eigenvalue 却是 N 个。

三、eigenvector 存在，但是是複数。

根据定义，数学家硬是算出複数的 eigenvalue，进一步得到複数的 eigenvector。

例如旋转矩阵，eigenvector 确实存在，即便没有任何缩放、即便无法作图。

特徵向量演算法（Characteristic Polynomial）

多项式求根。请参考“ Root Finding ”。

然而无法克服：一、根的范围完全不明；二、根可能是複数。

Eigenbasis (II)

Linear Transformation 的本质：缩放与旋转

首先讨论 eigenvalue 为实数。

当输入向量等于 eigenvector 的方向，那麽输出向量就是输入向量乘上 eigenvalue，方向保持不变。

当输入向量不是 eigenvector 的方向，此时可以运用分量的概念：Ax = A(x₁+x₂) = Ax₁ + Ax₂。输入向量，求出在 eigenvector 上面的分量，各个分量各自按照 eigenvalue 缩放，再合而为一，得到输出向量。

最后得到非常重要的结论：线性变换的本质，是在特徵向量上面，根据特徵值来缩放！

接著讨论 eigenvalue 为虚数。

老实说，我不懂，就略过吧。一般大家认为其效果是旋转。

矩阵次方

实施线性变换，eigenvalue 为实数，效果是缩放。eigenvalue 为虚数，效果是旋转。eigenvalue 为零，效果是消灭分量。eigenvalue 为负数，效果是翻转分量。

反覆实施线性变换，eigenvalue 绝对值小于一的方向趋近零，eigenvalue 绝对值等于一的方向保持不动，eigenvalue 绝对值大于一的方向趋近无限大。绝对值越小就缩短越快，绝对值越大就伸长越快，输入向量将渐渐偏向绝对值最大的方向。

eigenvalue 是负数，将不断来回翻转、来回跳跃，但是整体趋势仍与正数相同。

反覆实施线性变换，有时收敛至某处，有时发散至正负无限大、有时不断绕圈，端看起点在哪裡。

A = [ a  b ]   p₀ = [ x₁ ]   p₁ = [ y₁ ]
    [ c  d ]        [ x₂ ]        [ y₂ ]

eigenvalues of A = {λ₁, λ₂}
let |λ₁| ≥ |λ₂|

考虑 A p₀ = p₁的过程，观察特徵向量的影响力。

解  [  1  1 ] [ m₁ ] = [ x₁ ] = [ x₁        ]     --> p₀
    [ λ₁ λ₂ ] [ m₂ ]   [ y₁ ]   [ ax₁ + bx₂ ]     --> A p₀ = p₁
    x₁ 分别在两个特徵向量的分量，座标是 m₁ m₂。

解  [  1  1 ] [ n₁ ] = [ x₂ ] = [ x₂        ]     --> p₀
    [ λ₁ λ₂ ] [ n₂ ]   [ y₂ ]   [ cx₁ + dx₂ ]     --> A p₀ = p₁
    x₂ 分别在两个特徵向量的分量，座标是 n₁ n₂。

因为最后一定是朝向 eigenvalue 绝对值最大的 eigenvector 方向，
所以要判断 x₁ 最终朝向哪个方向，只需看 m₁ 的正负号。
所以要判断 x₂ 最终朝向哪个方向，只需看 n₁ 的正负号。

UVa 720

Trace-Determinant Diagram

以 trace 和 determinant 判断流向。

特徵向量演算法（Power Iteration）

只能求出绝对值最大的 eigenvalue 及其 eigenvector。

然而无法克服：一、根的范围完全不明；二、根可能是複数。

递推法。反覆实施线性变换，只要实施足够次数（矩阵次方，次方值足够大），就会朝向 eigenvalue 的绝对值最大的 eigenvector 的方向。

反覆实施线性变换，向量可能越来越长、越来越短，超出浮点数范围。解法是每一步骤都将向量长度缩放为 1。

时间複杂度 O(N^2 * K)，N 是矩阵大小，K 是叠代次数。

收敛速度，跟最大、次大特徵值的绝对值的比值|λ₁|/|λ₂|有关。比值越大，收敛速度越快。

很幸运的，我们可以调整特徵值。当矩阵的对角线加上同一个值，则特徵值们恰好都加上同一个值。(A + aI)x = Ax + ax = λx + ax = (λ + a)x。

我们可以调整特徵值，藉以提高比值，增加收敛速度，减少叠代次数。

特徵向量演算法（Inverse Iteration）

以 Power Iteration 找出所有的 eigenvalue 及其 eigenvector。

然而无法克服：一、根的范围完全不明；二、根可能是複数。

时间複杂度是 N 次 Power Iteration 的时间。

eigenvalues of A: λ₁, λ₂, λ₃, ...
let |λ₁| ≥ |λ₂| ≥ |λ₃| ≥ ...

let B = (A - αI)⁻¹
eigenvalue of B: 1/(λ₁-α) , 1/(λ₂-α) , 1/(λ₃-α) ...

α猜得准，会让 1/(λ-α) 变很大，成为 B 的λ₁。
此时套用 Power Iteration 即可得到 1/(λ-α)。

xk+1 = B xk = (A - αI)⁻¹ xk
此处化作 (A - αI) xk+1 = xk
即可採用 LU Decomposition。
叠代一次的时间複杂度从 O(N^3) 降为 O(N^2)。

Eigenbasis (III)

Eigendecomposition
（Spectral Decomposition）（Diagonalization）

线性变换的本质，拆成三个步骤，尝试改成矩阵：

一、“输入向量，求出在 eigenvector 上面的分量”：套用反矩阵，座标轴是特徵向量。
二、“各个分量各自按照 eigenvalue 缩放”：套用缩放矩阵，缩放比例是特徵值。
三、“各个分量合而为一，得到输出向量”：套用矩阵，座标轴是特徵向量。

[ 1 2 5 ]   eigendecomposition   [ X X X ] [ X 0 0 ] [ X X X ]
[ 2 4 6 ]  ------------------->  [ X X X ] [ 0 X 0 ] [ X X X ]
[ 3 1 7 ]                        [ X X X ] [ 0 0 X ] [ X X X ]
    A                                E         D         E⁻¹

写成数学式子就是 A = EDE⁻¹。E 是特徵向量（必须有反矩阵）（可逆矩阵），D 是特徵值（缩放矩阵）（对角线矩阵）。

这称作“特徵分解”或“频谱分解”或“对角化”。

Eigendecomposition 的存在条件

第一步骤使用了反矩阵。也就是说，特徵向量构成的矩阵，必须拥有反矩阵。至于反矩阵的存在条件，请参考前面章节。另外再介绍两个形容词：

invertable：可逆。原矩阵有反矩阵。
diagonalizable：可对角化。可特徵分解。原矩阵可找到一组特徵向量有反矩阵。

举例来说，单位矩阵、旋转矩阵、镜射矩阵、缩放矩阵、投影矩阵可以特徵分解，歪斜矩阵不可以特徵分解。

矩阵次方

同样的矩阵，同样的特徵向量，不必反覆套用反矩阵、矩阵，只要连乘特徵值即可。

A  = EDE⁻¹
A² = EDE⁻¹EDE⁻¹ = ED²E⁻¹
A³ = EDE⁻¹EDE⁻¹EDE⁻¹ = ED³E⁻¹

Eigenbasis (IV)（Under Construction!）

Change of Basis

A = MSM⁻¹。M 是任意矩阵（可逆矩阵），S 是某个矩阵（相似矩阵）。

建立一组座标轴，然后把原本矩阵放到这个座标轴上面来看。

相似矩阵是功能完全一样的矩阵，仅仅座标轴不同。

Hessenberg Decomposition 与 Schur Decomposition

A = QHQ⁻¹。H 是上三角暨次对角线矩阵，Q 是么正矩阵。

A = QUQ⁻¹。U 是上三角矩阵，Q 是么正矩阵。

这两个分解，是用来设计演算法、求得特徵值、完成特徵分解。对数学家来说是鸡肋，但是对计算学家来说却是好工具。

特徵向量演算法（QR Iteration）

原本矩阵，透过变换基底的技巧，逐渐变成上三角矩阵。原本矩阵的特徵值就是上三角矩阵的特徵值，而上三角矩阵的对角线正是特徵值。

try to converge to upper-triangle matrix.
but usually fails.

when A is real symmetric matrix (which has orthonormal eigenbasis).
QR iteration will try to converge to diagonal matrix.
fortunately Q is eigenbasis.

Ak = Qk Rk
Ak+1 = Rk Qk    = Qk⁻¹ Ak Qk = Qkᵀ Ak Qk
                  ^^^^^^^^^^^
                  change of basis

Ak and Ak+1 are similar (change of basis).
Their eigenvalues are same.

per iteration O(n^3), total O(k * n^3).

特徵向量演算法（Hessenberg QR Iteration）

http://persson.berkeley.edu/18.335/lec14handout6pp.pdf

预先将矩阵转化成 Hessenberg Matrix，再实施 QR Iteration，比较容易收敛成上三角矩阵。

1. [Hessenberg Decomposition]
   run n-1 times Household transformation
   and get Hessenberg matrix.
   per iteration O(n^2), total O(n^3).

   (Household transformation:
    use reflection matrix as new basis)

2. [QR Iteration]
   use Hessenberg matrix run QR iteration
   and get upper-triangular matrix.
   per iteration O(n^2), total O(k* n^2).

   (during iterations, always keeps Hessenberg matrix.)
   (upper-triangular * hessenberg = hessenberg)
   (hessenberg * upper-triangular = hessenberg)

特徵向量演算法（Jacobi Iteration）

http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm

特徵向量演算法（Arnoldi Iteration）

for matrix: Arnoldi iteration
for symmetric matrix: Lanczos iteration

http://www.math.uzh.ch/?file&key1=22557

Av = λv
Eigenvalues: λ1 λ2 ... λn

Cayley-Hamilton theorem
(A – λ1I) (A – λ2I) ... (A – λnI) = 0 
 Σ ci Ai = 0   for some ci
0~n
A⁻¹ =  Σ (–ci/c0) Ai–1
      1~n

Krylov subspace:
Ax = b  ===>  x = A⁻¹ b
x = span(b  Ab  A2b ... An-1b) = K(A, b)

特徵向量演算法（Rayleigh-Ritz Method）

https://en.wikipedia.org/wiki/Rayleigh–Ritz_method

Eigenbasis (V)（Under Construction!）

Singular Value Decomposition（SVD）

if matrix cannot eigendecomposition, we use SVD to get real eigenbasis.
for example: non-symmetric real matrix (complex eigenbasis)
for example: non-square matrix

AAᵀ is symmetric matrix, which eigenbasis is orthonormal/unitary basis
AᵀA is symmetric matrix, which eigenbasis is orthonormal/unitary basis

basis no1 is orthonormal/unitary matrix. (dimension reduction)
basis no2 is orthonormal/unitary matrix. (dimension extension)
change to diagonal matrix: square root of eigenvalues, called singular values.

         T
A = U Σ V 

 T       T T      T       T     T
A A = V Σ U  U Σ V = V ( Σ Σ ) V

   T       T    T T         T   T
A A = U Σ V  V Σ U = U ( Σ Σ ) U

                                      T         T
get V and U by eigendecomposition of A A and A A  
             T            T  
Σ = sqrt( Σ Σ ) = sqrt ( Σ Σ )

快速演算法，不必计算 AᵀA 和 AAᵀ。

http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf

Jordan Decomposition

http://math.stackexchange.com/questions/193460/

线性代数的本质：缩放与座标轴对调。

ring。

UVa 10753

Eigenvector 与 Eigenvalue 的相关定理

eigenvalue 的乘积是 determinant。

eigenvalue 皆不为零则有 inverse。

eigen(QA) ≠ eigen(A)。任意矩阵经过么正矩阵转换，特徵向量和特徵值都会改变。除非遇到特例。

eigen(AB) ≠ eigen(A) eigen(B)。矩阵複合，那就改变更多。除非遇到特例。

eigenvector(A²) = eigenvector(A)。连续变换两次，特徵向量一样，特徵值连乘两次。

eigenvector(A⁻¹) = eigenvector(A)。反矩阵，伸与缩颠倒，特徵向量一样，特徵值变倒数。

eigenvalue(Aᵀ) = eigenvalue(A)。转置矩阵，特徵向量改变，但是特徵值一样。我想不出直观的解释方式。大家都是间接透过 determinant 来证明。

特殊矩阵

（複数版本）么正矩阵 unitary matrix：特徵向量形成么正矩阵，特徵值的绝对值都是 1。

（实数版本）正规正交矩阵 orthonormal matrix：特徵向量形成正规正交矩阵，特徵值的绝对值都是 1。注意到特徵值可为複数，例如旋转矩阵。

unitary matrix A : A* = A⁻¹
orthonormal matrix A: Aᵀ = A⁻¹

（複数版本）共轭对称矩阵 Hermitian matrix：特徵向量形成么正矩阵，特徵值都是实数。

（实数版本）对称矩阵 symmetric matrix：特徵向量形成正规正交矩阵，特徵值都是实数。

Hermitian matrix A : A* = A
symmetric matrix A : Aᵀ = A

（複数版本）反共轭对称矩阵 skew-Hermitian matrix：特徵向量形成么正矩阵，特徵值都是虚数。

（实数版本）反对称矩阵 skew-symmetric matrix：特徵向量形成正规正交矩阵，特徵值都是虚数。

skew-Hermitian matrix A : A* = -A
skew-symmetric matrix A : Aᵀ = -A

正规矩阵 normal matrix：特徵向量形成么正矩阵。

normal matrix A : A* A = A A*

正半定矩阵 positive-semidefinite matrix：特徵值都是正数或零。

正定矩阵 positive-definite matrix：特徵值都是正数。

positive-semidefinite matrix A : A = M* M
    positive-definite matrix A : A = M* M and M⁻¹ exists

positive-semidefinite matrix A : x*Ax ≥ 0
    positive-definite matrix A : x*Ax > 0 when x ≠ 0

可交换矩阵 commuting matrices：特徵向量相同。

commuting matrices A and B : AB = BA

相似矩阵 similar matrices：特徵值相同。这是单向推论。例外是单位矩阵和歪斜矩阵，特徵值都是两个 1，但是不相似。

similar matrices A and B : A = M⁻¹ B M

对角线矩阵 diagonal matrix：特徵向量即是矩阵本身，特徵值即是对角线。这是单向推论。

diagonal matrix A : Ai,j = 0 when i ≠ j

三角矩阵 triangular matrix：特徵值即是对角线。这是单向推论。

upper triangular matrix A : Ai,j = 0 when i > j
lower triangular matrix A : Ai,j = 0 when i < j

Transformation（Under Construction!）

Transformation

先前介绍一个向量的变换，现在介绍多个向量的变换。

本篇文章从线性变换的角度，简单介绍一次。顺便藉此机会，让读者更加瞭解特徵基底的功效。之后于“ Representation ”章节将详细介绍。

Principal Component Analysis

Independent Component Analysis

Principal Component Pursuit

Positive-definite Matrix（Under Construction!）

微分

矩阵是函数，当然也有微分运算。

一个线性函数，对各个变数微分。得到多个导数。

                           ∂f         ∂f         ∂f     
f = (x₀ + x₁ + x₂)         ――― = 1    ――― = 1    ――― = 1
                           ∂x₀        ∂x₁        ∂x₂    

                           ∂f         ∂f         ∂f      
f = (c₀x₀ + c₁x₁ + c₂x₂)   ――― = c₀   ――― = c₁   ――― = c₂
                           ∂x₀        ∂x₁        ∂x₂     

一个线性函数，对一整个向量微分。将导数们从上到下依序拼成一个向量。

                                [ x₀ ]
 f = (c₀x₀ + c₁x₁ + c₂x₂)   x = [ x₁ ]
                                [ x₂ ]
∂f   [ ∂f/∂x₀ ]   [ c₀ ]
―― = [ ∂f/∂x₁ ] = [ c₁ ]
∂x   [ ∂f/∂x₂ ]   [ c₂ ]

∂   T                                        d        
―― y x = y                             --->  ―― xy = y
∂x                                           dx       

∂   T                                        d        
―― x y = y                             --->  ―― yx = y
∂x                                           dx       

∂   T                                        d   2     
―― x x = 2x                            --->  ―― x  = 2x
∂x                                           dx        
                      when A is
∂   T            T    symmetric              d    2      
―― x A x = (A + A ) x ========= 2Ax    --->  ―― ax  = 2ax
∂x                                           dx          

多个线性函数，依序拼成一个向量，对整个向量微分。将导数们从左到右依序拼成一个矩阵。此即矩阵微分。

     [ f₀ ]   [ a₀x₀ + a₁x₁ + a₂x₂ ]   [ a₀ a₁ a₂ ]       
     [ f₁ ]   [ b₀x₀ + b₁x₁ + b₂x₂ ]   [ b₀ b₁ b₂ ] [ x₀ ]
 F = [ f₂ ] = [ c₀x₀ + c₁x₁ + c₂x₂ ] = [ c₀ c₁ c₂ ] [ x₁ ]
     [ f₃ ]   [ d₀x₀ + d₁x₁ + d₂x₂ ]   [ d₀ d₁ d₂ ] [ x₂ ]
     [ f₄ ]   [ e₀x₀ + e₁x₁ + e₂x₂ ]   [ e₀ e₁ e₂ ]       
                                            A         x   

∂F     ∂f₀ ∂f₁ ∂f₂ ∂f₃ ∂f₄     [ a₀ b₀ c₀ d₀ e₀ ]       
―― = [ ――― ――― ――― ――― ――― ] = [ a₁ b₁ c₁ d₁ e₁ ] = J(F)
∂x     ∂x  ∂x  ∂x  ∂x  ∂x      [ a₂ b₂ c₂ d₂ e₂ ]       
            ∂/∂x A x                   Aᵀ               

∂         T                                  d        
―― A x = A                             --->  ―― ax = a
∂x                                           dx       

∂   T                                        d        
―― A x = A                             --->  ―― ax = a
∂x                                           dx       

∂               T                            d              
―― (A x + b) = A                       --->  ―― (ax + b) = a
∂x                                           dx             

∂   T      ∂    T         T  T   T           d          
―― y A x = ―― (y A) x = (y A) = A y    --->  ―― axy = ay
∂x         ∂x                                dx         

该矩阵是“多函数的一阶导数矩阵 Jacobian Matrix”。但是数学家却定义成此矩阵的转置，应该是古人没想清楚？

范数（长度）

定义长度的平方。向量所有元素的平方总和，等于向量点积。

定义微分连锁律。因为矩阵複合是从右到左，所以连锁律设定成从右到左。

定义长度的平方

     T      def₁: squared norm     2
(A x) (A x) ================== ‖Ax‖ 

定义连锁律

∂      2 def₂: chain rule ∂     ∂       2    T            T   
―― ‖Ax‖  ================ ―― Ax ――― (Ax) = (A )(2Ax) = 2 A A x
∂x                        ∂x    ∂Ax                           

这两个定义的合理性，可由严谨的推导过程证明：
                                            T
∂       T        ∂   T T      ∂   T  T     A A 必定对称    T   
―― (A x) (A x) = ―― x A A x = ―― x (A A) x ============ 2 A A x
∂x               ∂x           ∂x                               

当 A 退化为 I，依然合理：

∂   T    ∂     2  
―― x x = ―― ‖x‖ = 2x
∂x       ∂x       

∂   T    ∂      T       ∂      2     T
―― x x = ―― (Ix) (Ix) = ―― ‖Ix‖ = 2 I I x = 2x
∂x       ∂x             ∂x

范例：Norm Optimization

                 2
minimize ‖Ax - b‖

∂          2
―― ‖Ax - b‖ = 0                     “一次微分等于零”的地方是极值、鞍点
∂x                                   二次函数、开口向上，必是最小值
  ∂
[ ―― (Ax - b) ] [ 2(Ax - b) ] = 0   微分连锁律
  ∂x
 T
A  [ 2(Ax - b) ] = 0                微分

 T       T
A A x = A b                         同除以 2、展开、移项

      T -1 T
x = (A A) A b                       Normal Equation

主要用途是解线性方程组 Ax = b、线性迴归。

范例：Norm Optimization

             2               2
minimize ‖Ax‖  subject to ‖x‖ = 1

             2         2
minimize ‖Ax‖  - λ (‖x‖ - 1)     Lagrange's multiplier

∂        2         2
―― [ ‖Ax‖  - λ (‖x‖ - 1) ] = 0   “一次微分等于零”的地方是极值、鞍点
∂x

   T
2 A A x - 2 λ x = 0              展开

 T                                       T
A A x = λ x                      正解是 A A 最小的特徵值

以上结论是针对求最小值。亦可改成求最大值，结果类似。

主要用途是解线性方程组 Ax = 0、直线拟合。

梯度

函数的梯度（一次微分）：函数对向量微分，得到向量。

函数的梯度的梯度（二次微分）：再次对向量微分，得到矩阵。

     ∂f   [ ∂f/∂x₀ ]
∇f = ―― = [ ∂f/∂x₁ ]
     ∂x   [ ∂f/∂x₂ ]

 2    ∂∇f     ∂(∂f/∂x₀)  ∂(∂f/∂x₁)  ∂(∂f/∂x₂)  
∇ f = ――― = [ ―――――――――  ―――――――――  ――――――――― ]
       ∂x         ∂x         ∂x         ∂x     

            [ ∂²f/∂x₀∂x₀ ∂²f/∂x₁∂x₀ ∂²f/∂x₂∂x₀ ]
          = [ ∂²f/∂x₀∂x₁ ∂²f/∂x₁∂x₁ ∂²f/∂x₂∂x₁ ]
            [ ∂²f/∂x₀∂x₂ ∂²f/∂x₁∂x₂ ∂²f/∂x₂∂x₂ ]

          = H(f) = J(∇f)

该矩阵是“单函数的二阶导数矩阵 Hessian matrix”。

该矩阵恰巧是“多函数的一阶导数矩阵 Jacobian Matrix”代入“函数的梯度”，然而这个观点似乎没有什麽用处。

范例：Newton Method

详情请参考“ Newton Method ”、“ Newton Method ”。

牛顿法求根：从座标(x, f(x)) 的地方画切线，与座标轴相交之处，做为下一个 x。

∇f(x) (x - xnext) = f(x)

牛顿法多函数求根：多个函数形成一个向量。所有函数一齐实施牛顿法求根。
             
Jᵀ(f(x)) (x - xnext) = f(x)

牛顿法求极值：极值（与鞍点）出现在一次微分等于零的地方。
　　　　　　　预先微分，再套用牛顿法多函数求根。

Hᵀ(f(x)) (x - xnext) = ∇f(x)

牛顿法多函数求极值：像这种要求，我这辈子没见过。

Taylor Expansion:
                    1               1          2
f(x + Δx) = f(x) +  ―― f'(x) Δx  +  —— f"(x) Δx  + ...
                    1!              2!

                    1               1
f(x + Δx) = f(x) +  ——   Jᵀ  Δx  +  —— Δxᵀ Hᵀ Δx + ...
                    1!              2!
  n
Δx projects onto basis, which is function gradient.
textbook use different definition. textbook use transpose.

我的 Jacobian Matrix 有别于数学家的版本，因此我的牛顿法、泰勒展开式也有别于数学家的版本。我不知道我的版本是否合理。也许泰勒展开式应该解读成投影？

Positive-definite Matrix / Positive-semidefinite Matrix

“二次型”。x*Ax。

“正定矩阵”。x*Ax > 0，不讨论 x 是零向量。

“正半定矩阵”。x*Ax ≥ 0，不讨论 x 是零向量。

这是仿照多项式函数 ax² > 0 的概念，几何意义是位于 X 轴上方、开口朝上的抛物线。

函数推广到矩阵，输入变数、输出变数可以有很多个。例如两个变数的时候，就是仿照多项式函数 ax² + by² > 0 的概念，几何意义是椭圆。读者吃饱太閒可以複习一下高中数学的圆锥曲线，椭圆（係数为正数、多项式大于零）是其中一种可能性。

二次多项式推广到二次型之后，迸出了“对称”的概念。对称矩阵，几何意义是对称，例如椭圆。非对称矩阵，几何意义是不对称，例如蛋。简单起见，教科书通常只讨论实数对称正定方阵，书上只画了椭圆，没有蛋。

矩阵是线性函数，正定矩阵是线性函数暨凸函数！因此正定矩阵得以设计较快的“ Optimization ”演算法。

A-orthogonal

“矩阵正交”。y*Ax = 0。x*Ay = 0。其中一个成立，另一个就成立。

Ax 与 y 互相垂直；x 经过 A 转换之后，与 y 互相垂直。

知名范例是切线速度与加速度互相垂直，一次微分与二次微分互相垂直。

定义 y 与 Ax 的内积空间，A 必须是对称正定矩阵。内积空间开根号可以定义距离。

【待补文字】

范例：凸函数最佳化

A is symmetric and positive-definite
          T
minimize x A x
              2
subject to ‖x‖ = 1

          T             2
minimize x A x - λ ( ‖x‖ - 1 )     Lagrange multiplier

∂     T             2
―― [ x A x - λ ( ‖x‖ - 1 ) ] = 0   “一次微分等于零”的地方是极值、鞍点
∂x                                  二次型，必为极值

2 A x - 2 λ x = 0                  展开

A x = λ x                          移项，形成特徵向量的格式

答案是最小的特徵值的特徵向量！

值得一提的是，x*Ax = proj_x Ax。当 x 是 A 的特徵向量，则 x*Ax 就是特徵值。

矩阵是线性函数，其特色是特徵向量不变。对称正定矩阵是线性函数暨对称凸函数，其特色是最大值、最小值位于最大的、最小的特徵向量。

http://freemind.pluskid.org/machine-learning/projected-gradient-method-and-lasso/
http://www.stats.ox.ac.uk/~lienart/blog_opti_pgd.html
n->n 函数最佳化，其实就是求特徵值？这是 power iteration？

范例：Norm Optimization

given X and Y. find A.
          T
maximize Y A X
            T
subject to A A = I   (A is othronormal)

             T            T           T         T
minimize tr(Y AX) = tr(AXY ) = tr(AUΣV ) = tr(ΣV AU)

   T
(XY is covariance matrix between dimensions)

                         T
A V U is othronormal => V AU is othronormal

 T
V AU = I  (diagonal elements are all +1)
       T
A = V U

   2      T
‖A‖ = tr(A A)

tr(AB) = tr(BA)

范例：Norm Optimization

given X and Y. find A.
          T
maximize Y A X
            T
subject to A A = I   (A is othronormal)

max tr( Q D )

令 Q = I 以得到最大值

2-norm best projection -> 1-norm best eigenvalue。

PCA  min Frobenius norm >>> min sqrt( trace(At A) )
     min 2-norm of sigular values
PCS  min nuclear norm >>> min trace( sqrt(At A) )
     min 1-norm of singular values

Matrix Polynomial（Under Construction!）

Cayley-Hamilton Theorem

特徵值，就是根！

Minimal Polynomial

“最小多项式”。

Companion Matrix

“共伴矩阵”。

basis is Krylov matrix.
change to companion matrix.

http://homepages.laas.fr/henrion/aime@cz11/kukelova.pdf

多项式的根 ---> companion matrix 的特徵值
递迴多项式 ---> companion matrix 的次方
递迴多项式的公式解 ---> eigendecomposition

Nilpotent Matrix

“幂零矩阵”。A^k = 0。

Linear Recurrence

Recursive Function

递迴函数就是同一个函数複合好几次！

A recursive function f:
f(0) = 5
f(x) = 2 * f(x-1) + 1

Let g(y) = 2 * y + 1
f(0) = 5
f(1) = g(5)
f(2) = g(g(5))
f(3) = g(g(g(5)))

Linear Recurrence

线性递迴函数就是同一个线性函数複合好几次。

{ f(n) = a1 * f(n-1) + a2 * f(n-2) + ... + ak * f(n-k)   when n > k
{ f(k) = ck
{   :     :
{ f(2) = c2
{ f(1) = c1

著名的例子是 Fibonacci Sequence：仅两项，係数皆是 1。

{ f(n) = f(n-1) + f(n-2)   when n = 3, 4, 5, .....
{ f(2) = 1
{ f(1) = 1

{ f(1) = 1
{ f(2) = 1
{ f(3) = f(2) + f(1)
{ f(4) = f(3) + f(2)
{ f(5) = f(4) + f(3)
{   :      :      :

【注：recursion 和 recurrence，中文都翻译为“递迴”，然而两者意义大不相同，读者切莫混淆。】

演算法（Dynamic Programming）

由小到大一项一项慢慢算。採用“ 动态规划 ”，有许多种实作方式。时间複杂度为 O(N + (N-K) * K)，可以简单写成 O(NK)。

Linear Algebra

Linear Algebra

数学家重视性质，以函数的加法性、函数的倍率性来定义“线性变换”。

计算学家重视数值，本站以变数的加减、变数的倍率的角度来介绍“线性变换”。

儘管本站的介绍方式比较直觉，却是非常偏颇的介绍方式。为了端正视听，以下简述数学家的介绍方式。完全是另外一种世界观。

Vector Space

“向量空间”由一个集合、两个运算组成。两个运算分别是加法运算、倍率运算。

集合，可以设定成实数、整数、馀数、多项式、向量、函数、……。

加法运算、倍率运算，泛指一切适当的运算。例如在实数当中，可以设定成实数加法与实数倍率，也可以设定成实数乘法与实数次方。设定方式通常不只一种。

为了釐清加法运算与倍率运算的责任，数学家做了详细规定：

向量空间之加法运算的规定
1. Associativity 加法结合律
   u + (v + w) = (u + v) + w
2. Commutativity 加法交换律
   u + v = v + u
3. Identity element 加法单位元素
   v + 0 = v
4. Inverse element 加法反元素（负数与减法）
   v + (−v) = 0

向量空间之倍率运算的规定
5. Associativity 倍率结合律
   a ⋅ (b ⋅ v) = (a ⋅ b) ⋅ v
6. Distributivity of vector sum 倍率分配律，针对向量部分
   a ⋅ (u + v) = (a ⋅ u) + (a ⋅ v)
7. Distributivity of scalar sum 倍率分配律，针对倍率部分
   (a + b) ⋅ v = (a ⋅ v) + (b ⋅ v)
8. Identity element 倍率单位元素
   1 ⋅ v = v

符号 uvw0，代表数值，向量空间的集合的元素；符号 ab1，代表倍率，体的集合的元素；符号 01，泛指符合规定的元素，而且至少要有一个、必须存在。集合当中所有元素的所有配对方式，必须符合所有规定。

倍率运算的倍率，通常设定成“体 field”。体由一个集合、两个运算组成。两个运算分别是加法运算、乘法运算。数学家也做了详细规定，不过此处省略。

例如集合设定成多项式，加法运算设定成多项式加法，倍率运算设定成多项式倍率；倍率的集合设定成实数，倍率的加法运算设定成实数加法，倍率的乘法运算设定成实数乘法；0 是零多项式，1 是实数 1。

顺带一提，此例的 0 与 1 刚好是单一元素，而且非常直觉；但是当集合设定成其他特殊的集合，0 与 1 就可能有多种元素。

向量空间的重点在于加法运算与倍率运算，真要取名的话也该叫做“加倍空间”。不过由于加法、倍率很容易联想到向量，所以才取名“向量空间”。

Vector Space 实际范例

举一个比较複杂的例子。

向量空间                  倍率运算的倍率，通常是体
集合　　 --> 馀数 mod 7   集合　　 --> 整数　　（可以推广至馀数 mod ɸ(7)）
加法运算 --> 馀数乘法     加法运算 --> 整数加法
倍率运算 --> 馀数次方     乘法运算 --> 整数乘法

向量空间之加法运算的规定         (u = 2, v = 3, w = 4, a = 5, b = 6)
1. u + (v + w) = (u + v) + w  |  2 × (3 × 4) ≡ (2 × 3) × 4
2. u + v = v + u              |  2 × 3 ≡ 3 × 2
3. v + 0 = v                  |  3 × 1 ≡ 3           符号 0 设定成馀数 1
4. v + (-v) = 0               |  3 × 3 ≡ 3 × 5 ≡ 1   倒数

向量空间之倍率运算的规定
5. a(bv) = (ab)v              |  (2 ^ 6) ^ 5 ≡ 2 ^ (5 × 6)
6. a(u + v) = au + av         |  (2 × 3) ^ 5 ≡ (2 ^ 5) × (3 ^ 5)
7. (a + b)v = av + bv         |  3 ^ (5 + 6) ≡ (3 ^ 5) × (3 ^ 6)
8. 1v = v                     |  3 ^ 1 ≡ 3           符号 1 设定成整数 1

Inner Product Space

“内积空间”由一个集合以及三个运算组成。三个运算分别是加法运算、倍率运算、内积运算。

内积运算，泛指一切适当的运算。例如集合设定成向量、加法运算设定成向量加法、倍率运算设定成向量倍率，那麽内积运算可以设定成向量点积（dot product）。

为了釐清内积运算的责任，数学家做了详细规定：

内积空间之内积运算的规定
9.  Linearity: Additivity 加法性（加法分配律）
    (u + v) ∙ w = (u ∙ w) + (v ∙ w)
10. Linearity: Homogeneity of degree 1 倍率性（倍率结合律）
    (au) ∙ w = a(u ∙ w)
11. Commutativity 内积交换律
    u ∙ v = v ∙ u
12. Positive-definiteness 正定
    u ∙ u ≥ 0
    u ∙ u = 0 iff u = 0 (orthogonality)

内积空间真要取名的话也该叫做“加倍内空间”，不过这名称有点拗口。

内积空间是向量空间的延伸版本。数学家之所以发明内积空间，是因为有了内积运算之后，可以引入长度和角度的概念。

“norm 范数”泛指一切“与自身内积、再开根号”的情况。如果集合设定成向量，内积运算设定成向量点积，那麽范数是指向量长度。

“orthogonality 正交”泛指一切“内积等于零”的情况。如果採用方才的设定，那麽正交是指垂直。

Basis / Coordinate

向量空间当中，可以选定一组适当座标轴（基底）：座标轴互相“线性独立 linear independent”、座标轴数量（维度）足以生成所有元素。符合条件的座标轴有无限多组。

选定一组适当座标轴之后，座标轴各自利用倍率运算进行缩放，然后利用加法运算进行合成，就可以得到向量空间当中每一个元素。得到一个数值的过程称作“线性组合 linear combination”，得到所有数值的过程称作“生成 span”。

反过来说，选定一组适当座标轴之后，向量空间当中的每一个元素，可以利用分量的概念，分散到每个座标轴上，得到一个座标。每一个元素各自拥有独一无二的座标。

Linearity

函数的加法性 additive function:
y1 = f(x1)
y2 = f(x2)              additive
y1 + y2 = f(x1) + f(x2) ======== f(x1 + x2)

y1 = A x1
y2 = A x2             additive
y1 + y2 = A x1 + A x2 ======== A (x1 + x2)

函数的倍率性 homogeneous function of degree 1:
y = f(x)         homogeneous
y ⋅ k = f(x) ⋅ k =========== f(x ⋅ k)

y = A x           homogeneous
y ⋅ k = (A x) ⋅ k =========== A ⋅ (x ⋅ k)

加法性：先相加再变换，等于先变换再相加。

倍率性：先乘上倍率再变换，等于先变换再乘上倍率。

两者合称“线性”。

Linear Transformation

线性变换是一个函数，输入输出不限（此处是向量空间），函数必须具备线性，也就是加法性、倍率性。

先前是以变数的加法、变数的倍率来组成线性变换，其实这只是一个直觉的特例。实数相加是一个线性变换，实数乘上倍率是一个线性变换。两者乱组一通仍是线性变换（多个线性变换複合之后还是线性变换）。

事实上，还有其他的线性变换，无法用变数的加法、变数的倍率表示，例如函数微分、函数积分。

Matrix

linear transformation t: V -> W
v ∈ V   basis of V: {v1, v2, ..., vN}   coordinate of v: {x1, x2, ..., xN}
w ∈ W   basis of W: {w1, w2, ..., wN}   coordinate of w: {y1, y2, ..., yN}

linear combination:
x1v1 + x2v2 + ... + xNvN

linear transformation:
w = t(v)
  = t(x1v1 + x2v2 + ... + xNvN)
  = x1 t(v1) + x2 t(v2) + ... + xN t(vN)      "linearity"
  = x1 w1    + x2 w2    + ... + xN wN

matrix representation of linear transformation: y = M x
[ | ]   [   |     |     |         |  ] [ | ]   [  |  |  |      | ] [ | ]
[ y ] = [ t(v1) t(v2) t(v3) ... t(vN)] [ x ] = [ w1 w2 w3 ... wN ] [ x ]
[ | ]   [   |     |     |         |  ] [ | ]   [  |  |  |      | ] [ | ]

线性变换，是座标轴的线性组合、再实施变换；由于加法性、倍率性，又恰好是座标轴实施变换、再线性组合。

也就是说，线性变换是座标不变、座标轴改变。这件事可以写成矩阵乘法的格式。

当输入部分的座标轴 V，设定为标准座标轴，那麽矩阵 M 就是先前谈的线性变换矩阵，输出部分的座标轴 W 就是先前谈的座标轴。先前谈的只是一个直觉的特例。事实上，输入输出各自拥有座标轴，座标轴有无限多种选择，随便一种都行。

Change of Basis

更换输入部分的座标轴 V。就这样而已。

输出部分的座标轴 W，就是先前谈的相似矩阵。输入部分的座标轴 V，就是先前谈的座标轴，可以採用特徵基底、也可以採用任意基底。

抽象化

汽车、货车、公车、联结车，泛称为“车”。由实际名称变成泛称的这个过程，叫做抽象化。

数学家非常喜欢抽象化。上述名词，诸如加法运算、倍率运算、向量空间、线性变换、正交，都是泛称，都是经过抽象化的名称。