1. int getNumOfLeastColors(set<int>& colorSet) {// 求二进制矩阵的秩，即消元，最后看斜对角线上有几个 1  
2. 
   

学数值计算还有复变函数了喔，矩阵忘干净了。又看了一遍 蓝棕 的相关的讲解，总结一下。

1.向量是什么？

• 从初到末的箭头（物理角度，表示一种运动过程）
• 有序的数字列表（计算机/数学角度）[1,2]
• 加和数乘运算有意义的anything（抽象意义）

12两种理解之间的关系就是线性代数的奥秘，即几何角度与数值角度。

一个向量的坐标由一对数构成，可以理解为从原点到终点的箭头，描述运动过程。

比如，规定好坐标平面的单位，[1,2]，第一个数表示沿x轴走了1个单位；第二个数表示沿y轴走了2个单位。从原点出发的箭头和坐标向量一一对应。

向量的相加和数乘，从1运动效果的角度来看，十分直观。即总效果等于各个分量上的效果和，所以向量的相加和数乘可以变为坐标运算。

2.线性组合，张成空间与基

向量的另一种理解：缩放分量并且相加，它表示一种变换。例如在正交基

下，[3,2]表示的变化为i伸长为原来的三倍，j伸长为原来的2倍，最后把两者相加。在这种理解下，基向量其实就是用来缩放的对象。

以

为基，在

的拉伸下表示向量

,我们把这叫做线性组合，线性的意思即固定其中一个参数，拉伸后的向量始终在一条直线上移动，如图。

所有可以表示为给定向量线性组合（通过向量加法和数乘能得到）的向量的集合叫，张成空间。

当新增一个向量，这个向量落在之前的向量的张成空间时，我们说新增向量没有对张成空间做出任何贡献，称这几个向量是线性相关的，代数上理解即新增向量可以被线性表出。

向量空间的一组基是张成该空间的一个线性无关的向量集。

此处可以想一下三维空间是如何张成的。

为了更简洁的表示更多的向量，我们可以以终点代替箭头来表示向量。

3.矩阵与空间变换

变换的意思类似函数，给定一个向量，输出一个向量。

线性变换需要满足：直线变换后仍保持为直线，不能有所弯曲；原点必须固定不变。

直观上理解：坐标网格线保持平行且等距分布。

如何表示变换呢？只要描述基的变换就可以了，即描述

变换后去哪了。如图。

只要知道

去哪了，我们可以推断出任何向量变换后的位置。

所以，二维空间中，描述一个变换只要4个数，即

变化后的两个坐标。我们将这两个坐标放在一个2×2的方格中，称为2×2矩阵。这种理解与之前向量表示缩放基向量再相加的思想很契合！

举个栗子！再次感受一下矩阵变换的过程！

如果变换后的两个向量落在一条直线上，那么这两个向量会张成一个一维空间

注意此时的矩阵只是一个记号，它表示一种线性变换。

我们规定一种写法，用向量在右，矩阵在左来表示这种变换。

讲到这里，变换的内容就描述完了。下面想想几个常见变换的矩阵表示~~

• 逆时针旋转90度
• 剪切变换

要记住，矩阵，是描述变换的。

4.矩阵乘法与线性变换复合的联系

两次变换---复合变换的表示

例子是，先逆时针再剪切变换，

,即

由此，我们定义矩阵的乘积

，从右向左读。

可是，矩阵的运算法则是怎么来的呢？对于复合变换

我们首先考虑

的变化过程 ：

再考虑

的变化过程：

所以，从变换的效果来看，我们得到了矩阵的运算法则，即

这种变换效果的理解过程也很好的说明了，为什么矩阵不满足交换律，满足结合律。

交换律改变了作用顺序，而结合律不会。

推广到三维，

同理

5.行列式的介绍及其几何意义

我们发现，有的变化对空间有拉伸作用，有的是压缩作用。

我们从

所在单位正方形来看面积的变化比例，就能知道其他任意区域的面积变化比例（网格线平行等距的原因）

这个特殊的缩放比例，被称作行列式。比如

,说明面积不缩放。

行列式为负值时，表示变换改变了空间的顺逆方向。想像一个变换，变换过程中

不断接近直至重合，又远离，行列式由正值不断趋于0然后再变为负值是很自然的。从二维的角度看，即看

变换后两者的左右颠倒了没。（类比角速度方向，右手法则）

而行列式等于0时，如

表示线性变换将空间压缩到一条线（甚至是一个点）上。这告诉我们，只要看行列式就能了解矩阵所代表的的变换是否将空间压到更小的维度上。

推广到三维，即体积的变化缩放比例（方向的话，伸出你的三维小鸡爪，类比手性系）。

问题是，行列式是如何计算的呢？

二维情形下，如果有一个元素值为零。从伸缩角度很好的能理解，如下图：

如果都不为零的话，稍稍复杂一丢丢，也很好懂。

这种对行列式的理解也从作用效果说明了，为什么

6.逆矩阵，列空间，秩与零空间等概念的直观介绍

线性方程组来了。

从变换的角度来理解这个方程组：

，that is，我们需要找一个向量x，使得x经A变换后的向量与v重合。

首先考虑变换矩阵A的行列式:

1）行列式不为零时，在线性变换下，网格平行等距，变换前的点和变换后的点在坐标平面上是一一对应的，通俗的理解就是可以变过去，也可以再变回来的。由v到x变回来的矩阵通常被称为A的逆，记为

。从效果上理解，

知道了A的逆，我们就可以解方程了

(几何理解即逆向变化，看v跑到哪里了）推广到多维同样

只要行列式不为零，都能找到逆矩阵，都可这样解。

2）行列式为零时，压缩后不能解压。不能一对多。但即使不存在逆变换，解仍然可能存在。

如果v恰好在x变换后的线上，解存在。

但对于三维来说，变换压到一个面和一条线行列式都为零。太广泛。所以引入秩的概念。

当变换的结果为一条直线时，结果是一维的，我们称这个变换的秩为1；

变换后的结果为一个面时，压缩并没有那么严重，秩为2；

变换后仍充满整个空间的，秩为3。

所以说，秩代表着变换后列空间的维数。而变换后基向量的张成空间就是所有可能的变换结果。

零向量一定在变换后的空间中，对于非满秩矩阵来说，会有一系列向量被压缩到原点；变换后落在原点的向量，被称为矩阵的“零空间”或“核”，也就是v是零向量时方程的所有的解的集合。

非方阵矩阵的理解：考虑输入与输出个数。

当输入二维，输出为三维时，如变换矩阵

，两个列向量为变换后的张成空间的基。只能张成一个平面，此时的三维是伪三维。

当输入三维，输出二维时，如变换矩阵

，降维。

其实还有从二维到一维的变换，判断变换是不是线性的很直观的方法是，看原来直线上等距分布的点，变换后是不是还是保持直线的等距分布。这句话很重要，接下来将用到。

7.点积与对偶性

我们知道，如果有两个长度相同的向量，求他们的点积就是把各分量相乘再把结果相加。

点积还有一个形象的意义，就是将其中一个向量投影的长度与另一个向量做数乘。

点积为什么会和投影有关呢？为什么几何定义一个向另一个作投影这件事看起来没有那么对称，但其实点乘结果与向量顺序无关？

首先，先搞明白，点积的几何理解其实是对称的。

如果两个向量的长度恰好相同，那么利用对称性可知，两者在彼此上的投影数量都相同。

现在我们把其中一个变做原来的k倍。单位长度的两个向量仍然具有对称性。而投影数量是单位向量投影数量的k倍，把倍数最后乘上即可。

所以，缩放对于两个向量的影响最后作用到点积，效果是完全一样的。

下面来探究点积与投影的关系。

我们首先来看一个矩阵线性变换的例子，

,把i变换成数轴上的1，j变为数轴上的-2，运算结果为-2。

我们发现

左边从矩阵的角度来理解，是一种数值运算，但是和右边点积的运算过程一样。

如果投影能和1×2矩阵变换建立几何联系，由于坐标运算与点积运算形式上一样，我们就能搞清楚点积与投影之间的关系了。

首先，由于投影变换下，直线上等距分布的点投影到向量上仍然等距，所以投影变换是线性变换，可以用一个1×2矩阵来描述。求这个矩阵，由几何解释，我们只需要知道原来的

投影到这个向量上的两个坐标值就可以了。

神奇的地方出现了！由对称性，

投影到向量

上的坐标值等于

在

上投影的坐标值。即投影变换为

,而

恰好是

向量的转置！

所以，向量在

上的投影数值上等于

和那个向量的点积！精彩！

8.叉积及其几何意义

我们都知道，叉积的数值表示面积，体积，whatever。

正负与叉乘的顺序有关。二维为例，逆时针为正。

我们首先定义，叉积运算的结果的大小是有向面积。

所以二维向量的叉乘积是两个向量组成矩阵的行列式，也就是原来的

所在单位正方形变换后的面积。正负也很契合。

也不难看出

不过，其实真正的叉积其实是通过两个三维中的向量生成一个新的三维向量，

向量的长度是平行四边形的面积，方向与

所在的平行四边形的面垂直，遵循右手法则（食指×中指=拇指！）

计算叉积时，我们有一个运算的小技巧，如下图

这个技巧是咋来的呢？

首先，由前几部分的内容可知，从空间到数轴的线性变换都可以由一个一行的矩阵实现，emm也与点积相同。

证明思路：

1）定义一个由三维到一维的线性变换

2）找到那个一行的矩阵（或是对偶向量）

3）说明那个一行的向量就是

由二维的“假叉积”，我们很容易想到，三维中的行列式代表体积，也就是体积伸缩的比例，是不是三维叉积的结果是

呢？

显然不是，行列式是一个数，而叉积的结果是向量。

那如果稍稍改动一下呢？

把行列式其中一列变为变量，得到

于是我们得到了一个输入为三维，输出为一维的变换，形象上理解就是得到了一个函数，这个函数能计算以vw为底，自变量为高的平行六面体的体积。很显然，这个函数是线性的，用矩阵来描述这个函数

把行列式两项展开，与点积展开式作比较，就能得到p的分量的计算方法了。

这与把i，j，k放进行列式的结果一致。

如果能证明这个p向量是v×w的话，就证毕了。

下面我们考虑，什么样的p能满足以上的性质呢？

我们知道，一方面，点积的作用是做投影相乘。把 （

在p上投影）

另一方面，行列式表示体积，大小为vw的面积乘上 （

在垂直于vw上的投影）

所以从这两方面相等的角度来看，p的大小应该是vw的面积，方向是垂直于vw所在平面的，也就是v×w。

至此，我们证明了，p的分量就是v×w。

Q.E.D 开森

9.基变换的概念及其矩阵表示

我们之前提到，坐标的意义是缩放基向量，然后再将所有的方向的结果相加。

所以，坐标表示的向量与被缩放的基向量的选取有密切的联系。也就是说，在我们用坐标表示向量时，首先需要明确缩放的基向量的指向，还要求基向量为单位长度。

试想，除了选互相垂直相等的基向量，我们还可以有许许多多奇怪的选法。选法不同，表示同样的向量，我们的坐标肯定也不一样。向量与坐标之间的转化通过选取坐标系实现。

这就像每个世界里都有每个世界的描述东西的语言（坐标，也就是数组），语言不同但是描述的东西（向量）可能相同。（注意奥，这里不同的世界在零点的选取上达成共识。

例如，想象小红的世界里，两个基向量

呈钝角。可是小红用坐标描述

的时候，在她眼里，由缩放相加的思想，两个基向量的坐标就是

可是想象小蓝的世界里，他的基向量选取的是互相垂直的

。用小蓝的坐标描述同样的

，坐标变为了

既然语言不通，接下来一个很自然的问题就是，如何在不同的坐标系之间进行转化。如何进行翻译，让小红和小蓝能够互相理解呢？

比如小红用坐标

描述一个向量时，她是在说

从小蓝的角度看，

的坐标为

，

的坐标为

于是

由红语翻译到蓝语就是

我们来看一下这个过程发生了什么：我们用某个给定的坐标分量与小红的两个基向量分别相乘，然后又把结果相加了。，这通操作是不是似曾相识？对，是矩阵乘法。

众所周知，矩阵是表示变换的。那么从变换的角度，我们再来理解一下这个过程。

小蓝视角（以下坐标与变换矩阵基于小蓝视角表示）：

小红基向量构成的矩阵

表示的变换是将小蓝的基向量

,

变到小红的基向量

,

。

这里注意：由于线性变换是不改变缩放系数的，我们只描述基向量的变化后的去向，而不改变基向量缩放相加的组合系数。（也可以理解成，从前后两个视角看，线性变换不改变坐标。就是从变换前小蓝眼中的坐标，和变换后小红眼中的坐标是一样的。

小蓝尝试理解

坐标在小红的世界里表示什么。小蓝首先想自己的世界里的

，然后用用变换得到小红眼中的

，这个变换后的向量就是小蓝视角下小红的向量表示。于是，翻译完成！

这个矩阵，将小红语言描述的向量坐标，也就是小蓝误解的向量坐标，翻译成了小蓝能正确get到的真实向量坐标。

上图看起来感觉反了。怎么小红的语言通过 蓝到红的矩阵反倒变成了 小蓝的语言呢？

这样想矛盾的原因在于，这几个表示的视角不统一。一会小蓝眼中一会小红眼中。

我们应该把

当做小蓝眼中的误解，而不是小红眼中真实，小蓝的误解向量乘上小蓝眼中的变换矩阵，把小蓝眼中误解的变成小蓝眼中真实的。这样想运算过程小蓝视角才是统一的。

我个人习惯于这样理解：

这个矩阵是以小蓝为基向量表示的，任何别的基下的坐标乘上这个矩阵得到的缩放系数是以小蓝为基向量的，于是乘上之后说的就是蓝语。

同样的，想由蓝语翻红语，我们只需要乘上

的逆。

至此，不同坐标系下单个向量的转化已经完成。下面我们来解决不同坐标系下，描述变换的矩阵之间是如何转化的。

比如，小蓝眼中的逆时针旋转90度变换

，在小红眼中是如何表示的呢？

由于两个列向量追踪的是

的去向，显然小红眼中的变换矩阵并不是

我们还拿小红眼中

这个向量做变换。很自然的思路是，首先将红语翻蓝语，作变换，再将蓝语翻回红语，于是变换后应为

所以，左边三个矩阵的复合应该就是小红眼中的变换矩阵！

，嘿嘿，这就是相似矩阵。所以说相似矩阵同一种变换在不同基下的表示。

这个矩阵不同视角的变换在下一部分大有用处！

10.特征向量与特征值

试想一个普通的线性变换

，设

吧。绝大部分向量在变换后都偏离了原来的位置，但是会有特殊的

，使得变换后的向量还是在原来向量的直线上。这时矩阵对它的作用仅仅是拉伸或者压缩而已，如同一个标量。

在这个例子里，

就是这样一个特殊的向量，变换后被伸长3倍。与

共线的向量也如此。

其实还有一个比较隐蔽的向量

，被拉长为2倍。

这些特殊的向量就被称为变换的特征向量，每个特征向量都有一个拉伸的倍数，被称作特征值。特征值为负时表示变换后的向量与原向量反向。

特征向量有什么应用呢？比如描述3维空间中的旋转变换，显然特征值为1。什么样的向量是变换前后不变的呢？只有旋转轴上的向量。把三维旋转看成绕某个轴旋转一定角度，比矩阵描述直观的多。

下面看看特征向量怎么求。

其实是由

，解出来特征向量和特征值。

首先把右侧的数乘用变换表示，即

,整理得

这个式子恒成立，说明这个变换降维了。而空间压缩对应的就是矩阵的行列式为零

，

均可解。

不过，二维变换不一定都有特征向量，比如旋转90度变换。（其实是特征值为复数，深入讨论可把复数理解为变换）

特征值也可以有无数个，比如

华点来了，我们引入特征基的概念。

如果我们的基向量恰好是特征向量，变换矩阵就会是一个对角矩阵，矩阵的对角元是它们所属的特征值。这时是变换就只是横竖方向改变坐标网格的大小了。

对角矩阵在很多运算中都有很好的性质，比如和自己多次相乘的结果更容易计算，只是对角元不断的乘自己。

但是基向量恰好为特征向量的情况很难遇到。结合上一part内容，我们尝试换基。

如果特征向量能够张成全空间，我们就可以变换坐标系使得这些特征向量就是基向量。

啊这就是相似对角化。

11.抽象向量空间（有点超纲，最近好忙周一更）