线性代数系列(八) |
您所在的位置:网站首页 › 线性代数的总结与归纳论文 › 线性代数系列(八) |
主要内容
关联矩阵关联矩阵的零空间关联矩阵的左零空间关联矩阵的行空间欧拉公式
正文
虽然在课程中举例所使用的矩阵都是自己编制的矩阵,但是矩阵的来源却不是通过人随便编制出来的,它们都是来自实际问题,描述了实际问题的拓扑结构。其中最重要的一种概念就是图,图是矩阵的重要来源。 关联矩阵图论中的图不像是高等数学中的图,高等数学中的图更多的是指函数的图像,而图论中的图更多的是指描述拓扑结构的一种数学模型,它是结点和边的集合。对于一个图,用矩阵的特定行表示图的特定边,用矩阵的特定列表示矩阵的特定的顶点。某一行的某一列上的一个数有三种取值为 0 、 1 、 − 1 0、1、-1 0、1、−1,其中 0 0 0表示边与顶点没有关系, 1 1 1表示该顶点是特定边的终点, − 1 -1 −1表示该顶点是特定边的起点。这样的矩阵就是关联矩阵,关联矩阵描述了一个图中所有的结点、边和结点与边的关系等信息。 关联矩阵的零空间如下关联矩阵 [ − 1 1 0 0 0 − 1 1 0 − 1 0 1 0 − 1 0 0 1 0 0 − 1 1 ] \begin{bmatrix}-1;1;0;0\\0;-1;1;0\\-1;0;1;0\\-1;0;0;1\\0;0;-1;1\end{bmatrix} ⎣⎢⎢⎢⎢⎡−10−1−101−10000110−100011⎦⎥⎥⎥⎥⎤所谓零空间就是能够使得关联矩阵的线性组合为0的系数向量。用线性方程表示为 A x = 0 Ax=0 Ax=0。记 x = [ x 1 , x 2 , x 3 , x 4 ] T x=\begin{bmatrix}x_1,x_2,x_3,x_4\end{bmatrix}^T x=[x1,x2,x3,x4]T。计算 A x = 0 Ax=0 Ax=0得到 x 1 = x 2 = x 3 = x 4 x_1=x_2=x_3=x_4 x1=x2=x3=x4。这个向量的四个分量都是相等的。根据之前的内容该关联矩阵的零空间可以表示为 N ( A ) = c [ 1 1 1 1 ] N(A)=c\begin{bmatrix}1\\1\\1\\1\end{bmatrix} N(A)=c⎣⎢⎢⎡1111⎦⎥⎥⎤在这个例子中,零空间的基就是上面的全 1 1 1列向量,维度为 1 1 1,即 n − r = 4 − r = 1 n-r=4-r=1 n−r=4−r=1,所以矩阵的秩 r = 3 r=3 r=3。可以发现,我们在研究子空间的时候,一般都是研究它的维度和基。 关联矩阵的左零空间依然使用上面的那个例子。使用方程组的方式表示求左零空间即:
A
T
y
=
0
A^Ty=0
ATy=0,
[
−
1
0
−
1
−
1
0
1
−
1
0
0
0
0
1
1
0
−
1
0
0
0
1
1
]
[
y
1
y
2
y
3
y
4
y
5
]
=
[
0
0
0
0
]
\begin{bmatrix}-1;0;-1;-1;0\\1;-1;0;0;0\\0;1;1;0;-1\\0;0;0;1;1\end{bmatrix}\begin{bmatrix}y_1\\y_2\\y_3\\y_4\\y_5\end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\end{bmatrix}
⎣⎢⎢⎡−11000−110−1010−100100−11⎦⎥⎥⎤⎣⎢⎢⎢⎢⎡y1y2y3y4y5⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎡0000⎦⎥⎥⎤关联矩阵的列表示图的结点,行表示边,现在,将关联矩阵进行了转置,那么列就表示边,行表示结点。而
A
T
y
=
0
A^Ty=0
ATy=0可以理解为将图的边进行线性组合(拼接),结果为0向量可理解为最后回到原点。通俗来讲就是在图中找到一条回路。因此左零空间中的向量都是使得各边能够拼接成回路的系数向量。当我们可视化这个图后,找到一条回路将会变得非常简单。 我们一直都是习惯于解列空间,因此,在求研究行空间的时候,我们研究关联矩阵的转置的列空间,它们是同一个矩阵空间。如下:
A
T
=
[
−
1
0
−
1
−
1
0
1
−
1
0
0
0
0
1
1
0
−
1
0
0
0
1
1
]
A^T=\begin{bmatrix}-1;0;-1;-1;0\\1;-1;0;0;0\\0;1;1;0;-1\\0;0;0;1;1\end{bmatrix}
AT=⎣⎢⎢⎡−11000−110−1010−100100−11⎦⎥⎥⎤对于一个矩阵,它的行空间和列空间的维度等于矩阵的秩。所以该矩阵的行空间的维度为
3
3
3,因此,我们要找三个线性无关的列向量,才能够确定这个行空间。我们可以使用通俗的方法来求解,化简至行阶梯型矩阵,找到主列即可。但这里我们讨论的是线性代数和图论的关系,所以这里依靠它在图中的拓扑意义来求解。三角形法则告诉了我们最基础的线性组合,在图论中这个三角形表现为回路。也就是如果向量能够组合成回路,那么这些向量是线性相关的,如果不能组合成回路,那么这些向量是线性无关的。 在
A
T
A^T
AT中,每个列向量恰好表示某条边,这更便于我们找线性无关的向量,只需要找出不能够组成回路的三条边,这便是一组基。如图中的
1
、
2
、
4
1、2、4
1、2、4。 对于关联矩阵 A A A,求解关联矩阵的左零空间维度的公式为 d i m ( N ( A T ) ) = m − r , r = n − 1 dim(N(A^T))=m-r,r=n-1 dim(N(AT))=m−r,r=n−1,其中 r = n − 1 r=n-1 r=n−1来自拓扑关系。我们已经知道其中的 m m m表示边数, n n n表示结点的个数。在介绍左零空间的时候我们已经知道左零空间的维度表示线性无关的回路的个数。那么秩表示的是什么呢?实际上这个问题在这里并不是必要的。将上面的公式进行转换一下: # l i n e a r i n d e p e n d e n t l o o p s = # e d g e − ( # n o d e s − 1 ) \#linear\ independent\ loops=\#edge-(\#nodes-1) #linear independent loops=#edge−(#nodes−1)也就是 # l i n e a r i n d e p e n d e n t l o o p s − # e d g e + # n o d e s = 1 \#linear\ independent\ loops-\#edge+\#nodes=1 #linear independent loops−#edge+#nodes=1这就是由线性代数推导出来的欧拉公式,表示线性无关的回路的个数减去边的个数加上结点的个数等于 1 1 1,这是对于所有的图都成立的结论,因为所有的图都可以使用关联矩阵表示,并且关联矩阵的子空间的求法都是相同的。 总结矩阵实现了将一个拓扑问题转换为数值问题,并通过数值的方法来解决拓扑问题。实际中,很多复杂的关系都可以使用网络来表示,而网络可以通过关联矩阵来表示,这样就逐步实现了对现实问题的数学建模。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |