Menu

  • Home
  • Work
    • Cloud
      • Virtualization
      • IaaS
      • PaaS
    • Java
    • Go
    • C
    • C++
    • JavaScript
    • PHP
    • Python
    • Architecture
    • Others
      • Assembly
      • Ruby
      • Perl
      • Lua
      • Rust
      • XML
      • Network
      • IoT
      • GIS
      • Algorithm
      • AI
      • Math
      • RE
      • Graphic
    • OS
      • Linux
      • Windows
      • Mac OS X
    • BigData
    • Database
      • MySQL
      • Oracle
    • Mobile
      • Android
      • IOS
    • Web
      • HTML
      • CSS
  • Life
    • Cooking
    • Travel
    • Gardening
  • Gallery
  • Video
  • Music
  • Essay
  • Home
  • Work
    • Cloud
      • Virtualization
      • IaaS
      • PaaS
    • Java
    • Go
    • C
    • C++
    • JavaScript
    • PHP
    • Python
    • Architecture
    • Others
      • Assembly
      • Ruby
      • Perl
      • Lua
      • Rust
      • XML
      • Network
      • IoT
      • GIS
      • Algorithm
      • AI
      • Math
      • RE
      • Graphic
    • OS
      • Linux
      • Windows
      • Mac OS X
    • BigData
    • Database
      • MySQL
      • Oracle
    • Mobile
      • Android
      • IOS
    • Web
      • HTML
      • CSS
  • Life
    • Cooking
    • Travel
    • Gardening
  • Gallery
  • Video
  • Music
  • Essay

线性代数学习笔记

1
Dec
2019

线性代数学习笔记

By Alex
/ in Math
0 Comments
方程组的几何解释

方程组(Simultaneous Equations,联立方程):

\[\begin{cases}2x - y = 0 \\-x+2y = 3 \end{cases}\]

在线性代数中,常常表示为:\(\mathbf{A} \mathbf{x} = \mathbf{b}\)。其中\(\mathbf{A}\)表示它的系数矩阵(Coefficient Matrix),是如下形式的矩形元素排列:\(\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}\),x则是未知数向量:\(\begin{bmatrix} x \\ y \end{bmatrix}\),b也是一个向量。上述方程组展开的矩阵记法为:

\[{\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}\cdot {\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}0\\3\end{bmatrix}}\]
行图像

所谓行图像(Row Picture),就是在坐标系中绘制出每个方程的图像,从几何角度来解释方程组的含义。

很明显,每个方程的全部根(解,Solution)都构成一条直线,两条直线的交点即为方程组的根。根可能有0个(直线平行)、1个(直线相交)、无数(直线重合)。

推广到三元方程组的情况,三个方程,每个方程对应到三维空间的一个平面,三个平面的交点即为方程组的根。根同样可能有0个(任意两个平面平行)、1个(三平面相交)、无数(三平面交于同一直线,或者三平面重合)。

列图像

所谓列图像(Column Picture),则纵向的看方程组。两个方程未知数x的系数构成向量\(\begin{bmatrix} 2  \\ -1 \end{bmatrix}\),未知数y的系数则构成向量\(\begin{bmatrix} -1 \\  2 \end{bmatrix}\)。方程组可以改写为如下形式:

\[x\begin{bmatrix} 2  \\ -1 \end{bmatrix} + y\begin{bmatrix} -1 \\  2 \end{bmatrix} = \begin{bmatrix}0\\3\end{bmatrix}\]

上述等式的意义是什么?它是要寻找左侧两个向量的正确的线性组合(Linear Combination)——每个向量乘以一个系数,再相加 —— 以产生右侧的向量。我们这里暂时不讨论如何求解线性组合,通过解二元一次方程组可以得到x,y分别为1,2。在坐标系中绘制向量图像(向量加法、乘法),其结果恰恰是右侧向量。

1个x向量和2个y向量的线性组合,得到右侧的那个特殊的向量。那么,x向量和y向量的任意、全部线性组合,会得到什么呢?其结果向量会覆盖整个坐标平面。

那么,是否任意两个向量的全部线性组合都满足上述性质呢?也就是说,对于任意矩阵A,是否能找到一个向量b进行线性组合,获得任意向量x?并非如此,如果向量x和y的方向相同,不论怎么组合,其结果向量的方向无法改变,因而不可能覆盖整个坐标平面。回到行图像的角度,两个向量方向相同的情况如下:

\[\begin{cases}a (x + y) = A \\b (x + y) = B \end{cases}\]

很明显,不考虑 $x = -y$的特殊情况,$x,y$的取值不会对$A/B$的比值产生影响。

推广到三维或者更高维的空间,上述讨论结果依然适用。

Ax=b

这个表示法是方程组的矩阵形式。 \(\mathbf{A} \mathbf{x}\)是矩阵乘以一个向量,这种乘法的结果仍然是一个向量\( \mathbf{b}\)。

那么矩阵和向量的乘法如何进行?有两种方式。考虑下面的矩阵和向量:

\[{\begin{bmatrix}2&5\\1&3\end{bmatrix}} {\begin{bmatrix}1\\2\end{bmatrix}}\]

方法一,将\(\mathbf{A} \mathbf{x}\)看作A的每个列的线性组合。每次处理一列,1个第一列 & 2个第二列的线性组合,即:\[1\begin{bmatrix} 2  \\ 1 \end{bmatrix} + 2\begin{bmatrix} 5 \\  3 \end{bmatrix} = \begin{bmatrix}12\\7\end{bmatrix}\]

方法二,每次处理一行,第一行点乘(Dot Product)向量 + 第二行点乘向量,即:\[\begin{array}{l}{\left[\begin{array}{cc}{2} & {5}\end{array}\right] \cdot\left[\begin{array}{cc}{1} & {2}\end{array}\right]= [ 2 \times 1 + 5 \times 2]= 2x+ 5y =12} \\ {\left[\begin{array}{cc}{1} & {3}\end{array}\right] \cdot\left[\begin{array}{cc}{1} & {2}\end{array}\right]=[1 \times 1 + 3 \times 2 ]= 1x + 3y =7}\end{array}\]

