MIT线性代数笔记十二 图、网络、关联矩阵

  本讲讨论线性代数在物理系统中的应用。可参考链接为：https://www.juanklopper.com/wp-content/uploads/2015/03/I_13_Graphs_Incidence_matrices_Kirchhoff_laws.html

1. 图和网络 Graphs & Networks

  图是结点(node)和边(edge)的一个集合。

  边线上的箭头代表从结点流出的正方向。上图里包含 4 个结点，5 条边，我们可以将每条边都指定参考方向用于区分正负，比如一个电路网络。 在此例子中，将使用电势、回路、电流之类的词汇（当然这个模型还可以表示为液压系统、建筑结构等）。我们通过构造一个incidence matrix 关联矩阵来解析这个图的含义。

2. 关联矩阵（Incidence matrices）

  构造一个矩阵来表示图的内在含义，此矩阵称为关联矩阵，图中每个结点代表一列，每边代表一行。 则上图为$5\ast 4$矩阵。 反过来从这个矩阵出发我们也能画出图。

  第一行代表边①，从结点 1 流出记为-1，从结点 2 流入记为 1。也就是从结点1流向了结点2。

  边①、边②和边③构成了一个回路，称为环（loop）。反映在矩阵上是这三个行向量线性相关。

  源于现实问题的关联矩阵，通常描述了问题的结构。如果我们研究一个很大的图，则会构建一个很大的矩阵，但这个矩阵会是稀疏矩阵。

2.1 零空间

  考察矩阵的零空间，即求$Ax=0$的解。零空间告诉我们列向量线性组合的状态。这里$x$的分量表示的是每个节点。

$$Ax=\left[\begin{array}{c}{x}_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_1\\ x_4-x_3\end{array}\right]=\left[\begin{array}{l}0\\ 0\\ 0\\ 0\\ 0\end{array}\right]$$

  如果$x$为结点上的电势，则$Ax$给出了每个边上的电势差。 求解可以得到零空间为一维$dimN(A)=1$，它的基就是$\left[\begin{array}{l}1\\ 1\\ 1\\ 1\end{array}\right]$，解集则是$x=c\left[\begin{array}{l}1\\ 1\\ 1\\ 1\end{array}\right]$，代表等电势，说明等电势条件下不会有电流产生。常数 c 的确定需要边界条件，比如我们将结点 4 接地，则 $x_4=0$。

2.2 列空间

  若求$Ax=b$的解，则相当于在给定了电压$b$的情况下，求各点的电势，但实际上我们得不到电势的准确值，因为零空间有常数解$c$，各点得到的电势需要加上常数$c$，这很类似于求积分要加上常函数，常数值需要边界条件来确定。

  矩阵的列数为 4，而其零空间的维数为 1，则矩阵的秩为 3，矩阵第 1 列、第2列和第 4 列的列向量线性无关。

  考察矩阵列空间，一个重要的问题就是对于什么样的 $b$，$Ax=b$有解。边①、边②和边③构成了环，这三个行向量线性相关，同样的情况还有边④、边⑤和边③构成的环。

  我们沿着第一幅图中的一个环边（1，3，-2）对电势差求和：
$$(x_2-x_1)+(x_3-x_2)-(x_3-x_1)=0$$

$$x_2-x_1=b_1,x_3-x_2=b_3,x_3-x_1=b_2$$

  所以$b$的分量满足$b_1+b_3-b_2=0$以及$b_3-b_4+b_5=0$。如果把边①、边②、边④、边⑤构成的大环也表示出来则还可以得到一个等式$b_1-b_2+b_4-b_5=0$，但实际上这个等式就是之前这两个等式的组合。这两个等式就是基尔霍夫电压定律（Kirchhoff’s Voltage law），即环路电势差之和为零。

2.3 左零空间

  矩阵的左零空间是满足$A^{T}y=0$的向量 y 的集合。 其中$y$的每个分量表示的是每个边。 因为矩阵$A^T$有 5 列，且矩阵的秩为 3，因此矩阵的左零空间维数为 2。这反应了行向量的线性关系，整个“图”中，环数为 2。

$$A^{T}y=\left[\begin{array}{ccccc}-1& 0& -1& -1& 0\\ 1& -1& 0& 0& 0\\ 0& 1& 1& 0& -1\\ 0& 0& 0& 1& 1\end{array}\right]=\left[\begin{array}{l}0\\ 0\\ 0\\ 0\end{array}\right]$$

  其中y的分量的值为“边”上的电流。

  在电势差和电流之间建立联系就是欧姆定律（Ohm’s Law）。

  我们求解$A^{T}y=0$就是在求 5 个满足基尔霍夫电流定律（Kirchhoff’s Law）的电流值。

  $A^{T}y=0$的方程形式$\{\begin{array}{r}-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{array}$，每一个方程关于一个结点，方程表示结点电流值为 0，即流入等于流出。

  从图上解方程，而不是采用消元法解方程。如果我们设定 $y_1=1$，并且让$y_1$、$y_2$ 和 $y_3$组成的回路的“环流“为 0，则有 $y_2=1$，$y_3=-1$。可解得$y=\left[\begin{array}{c}1\\ 1\\ -1\\ 0\\ 0\end{array}\right]$。取另一个回路的环流为 0，则有$y_3=1$，$y_4=-1$，$y_5=1$。 $y=\left[\begin{array}{c}0\\ 0\\ 1\\ -1\\ 1\end{array}\right]$

  如果设定$y_1$、$y_2$、$y_4$和$y_5$组成的大回路环流为 0，则可以得到另一个向量 y，而该向量在零空间内，是前两个向量的线性组合。

2.4 行空间

  考察矩阵的行空间，因为矩阵$r=3$，所以存在 3 个线性无关的向量。**第 1 行、第 2 行和第 4 行为线性无关，在“图”中，边①、边②和边④构成了一张小图，这三个边没有形成回路。**线性相关问题等价于形成回路。没有回路的小图包含4个结点和 3 条边，再添加一条边就会产生回路，在矩阵里表现为在第 1 行、第 2 行和第 4行之上再添加一个行向量就会变为线性相关。没有回路的图称为“树”。

  思考一下维数公式的在“图”中的意义：
  左零空间维数$dimN(A^T)=m-r$；
  等价于$“环”数量=“边”数量-（“结点”数量-1）$；
  即 Eular 公式：$“结点”-“边”+“环”=1$。对所有图都成立。
  矩阵的秩$r=“结点”-1$，因为 r 表示了线性无关的边的数目，也就是“树”中“边”的数目。

  之前的讨论都是针对于一个无源的电场，如果加入电源则情况又不同，例如加入电流源相当于将基尔霍夫定律的方程变为 $A^{T}y=f$，f 就是外部流入的电流。

  将$e=Ax$，$y=Ce$，$A^{T}y=f$，三个等式结合得到应用数学中的基本方程$A^{T}CAx=f$。

  $v=Au，y=Cv，f=A^{T}y$。

  关于方程$A^{T}CAx=f$的更多内容可以阅读 GS 老先生 08 的书“Computational science and engineering”的第二章。