MIT_线性代数笔记：第 12 讲 图、网络、关联矩阵

图和网络 Graphs & Networks

“图”就是“结点”和“边”的一个集合。

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

关联矩阵（Incidence matrices）

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

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

矩阵的零空间

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

矩阵列空间

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

矩阵的列数为 4，而其零空间的维数为 1，则矩阵的秩为 3，矩阵第 1 列，第 2列，第 4 列的列向量线性无关。
考察矩阵列空间，一个重要的问题就是对于什么样的 b，Ax=b 有解。边①,边②和边③构成了环，这三个行向量线性相关，同样的情况还有边④,边⑤和边③构成的环。于是 b 的分量需要满足 b1-b2+b3=0 以及 b3-b4+b5=0。如果把边①,边②，边④,边⑤构成的大环也表示出来则还可以得到一个等式，但实际上这个等式就是之前这两个等式的组合。这两个等式就是基尔霍夫电压定律（Kirchhoff’s Voltage law）,即环路电势差之和为零。

矩阵的左零空间

矩阵的左零空间是满足 ATy=0 的向量 y 的集合。因为矩阵 AT有 5 列，且矩阵的秩为 3，因此矩阵的左零空间维数为 2。这反应了行向量的线性关系，整个“图”中，环数为 2。

我们求解 ATy=0 就是在求 5 个满足基尔霍夫电流定律（Kirchhoff’s Law）的电流值。

矩阵的行空间

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

思考一下维数公式的在“图”中的意义：
左零空间维数 dim N(AT)=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。