矩阵消元

解线性方程组最直接的方法是消元法(Elimination),这也是计算机程序使用的方法。矩阵变换(Matrix Operations)是线性代数的核心,因此本课用矩阵语言来描述消元法。

理想情况

考虑下面的三元方程组:

\[\begin{array}{r}{x+2 y+z=2} \\ {3 x+8 y+z=12} \\ {4 y+z=2}\end{array}\]

它的系数矩阵是3x3的矩阵:

\[\begin{array}{ccc}{1} & {2} & {1} \\ {3} & {8} & {1} \\ {0} & {4} & {1} \\ {} & {A} & {}\end{array}\]

回顾一下初中学习的消元法 —— 将第一个方程乘以一个适当的数,然后和第二个方程相减,达到消除一个元\(x\)的目的。用同样的方法消除元\(y\),即可解得\(z\)。

现在用矩阵语言来描述,首先选择左上角的1为主元(First Pivot,主元不能为0),与方程中的x系数对应,它的消元乘数为3。用第二行减它,保持主元行不变,矩阵变为:

\[\begin{array}{lll}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {4} & {1}\end{array}\]

这里暂时不去管右侧向量\(b\)。

现在,第二行的x元被消除了。下一步需要消除第三行的,但是已经是0了,不需要处理。

下一步,处理主元二(Second Pivot)。看第二、第三行,相当于二元方程组,主元选取第二行的y。乘以消元乘数-2,用第三行减去第二行,消除y。得到:

\[\begin{array}{lll}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {0} & {5}\end{array}\]

现在我们得到了三个主元 \(1, 2, 5\),现在的矩阵叫上三角(Upper Triangular)矩阵,记作\(U\)。消元的目的就是从\(A\)得到\(U\) —— 这是科学计算中最普遍的运算。

随便提一下行列式(Determinant),它是主元之积,这里它等于10。

失败情况

什么情况下,无法得到三个主元?

如果第一行的x为0,怎么办?交换行即可,将第1行换到第2行 —— 主元的位置被0占据则需要换行。

如果主元位置为0,并且后面没有行的这个位置非零,则没法换 —— 这意味着方程组无解,矩阵不可逆(Not Invertible)。

回代

前面一直没有考虑右侧向量\(b\)。我们把它作为系数矩阵的新一列,得到增广矩阵(Augmented Matrix):

\[\begin{array}{ccc}{1} & {2} & {1}  & {2} \\ {3} & {8} & {1}  & {12} \\ {0} & {4} & {1} & {2} \end{array}\]

在消元的时候,右侧向量会跟着同步变化。重复上上小节的消元过程,可以得到:

\[\begin{array}{lll}{1} & {2} & {1} & {2}  \\ {0} & {2} & {-2} & {6}  \\ {0} & {0} & {5} & {-10} \end{array}\]

最后得到的右侧向量称作\(c\)。到此消元过程结束,方程组变为:

\[\begin{aligned} x+2 y+z &=2 \\ 2 y-2 z &=6 \\ 5 z &=-10 \end{aligned}\]

从最后一个方程逐步回代,即可求解。

消元矩阵

在第一课中,我们用向量思维理解了矩阵乘法 —— 一个矩阵,乘以列向量,可以把矩阵的每列看做列向量,然后对对这些向量进行线性组合,其结果仍然是一个向量。

在讨论消元的时候,我们关心的是行变化。类似于列向量的线性组合 —— 一个行向量乘以矩阵,可以看做是矩阵行的线性组合,其结果仍然是行向量。前面的消元过程,就可以转化为确定适当线性组合,也就是寻找行向量的问题:

\[\left[\begin{array}{}{?} & {?} & {?} \\ {?} & {?} & {?} \\ {?} & {?} & {?}\end{array}\right]\left[\begin{array}{}{1} & {2} & {1} \\ {3} & {8} & {1} \\ {0} & {4} & {1}\end{array}\right]=\left[\begin{array}{ccc}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {0} & {5}\end{array}\right]\]

第一个行向量, 需要线性组合矩阵行,达到消第一主元的目的,第二个行向量,需要线性组合矩阵行,达到消第二主元的目的,类推……。

单位矩阵

首先我们看一下,不起任何消元左右的矩阵——单位矩阵(Identity Matrix),它是矩阵世界里的1:

