线性代数导论(12)-图和网络(最新讲义)

本讲着重于线性代数的应用,线性代数处理的矩阵都是有出处的,来自实际问题,描述问题的拓扑结构。
应用数学中最重要的模型,离散数学称之为”图“,一个图包含结点和边。
假设一个电路图,4 个结点,n=4;5条边,m=5

1. 绘制图

绘制图的python代码

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

dg = nx.DiGraph()
dg.add_edges_from([(1,2), (2,3), (1,3), (1,4), (3,4)])
edge_labels = {(1, 2): 1, (1, 3): 3, (1, 4): 4, (2, 3): 2, (3, 4): 5}

pos = nx.spring_layout(dg)
nx.draw_networkx_edge_labels(dg,pos,edge_labels=edge_labels, font_size=16)
nx.draw_networkx_labels(dg, pos, font_size=20, font_color='w')
nx.draw(dg, pos, node_size=1500, node_color="gray")

绘制结果

该图由4个节点与5条边组成,用矩阵来表示这些信息,这个矩阵叫做关联矩阵(IncidenceMatrix);

2. 关联矩阵

用矩阵$A$ 来表示,正负表示方向,每一行表示一条边,将1,2,3 条边表示出来后,这三条边是一个回路,从这个子图的矩阵中,这三行是线性相关的,行1+行2=行3,说明”回路“意味着”相关“,与回路对应的行是线性相关的。

$$\begin{array}{c | c c c c} & node_1 & node_2 & node_3 & node_4 \\ \hline edge_1 & -1 & 1 & 0 & 0 \\ edge_2 & 0 & -1 & 1 & 0 \\ edge_3 & -1 & 0 & 1 & 0 \\ edge_4 & -1 & 0 & 0 & 1 \\ edge_5 & 0 & 0 & -1 & 1 \\ \end{array}$$

我们可以建立$5 \times 4$矩阵
$$A= \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ \end{bmatrix}$$

观察前三行,易看出这三个行向量线性相关,也就是这三个向量可以形成回路(loop)。
关联矩阵源于问题,描述了问题的拓扑结构,它可能是一个非常稀疏的矩阵。

3. 问题1:矩阵的零空间是什么

(回顾:零空间告诉我们,如何对列向量进行组合可得到零向量,如果存在非0 组合则说明列向量线性相关,如果只存在0 组合得到零向量,则说明列向量线性无关)
现在,解$Ax=0$:
$$Ax= \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3\\x_4\\ \end{bmatrix}$$

展开得到:
$\begin{bmatrix}x_2-x_1 \\x_3-x_2 \\x_3-x_1 \\x_4-x_1 \\x_4-x_3 \\ \end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\\0\\ \end{bmatrix}$

4. 引入矩阵的实际意义:

$x=\begin{bmatrix}x_1 & x_2 & x_3 & x_4\end{bmatrix}$设为各节点电势(Potential at the Nodes)。
则式子中的诸如$x_2-x_1$的元素,可以看做该边上的电势差(Potential Differences)。

容易看出其中一个解
$x=\begin{bmatrix}1\\1\\1\\1\end{bmatrix}$
即等电势情况,此时电势差为$0$。它就是整个零空间。

4.1. 零空间维数

化简$A$易得$rank(A)=3$,所以其零空间维数应为$n-r=4-3=1$,即
$\begin{bmatrix}1\\1\\1\\1\end{bmatrix}$就是其零空间的一组基。

4.2. 零空间的物理意义

电势差是产生电流的原因,如果结点电势都相等,将不会产生电流

4.3. 第四个结点接地

当我们把图中节点$4$接地后,节点$4$上的电势为$0$,此时的
$$A= \begin{bmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 0 \\ 0 & 0 & -1 \\ \end{bmatrix}$$
各列线性无关,任意三个结点的电势线性无关,$rank(A)=3$。

5. 问题2:矩阵A 转置的零空间是怎样的?

现在看看$A^Ty=0$(这是应用数学里最常用的式子):

$A^Ty=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}$

对于转置矩阵有$dim N(A^T)=m-r=5-3=2$

5.1. $A^Ty$ 的实际意义是什么?

接着说上文提到的的电势差,矩阵$C$将电势差与电流联系起来,它的元素表示各边上的电流值y1,y2,y3,y4,y5,电流与电势差的关系服从欧姆定律
(欧姆定律:边上的电流值是电势差的倍数,这个倍数就是边的电导(conductance)即电阻(resistance)的倒数。)

$
电势差
\xrightarrow[欧姆定律]{矩阵C}
各边上的电流y_1, y_2, y_3, y_4, y_5
$,而$A^Ty=0$的另一个名字叫做“基尔霍夫电流定律”(Kirchoff’s Law, 简称KCL)。

5.2. 基尔霍夫电流定律

满足解的$y$向量值即是5个满足基尔霍夫电流定律的电流值。

再把图拿下来观察:

