当前课程知识点:线性代数(2) > 第八讲:图与网络 > 8.4 关联矩阵的四个基本子空间 > 8.4 关联矩阵的四个基本子空间
好 在这一部分呢
我们来讨论一下
关联矩阵的四个基本子空间的基
好 我们知道一个关联矩阵呢
和一个图实际上是一一对应的
我们这里说的是定向图
给一个定向图
我们可以给一个关联矩阵
反过来给一个关联矩阵
我们可以恢复出一个定向图
那么关联矩阵它作为矩阵呢
我们可以讨论
它的四个基本子空间
也就是它的零空间 行空间
列空间和左零空间
那么因为关联矩阵
跟图之间的相互关系
那么这四个基本子空间的基
实际上都赋含了图的一些信息
或图的性质
我们下面通过例子来说明
我们现在来看一个关联矩阵
计算它的四个基本子空间
因为关联矩阵呢
是反映的图的一些性质
所以它的四个基本子空间的基
也可以通过
关联矩阵的图的一些性质来刻画
我们来看下面这个例子
我们看右图这是由四个顶点
五条边构成的一个图
那么我们得到了它的关联矩阵呢
是一个五行四列的
每一行刻画了一条边的性质
1 2 3 4 5
第一条边经过了第一个顶点
和第二个顶点
每一列刻画了一个顶点的性质
每一列中非零的部分刻画了
经过这一顶点的边
比如说第二个顶点
对应的这一列
这一列的非零元是1 3 4
代表了经过②的三条边1 3 4
那么正负号代表了是进还是出
这个1代表的是进出
-1代表的从②这点出去
这个-1从②这点出去
这是我们的关联矩阵
我们现在来求
四个基本子空间的基
我们首先来看A的零空间
A的零空间的定义
是所有的x属于R^n Ax等于0
那么在现在这个例子中呢
这个n等于4
那么我们要筹一个四维向量
满足Ax等于0
我们可以看出A的每一行的元素
只有两个非零元 -1和1
所以每一行的元素之和
是等于0的
第一行-1+1
第二行也是-1+1
所以A的每一行的元素之和等于0
就说明了A乘上
由1构成的这个列向量是等于0的
换句话说
也就是这个向量的倍数
是属于N(A)的
那么我们看到A乘上u这个向量
得到的是各个边的电势
那么我们可以想一下
如果A乘上u等于零
那说明什么呢
那么从右边可以看出
A乘以u等于零
表示各个边上的电势差全是零
也就是说每一个顶点的电势
完全一样 这个是连通图
所以也就是u_1=u_2=u_3=u_4
这样子呢实际上整个u就是
1 1 1的倍数
由此我们看到N(A)中实际上
无关的向量只有一个
所以N(A)的维数是等于1
它们都是被1 1 1
这样一个向量伸出来的
这一步呢 因为我们知道
A的列空间的维数等于A的秩
那么A的秩
跟零空间的维数的关系
是A的列数减去A的秩
就是N(A)的维数
这样我们可以推出来
A的秩实际上等于3
换句话说 就是A这个矩阵
它的列数是顶点数
顶点数减1 也就是说
在这个例子中它的四列
其中有三列是线性无关的
另外一列可以被其他这三列
线性表示出
下面我们来看A的列空间
按列的空间定义呢
所谓一个列空间就是所有用A
去乘上一个x得到的向量
那么这里面的向量
都是A的列的线性组合
我们也知道Ax等于b有解
当且仅当b属于A的列空间
由刚才零空间的计算呢
我们知道 A的零空间
实际上是被1 1伸成的
零空间的维数是1
那么列空间的维数呢 等于A的秩
所以它等于n减1
所以n呢就是图的顶点个数
也就是A的列数
在我们这个例子中
实际上n是等于4的
所以列空间的维数是3
这样我们说明这个A呢实际上
表n减1个列向量是无关的
我们来证明
实际上呢A随便取n-1个列向量
都是线性无关的
大家注意这两个的区别
第一句话只是表示
A可以找出n-1个列向量
是线性无关的
第二个呢表示
A的任意n-1个列向量
是线性无关的
比如说我们举个例子
1 1 2 1 2 2
我们随便这个矩阵
并不是关联矩阵
我们来说明这个
这两列是线性无关的
但是这两列呢
一三列并不是线性无关的
所以这个矩阵满足第一条
这时候n取3
A有两个无关的列向量
但是并不是
A的任意两个无关的列向量
都是无关的
并不是A的任意两个列向量
都无关
那么对于关联矩阵呢
有这样一个非常好的性质
就是A的任意一个n-1个列向量
线性无关 我们来证明它
设A有n列
那么我们可以先假设
前n-1列是线性相关的
那么则存在着c_1到c_n-1不全为零
使得它们乘上α_i以后
加起来等于零
也就是零可以被r_1到r_n-1
非平凡的线性表出
那么我们要证明
实际上这些c_i呢必须是零
否则呢就会产生矛盾
我们来看一下
我们再补上一个
加上一个零乘α_n
那么实际上我们可以写成
这样一个形式
这个左边实际上就等于
c_1α_1+c_2α_2
一直加c_n-1α_n-1等于0
那么这个式子告诉我们
c_1到c_n-1 0这样一个向量
它属于N(A) 属于N(A)
但是我们知道N(A)
它是1 1 1这个向量的倍数
那么这一块有个0
所以由此可以推出
这些东西必须全是0
必须全是0
所以我们看到A的任意n-1列
都是线性无关的
否则呢就产生了矛盾
这样我们可以看到
A的列空间的基很容易取
就是任意取n-1列就可以了
我们换一个角度再看
对于我们最开始那个图
我们来看一下 Ax等于b
我们可以写成这样一个形式
b属于C(A)
那么我们可以看到
第一行和第三行相加
这个左边就变成了-x_1+x_3
那么它恰好等于第二行
所以右边也是相等
所以就是b_1+b_3=b_2
同样地我们可以推出
b_3+b_5=b_4 b_2+b_5=b_1+b_4
这样子呢
我们把右边移到左边以后
我们得到了这样两个式子
这样两个式子说明什么呢
我们知道Ax
x如果是表示每点的电势
那么Ax表示每点的电势
引起的每条边上的电势差
所以Ax表示电势差
那么大家可以看到
b_1 b_2 b_3 b_4 b_5
实际上代表的五条边上的电势差
那么我们来看这个等式
b_1-b_2+b_3=0
这个呢正好代表的是1 2 3边
它们的电势差之和等于零
1 2 3边构成一个回路
那么这部分恰好就是
我们的科尔霍夫电压定律
那么b_3-b_4+b_5也是一样的
就是3 4 5这三条边
构成一个回路
那么正负号我们来看
这块我们b_1和b_3取的是正号
也就是说b_1 b_3
按照我们规定的一个方向
比如说我们规定的是
逆时针方向为正
那么1 3都是逆时针方向
第二条边是顺时针方向
所以用负号表示
那我们可以看到
b要属于C(A)
那么b的分量要满足
科尔霍夫电压定律
那么这个实际上呢
我们大家可以看到
b属于C(A)
那么b要满足的
这两个表达式方程实际上就是
b要跟C(A)的正交补
之间的关系
体现了C(A)和正交补之间
N(A)^T的关系
那么这个矩阵大家可以看到
它刻画了我们的回路
而我们看这个矩阵有两行
第一行是代表着一条回路
第二行是代表了另一条回路
我们把这个矩阵叫回路矩阵
当然它的每一行
对应的是一个极小回路
两个极小回路呢
可以构成一个更大的回路
所以我们回路矩阵
它所使用的每一行
是一个极角回路
那么这张图中有两个极角回路
所以我们有两行
那么b的列呢代表的是五条边
那么我们来看一下
比如说这个1 -1 1 0 0
那么这个就表示的是
我们使用了1 2 3这三条边
4 5 这个位置全是0
那么1 2 3条边呢
1 3是取1 2取-1
代表的是这条回路
1 3是逆时针方向
2是顺时针方向
这样我们就得到了一个回路矩阵
那么这个回路矩阵呢
如果我们记作B的话
B乘上A就等于零
这就是我们的科尔霍夫电压定律
给出来的
就是每一条回路上
电压之和等于零
就是B乘上A的每一列都是零
B乘上A的每一列都是零
也就是说B乘上任意一个
A的列空间中的向量都是零
因为这个向量代表的是
每条边上的电势差
所以大B乘上这个小b呢
就代表的是每一个回路的电势差之和等于零
我们再来看左零空间
实际上刚才我们这个BA等于0
已经告诉我们左零空间了
那我们先回忆一下
左零空间的定义
A的左零空间是所有的向量y
m维向量
注意A是m行n列的
m代表的边的个数
n代表顶点个数
所以A^y=0的这些y
就是左零空间的向量
那我们刚才这个例子我们看到
A^Ty等于0 我们看
y_1+y_2的相反数等于0
就代表了经过顶点
y_i呢我们是边i上的电流
那么这个经过第一个顶点
电流
流入和流出的电流是一样的
这个代表的是第二个顶点
流入流出的电流是一样的
这就是科尔霍夫的电流定律
我们可以得到四个方程
刚才我们已经知道了BA等于0
B是回路矩阵
那么我们把它转置一下
那么就是A^TB^T等于0
这样就告诉我们
B^T的每一列都是
A的左零空间的解向量
而B^T的列就是B的行
而B的每一行代表的是
每一个极小回路
所以我们看到 由极小回路
所对应的这个回路向量
实际上就是
A的左零空间的解向量
我们现在给出一个定理
这个定理说呢A的左零空间
它的解向量由回路向量完全生成
也就是说B^T的列空间
或者B的行空间
就是A的左零空间
这个回路向量已经提供了
A的左零空间中的所有解
这个定理我们放到最后
注记中说一下
由这个定理我们看到
我们要想找左零空间的解
只要把所有极小回路向量
写出来就行了
最后我们来看一下A的行空间
因为A的秩是A的顶点数减1
所以A的行空间
跟A的列空间的维数是一样的
它也等于n-1
按照行空间的定义呢
行空间是由A的行线性组合出来
得到的向量空间
因为行空间跟A的零空间
是正交补关系
所以我们可以看到
A的行空间中的向量
任何一个向量f_1到f_n
这样一个向量呢
它的和是等于零的
因为1 1 1
这个是属于N(A)的
而且A的行空间的向量
跟这个向量是垂直的
按照内积的定义
垂直就代表着这两个向量乘起来
内积等于零
所以这样我们就得到了f_1+f_n=0
我们这个例子
只考虑到n等于4的情形
就是f_1加到f_4等于0
而下面我们来给出
A的行空间的一组基
A的行空间的一组基呢
它充分反映了这个图的一些性质
给定一个连通图呢
我们假设它有n个顶点 有m条边
那么我们可以知道
边数至少比顶点数减1
要大于等于
如果边数正好等于顶点数减1
那么我们把这个呢
就叫做一个树图
那么这样的一个树图呢
它不含回路
我们看如果含有回路
比如说这个例子
含回路 那么这三个顶点
三条边 边数等于顶点数
也就是边数大于顶点数减1了
所以边数等于顶点数减1呢
这样一个连通图 它是一个数
那么给定一个连通图
我们可以得到很多树图作为子图
比如说在我们例子中呢
从①到②
两个顶点 一条建项
就是我们那个连通图的一个子图
这个子图是一个数
边数等于顶点数减1
如果这个树的子图
包含了图的所有顶点
那么这时候我们称为极大树子图
比如说在我们那个例子中
从①到②到③到④
经过了这四个顶点
三条边 1 3 5
那么这样一个连通的子图
就是极大的树子图
那么我们来看一下
这样一个极大数子图呢
它的关联矩阵
和原图的关联矩阵的关系
那么显而易见
原图的关联矩阵的列有四列
那么现在极大数子图
它的关联矩阵也是四列
因为它经过所有顶点
原图的关联矩阵它的行
包含了所有的边
那么现在极大数子图
只包含了三条边
所以它是原来的关联矩阵
把相应的对应的那个边的行
抽出来得到的子矩阵
这就是原图的关联矩阵
那么我们把1 3 5行抽出来
第一行 第三行和第五行抽出来
对应的1 3 5这三条边
得到的这个子矩阵呢
就是极大数子图的关联矩阵
A0是一个行满秩的
那么这个A0的这三行呢
实际上就给出了CA^T的一组基
也就是说CA^T的一组基
实际上是来自于
极大数子图的关联矩阵的行数 相应的行
一个极大数字图它所使用的边
对应到A的行
就是A^T的一组基
A^T行 比如说2 5 4
构成了另一个极大数子图
那么我们从A这个矩阵中
抽出2 4 5这三行就构成了
C(A)^T的另外一组基
-1.1 实对称矩阵A正定的充要条件
-1.2 典型例题
--1.2 典型例题
-1.3 半正定矩阵及其判别条件
-1.4 二次型
--1.4 二次型
-1.5* 有心二次曲线(central conic)
-1.6* 三维空间中的二次曲面-6类基本的二次曲面
-1.7 二次型的分类
-1.8 矩阵的合同
-1.9* 惯性定理的证明
-1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
--1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
-1.11* 正(负)定矩阵在函数极值问题中的应用
-第一讲:正定矩阵--课后习题
-2.1 引言
--2.1 引言
-2.2 相似矩阵的性质
-2.3 Jordan标准形
-2.4 定理的证明
-2.5 Jordan标准形的应用
-第二讲:相似矩阵--课后习题
-3.1 引言
--3.1 引言
-3.2 奇异值分解(Singular Value Decomposition)
--3.2 奇异值分解(Singular Value Decomposition)
-3.3 例题
--3.3 例题
-3.4 奇异值分解的应用
-第三讲:奇异值分解--课后习题
-4.1 线性变换的定义和性质
-4.2 线性变换的运算
-4.3 线性变换的矩阵表示
-4.4 线性变换与矩阵之间的关系
-第四讲:线性变换 I--课后习题
-5.1 恒同变换与基变换
-5.2 图像压缩——基变换的应用
-5.3 线性变换在不同基下的矩阵
-5.4 矩阵分解与基变换
-5.5 线性变换的核与像
-5.6 不变子空间
-5.7* 幂零变换
-5.8* Jordan标准形
-第五讲:线性变换 II--课后习题
-6.1 伪逆
--6.1 伪逆
-6.2 Moore – Penrose 伪逆
-6.3 最小二乘法
-第六讲:伪逆--课后习题
-7.1 简介
--7.1 简介
-7.2 弹簧模型
--7.2 弹簧模型
-7.3 变量的线性关系
-7.4 刚度矩阵
--7.4 刚度矩阵
-7.5 从离散到连续
-第七讲:工程中的矩阵--课后习题
-8.1 简介
--8.1 简介
-8.2 图和矩阵
--8.2 图和矩阵
-8.3 网络和加权Laplacian矩阵
-8.4 关联矩阵的四个基本子空间
-8.5 注记
--8.5 注记
-第八讲:图与网络--课后习题
-9.1 问题引入
--9.1 问题引入
-9.2 Markov矩阵
-9.3 正Markov矩阵
-9.4 正矩阵
-第九讲:Markov矩阵和正矩阵--课后习题
-10.1 引言
--10.1 引言
-10.2 内积空间
-10.3 傅里叶级数
-10.4 投影
--10.4 投影
-10.5 关于Fourier变换的注记
-第十讲:Fourier级数--课后习题
-11.1 引言
--11.1 引言
-11.2 平移
--11.2 平移
-11.3 伸缩
--11.3 伸缩
-11.4 旋转
--11.4 旋转
-11.5 投影和反射
-第十一讲:计算机图像--课后习题
-12.1 引言
--12.1 引言
-12.2 复矩阵
--12.2 复矩阵
-12.3 复正规阵
-12.4 离散Fourier变换
-12.5 快速Fourier变换
-第十二讲:复数与复矩阵--课后习题
-结课寄语
--结课寄语