\[\left[\begin{array}{}{1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]\left[\begin{array}{}{1} & {2} & {1} \\ {3} & {8} & {1} \\ {0} & {4} & {1}\end{array}\right]=\left[\begin{array}{}{1} & {2} & {1} \\ {3} & {8} & {1} \\ {0} & {4} & {1}\end{array}\right]\]

第一个行向量,1个第一矩阵行 + 0个第二矩阵行 + 0个第三矩阵行,明显结果仍然是第一矩阵行。第二、第三行向量类似。

如何消元

我们为了消第二行的x,当时是将第一行乘以3,然后用第二行减去它,结果替换掉第二行。这可以看做是-3个第一行 + 1个第二行 + 0个第三行的线性组合。对应到矩阵:

\[\left[\begin{array}{}{1} & {0} & {0} \\ {-3} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]\left[\begin{array}{}{1} & {2} & {1} \\ {3} & {8} & {1} \\ {0} & {4} & {1}\end{array}\right]=\left[\begin{array}{}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {4} & {1}\end{array}\right]\]

注意,第一行不需要消元,因此我们维持单位矩阵的第一行不变。

上面得到的左侧矩阵,称为初等矩阵(Elementary Matrix,和单位矩阵仅有微小差别的矩阵),记作\(\mathbf{E}_{2 1}\),表示它需要干掉的是第2行第1列的元。

更进一步,在上面的右侧矩阵的基础上,我们在应用初等矩阵\(\mathbf{E}_{3 2}\),干掉的是第3行第2列的元:

\[\left[\begin{array}{}{1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {-2} & {1}\end{array}\right]\left[\begin{array}{}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {4} & {1}\end{array}\right] = \left[\begin{array}{}{1} & {2} & {1} \\ {0} & {2} & {-2} \\ {0} & {0} & {5}\end{array}\right]\]

综合在一起,其实就是用两个初等矩阵乘以系数矩阵,可以得到上三角矩阵:

\[E_{32}\left( E_{21} A\right)=U\]

其实我们很容易想到有单个矩阵即可完成上述两个初等矩阵的工作,并且可以由此引出矩阵乘法的结合律(Associative Law,注意交换律不成立):

\[E_{32}\left( E_{21} A\right)=\left(E_{32}E_{21}\right) A = E A\]

我们不去证明结合律,但是这两个初等矩阵相乘即得到消元矩阵。

置换矩阵

置换矩阵(Permutation Matrix)是另外一种初等矩阵,它的目的是置换两行或两列。

交换两行的置换矩阵:

\[\left[\begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right]\left[\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right]=\left[\begin{array}{ll}{c} & {d} \\ {a} & {b}\end{array}\right]\]

交换两列的置换矩阵,注意列变换需要在右边乘以一个矩阵:

\[\left[\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right]\left[\begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right]=\left[\begin{array}{ll}{b} & {a} \\ {d} & {c}\end{array}\right]\]
逆矩阵

本课还提及了逆(Inverses)矩阵。

第一次消元时,我们使用矩阵\(\left[\begin{array}{}{1} & {0} & {0} \\ {-3} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]\),也就是-3个第一行加到1个第二行上,消除了第二行的x。

那么,怎么找到一个矩阵,来取消这次消元呢?根据结合律可知:

\[A = IA = ( E^{-1} E  )A\]

也就是,逆矩阵就是和你相乘后变为单位矩阵的矩阵。我们做消元的时候,是让第二行加上了-3个第一行,取消此操作即让第二行加上3个第一行即可:

\[\left[\begin{array}{ccc}{1} & {0} & {0} \\ {3} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-3} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]=\left[\begin{array}{lll}{1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]\]
矩阵乘法
求单个元素 

两个矩阵相乘,如何求得结果矩阵中第i行j列的元素\(C_{ij}\)?回顾一下上一课的做法,结果矩阵的第i行是右侧矩阵B所有行的线性组合,组合的系数来自左侧矩阵A的第i行,而结果矩阵的第j列仅仅和B的j列有关,因此:

\[C_{ij} = (Row\ i\ of\ A) \cdot (Col\ j\ of\ B) = a_{i1}b_{1j} + a_{i2}b_{2j}\ +\ ... = \sum_{k=1}^{n} a_{i k} b_{k j} \]

你可以将其看作是一行N列矩阵和一列N行的矩阵相乘,结果是1行1列矩阵。 

将A看做行向量

仍然以线性组合的方式考虑:第一个矩阵的每一行,需要作为系数,进行第二个矩阵的行向量进行线性组合。这意味着第一个矩阵的列数量等于第二个矩阵的行数量:

\[{A}_{m \times n} {B}_{n \times p} = {AB}_{m \times p}\]

矩阵乘积的结果不一定是方阵,也就是说第一矩阵的行数量不需要等于第二矩阵的列数量。

将B看做列向量

如果将B看做是一个个的列向量。在线性组合时,这些向量相互之间是不影响的,可以单独计算。也就是说,矩阵乘法可以看做A和B的每个列向量相乘得到AB的各列向量。 

换一个角度,从列图像来看。矩阵A乘以向量(B中的列),即A的每个列的线性组合,注意A列向量的数量(就是列数)和B的行数(B列的长度)相同。

总之,将矩阵乘法看成右侧行向量的线性组合,还是左侧列向量的线性组合,效果是一样的。

多矩阵求和

我们已经从三个角度考虑过矩阵乘法,此外还可以以左侧列乘以右侧行。

但是必须比左侧列看做是\({A}_{m \times 1}\)矩阵,右侧行看做是\({B}_{1 \times p}\)矩阵。结果是\({AB}_{m \times p}\)矩阵。

所有左侧列、右侧行的乘积都是这样的矩阵。所有这些矩阵求和,即最初矩阵AB的乘积:

\[\left[\begin{array}{ll}{2} & {7} \\ {3} & {8} \\ {4} & {9}\end{array}\right]\left[\begin{array}{ll}{1} & {6} \\ {0} & {0}\end{array}\right]=\left[\begin{array}{l}{2} \\ {3} \\ {4}\end{array}\right]\left[\begin{array}{ll}{1} & {6}\end{array}\right]+\left[\begin{array}{l}{7} \\ {8} \\ {9}\end{array}\right]\left[\begin{array}{ll}{0} & {0}\end{array}\right]\]
分块乘法

直接把分块看做元素就可以:

\[\left[\begin{array}{II}{A_{1} A_{2}} \\ {A_{3} A_{4}}\end{array}\right]\left[\begin{array}{ll}{B_{1}}  {B_{2}} \\ {B_{3}}  {B_{4}}\end{array}\right]\]

结果矩阵左上角,等于B行向量们以A第一行为系数的线性组合,即\(A_1\times B_1 + A_2\times B_3\)

逆矩阵

逆矩阵是关于方阵的,也就是说,可逆矩阵一定是方阵。

方阵的逆矩阵

给定一个方阵,它可能有或没有逆矩阵(Inverse)。所谓逆矩阵,就是:

\[ A' \times A = A \times A' = I \]

也就是,方阵和它的逆矩阵相乘,结果是单位矩阵,不管是左逆(逆矩阵放在左边)还是右逆。注意左逆等于右逆,对于非方阵不成立,因为形状不匹配无法相乘。

存在逆矩阵的矩阵,称为可逆(Invertiable)或非奇异(Non singular)矩阵。

奇异矩阵

如果存在一个非零向量\( X \)使得\( AX = 0 \),则矩阵是奇异(Singular,形容破坏了某种优良性质的数学对象)的。也就是说,如果矩阵的列,通过某种线性组合,能得到零向量,则它是不可逆的。明显,如果从列图像看,奇异矩阵要求列向量方向相同。

反证:如果在上述条件下,矩阵仍然可逆,那么必然\( A' \times A \times X = I \times X = 0 \),要求X为零向量。

下面是一个奇异矩阵:

\[ \left[\begin{array}{ll}{1} & {3} \\ {2} & {6}\end{array}\right]\left[\begin{array}{l}{3} \\ {-1}\end{array}\right]=\left[\begin{array}{l}{0} \\ {0}\end{array}\right]\]
Gauss-Jordan消元

这是一种求解逆矩阵的方法。 其思想是同时求解两个线性方程组。

还记得通过消元法处理增广矩阵么?Gauss-Jordan方法类似。我们已知A和I,现在需要求得A':

\[\left[\begin{array}{ll}{1} & {3} \\ {2} & {7}\end{array}\right]\left[\begin{array}{l}{a} \\ {b}\end{array}\right]=\left[\begin{array}{l}{1} \\ {0}\end{array}\right]\] \[\left[\begin{array}{ll}{1} & {3} \\ {2} & {7}\end{array}\right]\left[\begin{array}{l}{c} \\ {d}\end{array}\right]=\left[\begin{array}{l}{0} \\ {1}\end{array}\right]\]

Gauss-Jordan方法将A和I放在一起进行消元:

\[\left[\begin{array}{llll}{1} & {2} & {1} & {0} \\ {3} & {7} & {0} & {1}\end{array}\right]\]

以便将A变为单位矩阵I,此时右侧就变成了A'。

第一步,将第一行乘以-2,加到第二行上:

\[\left[\begin{array}{llll}{1} & {3} & {1} & {0} \\ {2} & {7} & {0} & {1}\end{array}\right] ⇨ \left[\begin{array}{lll}{1} & {3} & {1} & {0} \\ {0} & {1} & {-2} & {1}\end{array}\right]\]

第二步,将第二行乘以-3,加到第一行上:

\[\left[\begin{array}{lll}{1} & {3} & {1} & {0} \\ {0} & {1} & {-2} & {1}\end{array}\right] ⇨ \left[\begin{array}{cccc}{1} & {0} & {7} & {-3} \\ {0} & {1} & {-2} & {1}\end{array}\right]\]

右侧即A的逆矩阵A'

如何理解这种方法?实际上相当于对长矩阵应用了一个消元矩阵,把左半部分消成单位矩阵,意味着消元矩阵\(E = A'\),而它将单位矩阵消成(乘法)了什么?任何矩阵乘以单位矩阵是它自己:

\[ A' [A I] = [I A']\]
A的LU分解

先前的课程中我们学习了如何将A进行行变换,得到上三角矩阵U的过程,并且知道有了U线性方程组的解就出来了。而本课的目的是直接给出消元公式,最基本的矩阵分解:

\[ A = L U \]
逆和转置

关于A和它的逆A',下面的等式成立:

\[ A' \times A = A \times A' = I \]

那么两个n阶矩阵乘积AB的逆是什么呢?

\[ ABB'A' = A(BB')A' = AIA' = AA' = I \]

也就是说,AB的逆是B'A'。

那么对上述等式进行转置(列变为行,行变为列,Transpose)如果\( A A^{-1} = I\),则两侧分别进行转置:

\[ (A^{-1})^{T} A^{T}= (A^{T})^{-1} A^{T}= I\]

关于上述等式的解释:

  1. 单位矩阵的转置仍然是单位矩阵
  2. 矩阵乘积进行转置,需要分别转置,然后交换顺序进行相乘
  3. 转置的逆,就是逆的转置。也就是说,对于单个矩阵来说,转置和逆这两者的顺序可以交换
LU分解

考虑矩阵\(\left[\begin{array}{ll}{2} & {1} \\ {8} & {7}\end{array}\right]\),我们期望消除第二行的第一个元素,得到上三角矩阵\(\left[\begin{array}{ll}{2} & {1} \\ {0} & {3}\end{array}\right]\),需要用是初等矩阵式\(\left[\begin{array}{ll}{1} & {0} \\ {-4} & {1}\end{array}\right]\)

此时:\(E_{21}A=U\),我们想得到的是\(A = LU\),如何变换?只需要两边乘以\((E_{21})^{-1}\)即可:

\(E_{21}A=U ⇨ (E_{21})^{-1}E_{21}A=(E_{21})^{-1}U ⇨ IA=(E_{21})^{-1}U ⇨ A=(E_{21})^{-1}U ⇨ \left[\begin{array}{ll}{2} & {1} \\ {8} & {7}\end{array}\right]=\left[\begin{array}{ll}{1} & {0} \\ {4} & {1}\end{array}\right]\left[\begin{array}{ll}{2} & {1} \\ {0} & {3}\end{array}\right] \)

可以看到L的非零元素集中在左下角,这也是它名字的由来 —— 下三角矩阵。

所谓LU分解(Decomposition),就是将一个矩阵(方程组的系数)分解为一个下三角矩阵和一个上三角矩阵的乘积。

消元的计算复杂度

对于n阶方阵,消元总计需要:

  1. \( \frac{1}{3}  n^3\)次操作处理\(A\)
  2. \(n^2\)次操作处理\(b\)
LU分解的意义

使用LU分解,具有较小的计算复杂度。

考虑3x3矩阵,对它进行消元,对于不需要换行(应对主元为零)的简化场景,需要应用三个初等矩阵\(E_{32}E_{31}E_{21} A = U\),来分别把第二行第一个元素、第三行第一、第二个元素消去。随着矩阵阶数的增加,计算量显然不是线性增长的。

如果把初等矩阵换到右侧,则是\( A = E_{21} ^{-1}E_{31}^{-1}E_{32}^{-1} U\),\(L\)就是那三个逆矩阵的乘积。这些逆的乘积,要比初等矩阵的乘积简单。

下面的例子,假设矩阵\(A\)的第三行第一列已经为0,不需要\(E_{31}\),需要两个初等矩阵完成消元。计算它们的乘积,得到消元矩阵E:

\[\underset{E_{32}}{\left[\begin {array}{} {1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {-5} & {1}\end{array}\right]}{\ }\underset{E_{21}} {\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-2} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-2} & {1} & {0} \\ {10} & {-5}&{1}\end{array}\right] = E\]

好了,从消元矩阵上看,为了得到上三角矩阵的第三行,需要第一行参与的线性组合。这是为何?原因是\( E_{21} \)时第二行已经加上了-2倍的第一行,\( E_{32} \)是在已经组合之后的行2的基础上在进行组合,又加上了-5倍第二行,相当于是,为了消第三行第二列,需要组合10被的行一。这也是消元矩阵左下角的10的来由。

现在,换个角度,用初等矩阵的逆计算:

\[\underset{E_{21}^{-1}} {\left[\begin{array}{ccc}{1} & {0} & {0} \\ {2} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right]}{\  }\underset{E_{32}^{-1}}{\left[\begin {array}{} {1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {5} & {1}\end{array}\right]}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {2} & {1} & {0} \\ {0} & {5}&{1}\end{array}\right] = L \]

可以看到,构成\(L\)的矩阵,相乘的顺序非常好,求得L不需要任何计算 —— 只需将所有消元乘数(来自初等矩阵)写出来就可以(在不需要换行的情况下)得到L。

转置-置换-向量空间R
置换矩阵

当消元过程中,遇到主元为0的情况,需要更换行的位置,保证主元非零。这种置换操作叫Permutation。

能够完成两行或多行置换的矩阵,叫做置换矩阵。对于3阶方阵,这种矩阵有6个,例如:

\[P_{12} = \left[ \begin{array}{ccc}{0} & {1} & {0}\\ {1}&{0}&{0}\\{0}&{0}&{1}\end{array}\right]\]

这群矩阵很特别,不管如何相乘,结果仍然是6个之一。

一个n阶的置换矩阵的总数,是$n^!$,因此4阶的置换矩阵有24个。

置换矩阵就是进行了换行的单位矩阵。单位矩阵也是置换矩阵,只是它什么事情也不做而已。

置换矩阵有个性质,其逆矩阵等于其转置矩阵:\(\begin{aligned}P^{-1} = P^T\\P^T P = I \end{aligned}\)

很多情况下矩阵不够好,需要引入置换矩阵才能完成消元。对于Matlab,它甚至对于非常小的主元(非零)也会进行换行,原因是影响了计算准确性。为了进行LU分解,可能需要先对$A$应用置换矩阵:

\[P{ }A = L{ }U\]

才能得到右上角全零、对角线为1的$L$,以及左下角全零的$U$。

转置

转置操作可以用于任何矩阵,就是将第N行变为第N列:

\[\begin{bmatrix} 1 &3 \\ 2&3 \\4&1 \end{bmatrix}^T = \begin{bmatrix}1 &2 &4 \\ 3 &3 &1\end{bmatrix}\]

明显,对于任意元素,存在:$(A^T)_{ij} = A_{ji}$

对称矩阵

对称(Symmetric)矩阵就是转置后没有变化的矩阵,即$A^T = A$。这种矩阵沿着左上-右下对角线对称,例如:$\begin{bmatrix}3&1&7\\1&3&9\\7&9&4\end{bmatrix}$

对于任何矩阵$R$,$R^T R $ 都是对称矩阵,因为结果矩阵的转置等于自己:$(R^TR)^T = R^T R^{TT} = R^TR$

向量空间

向量可以支持以下运算:

  1. 加上一个向量,可能导致其方向改变
  2. 乘以个标量,方向不变

向量空间(Vector Spaces)具有以下性质:

  1. 其中的任意向量经过任意加、乘,也就是线性组合,仍然落在向量空间中,或者说向量空间必须对于加、乘操作是封闭的。对于二维空间来说,第一象限不是向量空间,因为尽管其中的向量任意相加不会跑出去,但是乘以一个负数则跑到第3象限了

$R^n$表示所有$n$维实向量(其所有分量Component都是实数)的整体,它覆盖整个$n$维空间的所有点,很明显它是一个向量空间。

子空间

那么,是否$R^n$的一部分也可以是向量空间(即子空间)呢:

  1. 由于任何向量乘以0,都是原点,因此任何向量空间都必然经过原点
  2. $R^2$的子空间包括:
    1. $R^2$本身
    2. 任何过原点的直线$L$
    3. 原点,也就是零向量$Z$
  3. 推广到$R^3$,它的子空间包括:
    1. $R^3$本身
    2. 所有过原点的平面
    3. 所有过原点的直线
    4. 原点
矩阵角度

现在从矩阵角度来考虑子空间。如何得出矩阵$A$所在的子空间?或者说,如何得出矩阵所有列向量所属的子空间。

该子空间必须满足,对矩阵列向量进行任意线性组合,结果仍然在此子空间中。或者说,矩阵列向量的所有线性组合构成了子空间,该子空间也叫列空间(Column space),记作$C(A)$。

对于只有3行2列的矩阵$\begin{bmatrix}a&d\\b&e\\c&f\end{bmatrix}$,其线性组合最大构成的子空间是平面,也可能是直线,或者是原点。

列空间和零空间
子空间的并集

两个子空间的并集通常不是子空间,考虑$R^3$中相交的$L$和$P$,很明显两者中取出的向量,相加后通常不在$L$或$P$中。

子空间的交集

两个子空间的交集,仍然是子空间。以$R^3$为例,$L$和$P$的交集可能是零向量,也可能是$L$。

推广到任意$R^n$中的两个子空间$S$和$T$,它们的交集$S\cap T$必然也是子空间。

推广到R4

考虑矩阵$A = \begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}$,它是包含3个4维列向量。就像2个3维列向量不管如何组合都无法覆盖三维空间那样,这些4维列向量不管如何组合都无法覆盖四维空间,最多覆盖3维。

根据矩阵中列的不同,列空间可能是3维空间、平面、直线或零向量,它们的共同点是都经过零向量。

再次强调一下,列空间就是列向量的所有线性组合。

Ax = b

结合上一小节的3x4矩阵,回到本课最初的问题上:

  1. 对于任意$b$这个方程组总是有解么。也就是说,对于一组列向量$A = \begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}$,是否总是存在它们的线性组合(系数为$x$,亦即方程组的解)以得到任意的$b$。任意的$b$就代表着$R^n$,答案显然是否:
    1. 从方程组角度看:因为方程组有4个方程,却只有3个未知数
    2. 从线性组合的角度看:线性组合被局限在3维空间里面,无法达到4维空间的任何点
  2. 对于什么样的$b$,方程组 $Ax = \begin{bmatrix} 1&1&2\\2&1&3\\3&1&4\\4&1&5 \end{bmatrix} \times \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} =\begin{bmatrix} b_1 \\ b_2 \\b_3 \\ b_4\end{bmatrix}  $是有解的。这个问题其实可以转化为,什么样的$b$位于$A$的列空间中:
    1. 零向量是满足需求的$b$
    2. 1个第一列组合0个第2、3列
    3. ……