将$A^Ty=0$中的方程列出来:
$$\left\{ \begin{aligned} y_1 + y_3 + y_4 &= 0 \\ y_1 - y_2 &= 0 \\ y_2 + y_3 - y_5 &= 0 \\ y_4 - y_5 &= 0 \\ \end{aligned} \right.$$

5.2.1. 解方程时得到如上等式,可看到每个方程表示一个守恒定律:

  • 对比看$A^Ty=0$的第一个方程,$-y_1-y_3-y_4=0$,可以看出这个方程是关于节点$1$上的电流的,方程指出节点$1$上的电流和为零,基尔霍夫定律是一个平衡方程、守恒定律,它说明了流入等于流出,电荷不会在节点上累积。
  • 再比如第二个节点$y_1-y_2=0$ 表示流进来的和流出去的是相等的,结点上不会积累电荷。

5.2.2. 求解的过程我们不用消元法,从上图中看

假设y1=1,那么y2=1,那么y3=-1,右边回路中y4=y5=0 即可;
同样的,看另一组解,设左边回路为y1=y2=0,右边y3=y5=1,y4=-1。得到零空间解

6. 问题3:A的行空间是怎样的?即求$A^T$的列空间。

对于$A^T$,有上文得出其零空间的维数是$2$,则零空间的基应该有两个向量。

6.1. 求基的第一个向量

  • 现在假设$y_1=1$,也就是令$1$安培的电流在边$1$上流动;
  • 由图看出$y_2$也应该为$1$;
  • 再令$y_3=-1$,也就是让$1$安培的电流流回节点$1$;
  • 令$y_4=y_5=0$;

得到一个符合KCL的向量$\begin{bmatrix}1\\1\\-1\\0\\0\end{bmatrix}$,代回方程组发现此向量即为一个解,这个解发生在节点$1,2,3$组成的回路中,该解即为零空间的一个基。

6.2. 求基的第二个向量

根据上一个基的经验,可以利用$1,3,4$组成的节点求另一个基:

  • 令$y_1=y_2=0$;
  • 令$y_3=1$;
  • 由图得$y_5=1$;
  • 令$y_4=-1$;

得到令一个符合KCL的向量$\begin{bmatrix}0\\0\\1\\-1\\1\end{bmatrix}$,代回方程可知此为另一个解。

6.3. 则$N(A^T)$的一组基为

$\begin{bmatrix}1\\1\\-1\\0\\0\end{bmatrix}\quad\begin{bmatrix}0\\0\\1\\-1\\1\end{bmatrix}$

6.4. 看图,利用节点$1,2,3,4$组成的大回路(即边$1,2,5,4$)

令$y_3=0$;令$y_1=1$;则由图得$y_2=1, y_5=1, y_4=-1$

得到符合KCL的向量$\begin{bmatrix}1\\1\\0\\-1\\1\end{bmatrix}$
易看出此向量为求得的两个基之和。

7. 接下来观察$A$的行空间,即$A^T$的列空间

方便起见我们直接计算如下矩阵的列空间。
$$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}$$

易从基的第一个向量看出前三列$A^T$的线性相关,则$A^T$的主列为第$1,2,4$列,对应在图中就是边$1,2,4$,可以发现这三条边没有组成回路,则在这里可以说线性无关等价于没有回路
由$4$个节点与$3$条边组成的图没有回路,就表明$A^T$的对应列向量线性无关,也就是节点数减1,($rank=nodes-1$)条边线性无关。另外,没有回路的图也叫作树(Tree)。

8. 问题4:维数(即回路的数量),结点树,边数的关系

再看左零空间的维数公式:$dim N(A^T)=m-r$,左零空间的维数就是相互无关的回路的数量,
即相互无关(两回路之间无关)的回路数量#loops=边的数量#edges-列空间的秩#rank(等于n-1,结点的数量n,1 为A零空间的维)
于是得到$loops=edges-(nodes-1)$,整理得:
$$
nodes-edges+loops=1
$$
此等式对任何图均有效,任何图都有此拓扑性质,这就是著名的欧拉公式(Euler’s Formula)。$零维(节点)-一维(边)+二维(回路)=1$便于记忆。

9. 本例总结:

这些是在无电源情况下的方程:

  • 将电势记为$e$,则在引入电势的第一步中,有$e=Ax$;
  • 电势差导致电流产生,$y=Ce$;
  • 电流满足基尔霍夫定律方程,$A^Ty=0$;

电源接入方式:在边上加电池(电压源),或在节点上加外部电流 两种。

  • 如果在边上加电池,会体现在$e=Ax$中;
  • 如果在节点上加电流,会体现在$A^Ty=f$中,$f$向量就是外部电流。

将以上三个等式连起来得到$A^TCAx=f$,另外,最后一个方程是一个平衡方程,
还需要注意的是,方程仅描述平衡状态,方程并不考虑时间。
最后,$A^TA$是一个对称矩阵。


技术交流学习,请加QQ微信:631531977
目录