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的另外一组基