结论就是:$A_x=b$有解,当且仅当$b$位于$A$的列空间中时。

线性无关

一组列向量线性无关,意味着它们每个人对线性组合都有贡献。例如上面的矩阵,列1和列2方向不同,线性无关。但是列1和列2组合后的向量,和量3可以方向一致(3位于1和2构成的平面上),这种情况下,列3对线性组合没有贡献,亦即它和前两个列是线性相关的。

线性相关的向量,可以去除,对列空间没有影响。留下的称为主列(Pivot Columns)。保留的原则是,优先保留左侧的。

零空间

零空间(Null space)是一种完全不同的子空间,它由所有能解$A x = 0$的$x$组成。也就是线性组合结果为0的系数(Coefficients)的集合。

对于$Ax = \begin{bmatrix} 1&1&2\\2&1&3\\3&1&4\\4&1&5 \end{bmatrix} \times \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = 0 $来说,列空间是$R^4$的子空间,而零空间只有三个维度(因为方程只有3个未知数),是$R^3$的子空间。

零空间包含那些向量呢?首先零向量必然在其中,能称之为空间,必然包含零向量,这是封闭性的必然(任何向量都可以线性组合为0向量)。用零向量带入,明显符合预期。

此外,$\begin{bmatrix}1\\1\\-1\end{bmatrix}$也在零空间中,由此也可以推导出对于任意的$C$,有$\begin{bmatrix}C\\C\\-C\end{bmatrix} $位于零空间中:$C \times A \times \begin{bmatrix}1\\1\\-1\end{bmatrix}  = C \times 0 ⇨ A \times C \times \begin{bmatrix}1\\1\\-1\end{bmatrix}  = 0 ⇨ A \times \begin{bmatrix}C\\C\\-C\end{bmatrix}  = 0$。注意标量在乘法中支持交换律。

因此,对于该例子中的$A$来说,它的零空间是$R^3$中的一条直线。 

任意矩阵

对于任意$Ax = 0$,它的解构成一个子空间。证明如下:

  1. 对于方程的任意解$v$、$w$,有$\begin{cases} Av = 0\\ Aw = 0\end{cases}$
  2. 等式相加,使用分配率(Distributive law),即$Av + Aw = A(v + w) = 0$。即,如果$v$、$w$位于零空间内,那么$v + w$也在零空间内
  3. 同样,对于任意$v$(或者$w$),有$A(Cv) = C (Av) = Av = 0$
  4. 因此方程的任意解位于零空间中
主变量、特解

考虑线性方程组$A = \begin{bmatrix}1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\x_3\\ x_4\end{bmatrix} = 0$,第2列是第1列的2倍 ,第1行+第2行=第3行,它们是线性相关的,这一情况会在消元过程中表现出来:

\[\begin{bmatrix}1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix} ⇨ \begin{bmatrix}1&2&2&2\\0&0&2&4\\0&0&2&4\end{bmatrix}  ⇨ \begin{bmatrix}1&2&2&2\\0&0&2&4\\0&0&0&0\end{bmatrix} \]

第2步消元我们就遇到了麻烦,简单情况下,行2的第1列被消除,这里第2列也被消除了。我们自然的将第3列作为主元,执行第2步消元,将行3消为0。最终得到的不典型的阶梯形式(Echelon form)的$U$

需要注意的一点,消元不会改变方程组的解,因此,对于上例来说,消元不会改变零空间。

秩

秩(Rank)就是消元完毕后,矩阵的主元的数量。对于上面的矩阵$A$,其秩为2。

主变量和自由变量

所谓主变量,就是主列,也就是消元后包含主元(每行的第1个非0 元素)的列所对应的未知数。在上例中,列1列3包含主元,因此主变量是$x_1$、$x_3$。

与主变量对应的是自由变量,自由变量对应的列没有主元,即$x_2$、$x_4$。所谓自由变量,是指它的取值是任意的,不影响方程组的解。

我们可以取$ x_2 = 1 \\ x_4 = 0$可以得到解$x=\left[\begin{array}{c}{-2} \\ {1} \\ {0} \\ {0}\end{array}\right]$。这个解是$R^4$中的一个点。很明显$x=C\left[\begin{array}{c}{-2} \\ {1} \\ {0} \\ {0}\end{array}\right]$成立,解延续为一条直线。

特解

前面提到,自由变量可以随意取值。我们已经得到一个解$\left[\begin{array}{c}{-2} \\ {1} \\ {0} \\ {0}\end{array}\right]$,类似的在随意更换一下自由变量,可以再得一个解$\left[\begin{array}{c}{2} \\ {0} \\ {-2} \\ {1}\end{array}\right]$。这样手工选出来的解,叫做特解(Special solutions)。

有了特解,就可以构造出整个零空间,特解的任意线性组合即所有解,亦即零空间。那么特解到底有几个?每个自由变量对应一个特解。自由变量的数量为列数减去秩$n - r $。

回顾Ax=0解法
  1. 消元,如果遇到主元位置为零的情况,不用管它,继续消元
  2. 得到关键的,主元个数即秩,以及自由变量数量
  3. 根据自由变量数量选出特解
  4. 将特解进行线性组合,得到零空间,亦即解
简化行阶梯形式

行阶梯矩阵可以继续化简:

\[\begin{bmatrix}1&2&2&2\\0&0&2&4\\0&0&0&0\end{bmatrix} \]

回顾一下第3行是怎么来的?它是由行1和行2进行线性组合得到的。我们可以继续通过线性组合进行消元,让主元的上方也变为零、所有主元变为1。

\[\begin{bmatrix}1&2&2&2\\0&0&2&4\\0&0&0&0\end{bmatrix} ⇨ \begin{bmatrix}1&2&0&-2\\0&0&2&4\\0&0&0&0\end{bmatrix}  ⇨ \begin{bmatrix}1&2&0&-2\\0&0&1&2\\0&0&0&0\end{bmatrix} \]

现在我们得到了$R$,所有主元为1,主元上下方都是0,这样的$R$叫做$A$的简化行阶梯形式。在Matlab中一个命令RREF(Reduced Row Echelon Form of A)即可完成矩阵到$R$的转换。这种最简化的形式包含了所有足够的信息。

我们可以注意到,由于主元都变为1,且它们的上下都是0,因此$R$中隐含了单位矩阵,它在主行(1、2)和主列(1、3)的交汇之处。

第3行全零,没有意义,因为它可以是任意行的线性组合,$0 = 0$也总是满足。

求解$Ax = 0$转换为中间过程$Ux = 0$,最终变为求$Rx = 0$。

我们把主列放在一起,自由列放在一起,可以得到化简行阶梯的典型形式:

\[ R = \begin{bmatrix}I&F\\0&0\end{bmatrix} = \begin{bmatrix}1&0&2&-2\\0&1&0&2\\0&0&0&0\end{bmatrix} \]

零空间矩阵

所谓零空间矩阵$N$,它的所有列都是特解,特解进行线性组合即可得到零空间。

如果$N$的每一列都是特解,那么等式$RN = 0$成立,原因是$N$的任何列满足$Rx = 0$,因此RN相乘应该是零矩阵。

什么样的$N$满足需求?很明显是$N=\begin{bmatrix}-F\\I\end{bmatrix}$,这就是特解构成的零空间矩阵。在Matlab中使用NULL指令可以计算出零空间矩阵。

转置

矩阵转置之后,主列(包含主元的列)数量不变。上面的矩阵$A$主列数量为2,它的转置矩阵的主列数量仍然是2:

\[\begin{bmatrix}1&2&3\\2&4&6\\2&6&8\\2&8&10\end{bmatrix}  ⇨ \begin{bmatrix}1&2&3\\0&2&2\\0&0&0\\0&0&0\end{bmatrix} ⇨ \begin{bmatrix}1&0&1\\0&1&1\\0&0&0\\0&0&0\end{bmatrix}  \]

上述矩阵自由列数量为1,因此它的特解只有一个,取$x_3 = 1$,得到特解$\begin{bmatrix}-1\\-1\\1\end{bmatrix}$,它可以乘以任何倍数,因此零空间是一条直线。我们可以将零空间记作$x = C\begin{bmatrix}-1\\-1\\1\end{bmatrix}$,而那个特解叫做零空间的基(Basis)。

 

← LaTex语法速查
常用数学公式 →

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

Related Posts

  • 常用数学公式
  • Octave知识集锦
  • 吴恩达机器学习笔记
  • LaTex语法速查

Recent Posts

  • Investigating and Solving the Issue of Failed Certificate Request with ZeroSSL and Cert-Manager
  • A Comprehensive Study of Kotlin for Java Developers
  • 背诵营笔记
  • 利用LangChain和语言模型交互
  • 享学营笔记
ABOUT ME

汪震 | Alex Wong

江苏淮安人,现居北京。目前供职于腾讯云,专注容器方向。

GitHub:gmemcc

Git:git.gmem.cc

Email:gmemjunk@gmem.cc@me.com

ABOUT GMEM

绿色记忆是我的个人网站,域名gmem.cc中G是Green的简写,MEM是Memory的简写,CC则是我的小天使彩彩名字的简写。

我在这里记录自己的工作与生活,同时和大家分享一些编程方面的知识。

GMEM HISTORY
v2.00:微风
v1.03:单车旅行
v1.02:夏日版
v1.01:未完成
v0.10:彩虹天堂
v0.01:阳光海岸
MIRROR INFO
Meta
  • Log in
  • Entries RSS
  • Comments RSS
  • WordPress.org
Recent Posts
  • Investigating and Solving the Issue of Failed Certificate Request with ZeroSSL and Cert-Manager
    In this blog post, I will walk ...
  • A Comprehensive Study of Kotlin for Java Developers
    Introduction Purpose of the Study Understanding the Mo ...
  • 背诵营笔记
    Day 1 Find Your Greatness 原文 Greatness. It’s just ...
  • 利用LangChain和语言模型交互
    LangChain是什么 从名字上可以看出来,LangChain可以用来构建自然语言处理能力的链条。它是一个库 ...
  • 享学营笔记
    Unit 1 At home Lesson 1 In the ...
  • K8S集群跨云迁移
    要将K8S集群从一个云服务商迁移到另外一个,需要解决以下问题: 各种K8S资源的迁移 工作负载所挂载的数 ...
  • Terraform快速参考
    简介 Terraform用于实现基础设施即代码(infrastructure as code)—— 通过代码( ...
  • 草缸2021
    经过四个多月的努力,我的小小荷兰景到达极致了状态。

  • 编写Kubernetes风格的APIServer
    背景 前段时间接到一个需求做一个工具,工具将在K8S中运行。需求很适合用控制器模式实现,很自然的就基于kube ...
  • 记录一次KeyDB缓慢的定位过程
    环境说明 运行环境 这个问题出现在一套搭建在虚拟机上的Kubernetes 1.18集群上。集群有三个节点: ...
  • eBPF学习笔记
    简介 BPF,即Berkeley Packet Filter,是一个古老的网络封包过滤机制。它允许从用户空间注 ...
  • IPVS模式下ClusterIP泄露宿主机端口的问题
    问题 在一个启用了IPVS模式kube-proxy的K8S集群中,运行着一个Docker Registry服务 ...
  • 念爷爷
      今天是爷爷的头七,十二月七日、阴历十月廿三中午,老人家与世长辞。   九月初,回家看望刚动完手术的爸爸,发

  • 6 杨梅坑

  • liuhuashan
    深圳人才公园的网红景点 —— 流花山

  • 1 2020年10月拈花湾

  • 内核缺陷触发的NodePort服务63秒延迟问题
    现象 我们有一个新创建的TKE 1.3.0集群,使用基于Galaxy + Flannel(VXLAN模式)的容 ...
  • Galaxy学习笔记
    简介 Galaxy是TKEStack的一个网络组件,支持为TKE集群提供Overlay/Underlay容器网 ...
TOPLINKS
  • Zitahli's blue 91 people like this
  • 梦中的婚礼 64 people like this
  • 汪静好 61 people like this
  • 那年我一岁 36 people like this
  • 为了爱 28 people like this
  • 小绿彩 26 people like this
  • 杨梅坑 6 people like this
  • 亚龙湾之旅 1 people like this
  • 汪昌博 people like this
  • 彩虹姐姐的笑脸 24 people like this
  • 2013年11月香山 10 people like this
  • 2013年7月秦皇岛 6 people like this
  • 2013年6月蓟县盘山 5 people like this
  • 2013年2月梅花山 2 people like this
  • 2013年淮阴自贡迎春灯会 3 people like this
  • 2012年镇江金山游 1 people like this
  • 2012年徽杭古道 9 people like this
  • 2011年清明节后扬州行 1 people like this
  • 2008年十一云龙公园 5 people like this
  • 2008年之秋忆 7 people like this
  • 老照片 13 people like this
  • 火一样的六月 16 people like this
  • 发黄的相片 3 people like this
  • Cesium学习笔记 90 people like this
  • IntelliJ IDEA知识集锦 59 people like this
  • 基于Kurento搭建WebRTC服务器 38 people like this
  • Bazel学习笔记 37 people like this
  • PhoneGap学习笔记 32 people like this
  • NaCl学习笔记 32 people like this
  • 使用Oracle Java Mission Control监控JVM运行状态 29 people like this
  • 基于Calico的CNI 27 people like this
  • Ceph学习笔记 27 people like this
  • Three.js学习笔记 24 people like this
Tag Cloud
ActiveMQ AspectJ CDT Ceph Chrome CNI Command Cordova Coroutine CXF Cygwin DNS Docker eBPF Eclipse ExtJS F7 FAQ Groovy Hibernate HTTP IntelliJ IO编程 IPVS JacksonJSON JMS JSON JVM K8S kernel LB libvirt Linux知识 Linux编程 LOG Maven MinGW Mock Monitoring Multimedia MVC MySQL netfs Netty Nginx NIO Node.js NoSQL Oracle PDT PHP Redis RPC Scheduler ServiceMesh SNMP Spring SSL svn Tomcat TSDB Ubuntu WebGL WebRTC WebService WebSocket wxWidgets XDebug XML XPath XRM ZooKeeper 亚龙湾 单元测试 学习笔记 实时处理 并发编程 彩姐 性能剖析 性能调优 文本处理 新特性 架构模式 系统编程 网络编程 视频监控 设计模式 远程调试 配置文件 齐塔莉
Recent Comments
  • qg on Istio中的透明代理问题
  • heao on 基于本地gRPC的Go插件系统
  • 黄豆豆 on Ginkgo学习笔记
  • cloud on OpenStack学习笔记
  • 5dragoncon on Cilium学习笔记
  • Archeb on 重温iptables
  • C/C++编程:WebSocketpp(Linux + Clion + boostAsio) – 源码巴士 on 基于C/C++的WebSocket库
  • jerbin on eBPF学习笔记
  • point on Istio中的透明代理问题
  • G on Istio中的透明代理问题
  • 绿色记忆:Go语言单元测试和仿冒 on Ginkgo学习笔记
  • point on Istio中的透明代理问题
  • 【Maven】maven插件开发实战 – IT汇 on Maven插件开发
  • chenlx on eBPF学习笔记
  • Alex on eBPF学习笔记
  • CFC4N on eBPF学习笔记
  • 李运田 on 念爷爷
  • yongman on 记录一次KeyDB缓慢的定位过程
  • Alex on Istio中的透明代理问题
  • will on Istio中的透明代理问题
  • will on Istio中的透明代理问题
  • haolipeng on 基于本地gRPC的Go插件系统
  • 吴杰 on 基于C/C++的WebSocket库
©2005-2025 Gmem.cc | Powered by WordPress | 京ICP备18007345号-2