L12-图、网络和关联矩阵

参考

Unit I: Ax = b and the Four Subspaces - GRAPHS, NETWORKS, INCIDENCE MATRICES | pdf
课本章节：Section 8.2 in the 4^th or Section 10.1 in the 5^th edition
练习题：L12-图、网络和关联矩阵-习题集

当线性代数与现实应用相结合时，会从所构建出的矩阵和向量中找到特别的结构信息，这一节课将探索电网 electrical networks 与线性代数的关系。

图

图 Graph 是指结点 nodes 和边/连线 edges 的集合

mermaid

以上的图具有 $n=4$ 个结点和 $m=5$ 条连线

如果为每条连线添加上箭头以表明正方向 positive direction，则这样的图就可以用于描述现实场景，例如电网中的电流方向

mermaid

关联矩阵

可以用矩阵来表示上述具有方向的图，这样的矩阵称为关联矩阵 Incidence Matrix

\begin{aligned} {\color{Violet} node} & {\color{Violet} \begin{matrix} \hspace{0.5em} 1 & \hspace{0.5em} 2 & \hspace{0.5em} 3 & \hspace{0.5em} 4 \end{matrix}} \\ A_{m \times n}=& \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ \end{bmatrix} & {\color{Violet} \begin{matrix} edge1 \\ edge2 \\ edge3 \\ edge4 \\ edge5 \end{matrix}} \end{aligned}

该矩阵的每一行相当于图的一条连线 edge，每一列相当于图的一个结点 node

例如矩阵 $A$ 的第一行就是表示连线 edge 1在图中从结点 node1 指向结点 node2，矩阵中相应的元素分别为 $-1$ 和 $1$ （而与结点 node3 和结点 node4 无关，相应的元素为 $0$ ）

该矩阵在结构上的特点：

矩阵大部分元素都是零，每行只有 $2$ 个非零元素（对应于图中该连线的两个结点），以上实例的矩阵中只有 $2m=2 \times 5=10$ 个非零元素（其中 $m$ 表示矩阵的行，对应于图中的连线 edges 数量），所以矩阵看起来很「稀疏」 sparse
矩阵中线性相关的行，所对应图中的连线会组成 loop 环形回路。例如矩阵的第 1 行、第 2 行和第 3 行向量是线性相关的 $row1 + row2= row3$ ，则对应于图中连线 edge 1、edge 2、edge 3 构成闭合回路（同样，对于置换矩阵 $A^{T}$ 则是线性相关的列对应于图中连线会组成环形回路）

向量空间

关联矩阵的向量空间与实际场景相结合，会有特殊的应用意义。

如果将图是表示一个电网，则图中的结点 nodes 就会存在电势，如果两个结点之间存在电势差则它们之间的连线 edge 就会产生电流，这些属性都可以通过数学等式来描述。

零空间

mermaid

一个由 $n=4$ 个结点和 $m=5$ 条连线构成的图 graph

通过关联矩阵 $A$ 表示以上的图 graph，其中每一行相当于图的一条连线 edge，每一列相当于图的一个结点 node

\begin{aligned} {\color{Violet} node} & {\color{Violet} \begin{matrix} \hspace{0.5em} 1 & \hspace{0.5em} 2 & \hspace{0.5em} 3 & \hspace{0.5em} 4 \end{matrix}} \\ A_{5 \times 4}=& \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ \end{bmatrix} & {\color{Violet} \begin{matrix} edge1 \\ edge2 \\ edge3 \\ edge4 \\ edge5 \end{matrix}} \end{aligned}

关联矩阵 $A$ 的零空间 $N(A)$ 是由方程组 $Ax=0$ 的所有解构成的

\begin{aligned} 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} \end{aligned}

观察该方程组的式子特点，矩阵 $A$ 的作用是计算出（连线上）未知数 $x_{i}$ 之间的差值，因此关联矩阵零空间的实际意义是在电网各点之间的电势差为 $0$ 时（电网处于一个平衡状态），求出各结点的电势。

提示

（消元法）求解 $Ax=0$ （即零空间 $N(A)$ ）的常规步骤：

对矩阵 $A$ 进行变换存在得出相应的上三角矩阵 $U$ $\begin{aligned} 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} \xrightarrow{E} \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \xrightarrow{E} \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ {\color{Blue} 0} & {\color{Blue} 0} & {\color{Blue} 0} & {\color{Blue} 0} \\ 0 & 0 & 1 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \xrightarrow{P} \xrightarrow{E} \begin{bmatrix} {\color{Green} -1} & 1 & 0 & 0 \\ 0 & {\color{Green} -1} & 1 & 0 \\ 0 & 0 & {\color{Green} 1} & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{aligned}$
在消元过程中，第 3 行向量变成零，所以它与第 1 行、第 2 行的向量是线性相关的（所以之后的消元步骤需要使用置换矩阵，将第 4 行与第 3 行调换）
可知矩阵 $A$ 的秩为 $r=3$ ，因此零空间的维度 $dimN(A)=n-r=4-3=1$ （即方程中只有一个自由变量），所以只需要由一个特解就可以张成零空间
如果取 $x_{4}=1$ 则可以求得一个特解 $\begin{aligned} \left\{\begin{matrix} x_{1}=1 \\ x_{2}=1 \\ x_{3}=1 \\ x_{4}=1 \end{matrix}\right. \end{aligned}$
所以方程组的通解是 $\begin{aligned} x=c \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \end{aligned}$

在求解 $Ax=0$ 方程组时，除了通过消元法，还可以先观察方程组的特点，来推理出其解的特点。

由于零空间的向量是使得 $Ax=0$ 成立的，而向量 $x$ 的作用是对矩阵 $A$ 各列进行线性组合，可以先观察矩阵 $A$ 的各列是否存在线性相关，如果不存在，则 $x$ 只能均为 $0$ 时才可以使得 $A$ 中线性独立的各列的线性组合为零向量。那么在这种情况下，零空间就只包含零向量。

对于以上的实例，因为矩阵 $A$ 的第 4 列与第 1 列、第 2 列、第 3 列线性相关 $col4 = -(col1+col2+col3)$ 所以矩阵 $A$ 的零空间除了零向量，还至少存在一个非零向量，其中一个特解如下

\begin{aligned} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \end{aligned}

再结合方程组的等式特点，可以推理出方程组的通解

\begin{aligned} x=c \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \end{aligned}

所以矩阵的零空间 $N(A)$ 是一条直线，其维度 $dimN(A)=1$ 因此矩阵 $A$ 的秩为 $r=n-dimN(A)=4-1=3$

将方程组应用于实际场景，因为矩阵的零空间中存在无限的向量，其通解是 $c\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$ ，即电网各结点的电势相同，但可以是任意值。而如果将电网的其中一个结点接地，则该结点的电势就会为 $0$ ，那么此时整个电网的其他结点的电势也会是 $0$

左零空间

mermaid

一个由 $n=4$ 个结点和 $m=5$ 条连线构成的图 graph

转置矩阵 $A^{T}$ 其列和行正好与关联矩阵 ${A}$ 对调，所以转置矩阵的每一列相当于图的一条连线 edge，每一行相当于图的一个结点 node

\begin{aligned} {\color{Violet} edge} & {\color{Violet} \begin{matrix} 1 & \hspace{0.8em} 2 & \hspace{0.8em} 3 & \hspace{0.8em} 4 & \hspace{0.8em} 5 \end{matrix}} \\ 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} & {\color{Violet} \begin{matrix} node1 \\ node2 \\ node3 \\ node4 \end{matrix}} \end{aligned}

关联矩阵 $A$ 的左零空间 $N(A^{T})$ 是由方程组 $A^{T}y=0$ 的所有解构成的

\begin{aligned} A^{T}y= \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} -y_{1}-y_{3}-y_{4} \\ y_{1}-y_{2} \\ y_{2}+y_{3}-y_{5} \\ y_{4}+y_{5} \end{bmatrix}= \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{aligned}

观察该方程组的式子特点，并结合图 graph 可知，转置矩阵 $A^{T}$ 的作用是描述每个结点的连线情况（而且包括连线的方向）。

如果以上的图是一个电网，且各未知数 $y_{i}$ 表示相应连线的电流值，则方程组 $A^{T}y=0$ 所描述的连线情况就是基尔霍夫电流定律，即经过各结点的流入电流之和等于流出电流之和，所以各个结点就不会积累电荷，即电网处于平衡状态。例如方程组的第一行表示结点 node1 与三条连线相连 edge1、edge3、edge4 的电流是 $y_{1}$ 、 $y_{2}$ 、 $y_{4}$ ，而且它们之和为零，即结点 node1 不积累电荷。

说明

基尔霍夫电流定律 Kirchhoff's Current Law，也称为节点电流定律，是指电路中任一个节点上，在任一时刻，流入节点的电流之和等于流出节点的电流之和，简写为 KCL

其数学表达式为

\begin{aligned} \sum_{k=1}^{n}i_{k}=0 \end{aligned}

由上一节已知矩阵 $A$ 的秩为 $r=3$ ，则根据公式可以求得左零空间的维度 $dimN(A^{T})=m-r=5-3=2$ ，所以只需要由 2 个特解就可以张成左零空间

提示

求解矩阵 $A$ 的左零空间时，可以采用消元法这种常规的步骤，来求解 $A^{T}$ 的零空间，就是矩阵 $A$ 的左零空间

在求解方程组 $A^{T}y=0$ （即左零空间 $N(A^{T})$ ）时，除了通过消元法，还可以先观察方程组的特点，结合图 graph 的实际场景来推理出其解的特点。

mermaid

根据基尔霍夫电流定律，即各结点的流入电流之和等于流出电流之和，其中方程组中 $y_{i}$ 表示流经相应连线的电流。

结合图 graph 的结构，如果连线 edge1 的电流取值为 $y_{1}=1$ 时，对于结点 node2 而言，另一条连线 edge2 的电流就应该是 $y_{2}=1$ 。然后考虑连线 edge3，如果电流取值为 $y_{3}=-1$ ，则与结点 node1 相连的最后一条连线 edge4 的电流就是 $y_{4}=0$ ；而与结点 node3 相连的最后一条连线 edge5 的电流就是 $y_{5}=0$ 。

所以方程组 $A^{T}y=0$ 其中一个特解是（回代到方程组中检验，也成立）

\begin{aligned} \begin{bmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{bmatrix} \end{aligned}

同理可以求得另一个特解是 $\begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix}$

所以左零空间 $N(A^{T})$ 由如下的向量构成

\begin{aligned} c \begin{bmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}+ d \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix} \end{aligned}

观察特解的结构，例如 $\begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix}$ 它分别对应于图 graph 中的 edge3、edge4、edge5 这三条边，它们组成一个loop 环形回路，而这三条边所对应于矩阵 $A^{T}$ 的第 3 列、第 4 列、第 5 列向量是线性相关的 $col4-col3=col5$

欧拉公式

根据两个向量空间的维度，及关联矩阵与图的对应关系，可以得到一个特别的公式

\begin{aligned} loops = edges - (nodes - 1) \end{aligned}

因为左零空间的维度 $dimN(A^{T})=m-r=5-3=2$ ，它正好对应于图中（不重复/非包含关系的） loops 环形回路数量，即只包含内部的「小」环形回路，不算最外一圈

而将关联矩阵 $A^{T}$ 与图 graph 相对应，它的各边对应于图的连线，所以 $m$ 表示 edges 连线的数量

另外根据上一节所求解的零空间 $N(A)$ 可知，该空间的维度（即自由变量的个数）只有 $1$ ，所以秩（也就是主元的数量）就是 $r=n-1=4-1=3$ ，将关联矩阵 $A^{T}$ 与图 graph 相对应，它的各列对应于图的结点，所以 $n$ 表示 nodes 结点的数量

所以 $dimN(A^{T})=m-r=m-(n-1)$ 就相当于 $loops = edges - (nodes - 1)$

其实这个公式不仅对于以上的实例适用，还符合任何的环形的闭合图，这就是欧拉公式，以上通过线性代数来证明了该公式

例如对于以下的图

mermaid

以上的图具有 5 个结点，7 条连线，3 个环形回路

所以 $nodes-edges+loops=5-7+3=1$

疑问

\begin{aligned} nodes - edges + loops = 1 \end{aligned}

如果将公式里的各个元素代表一个维度的值，这样公式适应于更普遍的情况：

nodes 结点，就像是零维度的值（对应于图上一点）
edges 连线，就像是一维的值（对应于图上的一条线）
loops 环形回路，就像是二维的值（对应于图上一个区域）

行空间

mermaid

一个由 $n=4$ 个结点和 $m=5$ 条连线构成的图 graph

关联矩阵 $A$ 的行空间是基于各行的所有可能的线性组合得到的向量集合

\begin{aligned} {\color{Violet} node} & {\color{Violet} \begin{matrix} \hspace{0.5em} 1 & \hspace{0.5em} 2 & \hspace{0.5em} 3 & \hspace{0.5em} 4 \end{matrix}} \\ A_{5 \times 4}=& \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \\ \end{bmatrix} & {\color{Violet} \begin{matrix} edge1 \\ edge2 \\ edge3 \\ edge4 \\ edge5 \end{matrix}} \end{aligned}

为了便于研究，一般将行空间表述为 $C(A^{T})$ ，即由转置矩阵 $A^{T}$ 的各列的所有可能的线性组合得到的向量集合

\begin{aligned} {\color{Violet} edge} & {\color{Violet} \begin{matrix} 1 & \hspace{0.8em} 2 & \hspace{0.8em} 3 & \hspace{0.8em} 4 & \hspace{0.8em} 5 \end{matrix}} \\ 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} & {\color{Violet} \begin{matrix} node1 \\ node2 \\ node3 \\ node4 \end{matrix}} \end{aligned}

由前面章节可知矩阵 $A$ 的秩为 $r=3$ ，根据公式可知行空间的维度是 $dimC(A^{T})=r=3$ ，所以只需要从矩阵 $A^{T}$ 中选择 $3$ 个线性无关的列向量，就可以张成行空间 $C(A^{T})$

根据上一节可知方程组 $A^{T}y=0$ 的两个特解为

\begin{aligned} \begin{bmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix} \end{aligned}

因此矩阵 $A^{T}$ 的第 1 列、第 2 列、第 3 列向量线性相关 $col1+col2-col3=0$ ，而第 3 列、第 4 列、第 5 列向量线性相关 $col3 - col4 + col5 =0$ 。

所以在矩阵 $A^{T}$ 中可以选择第 1 列、第 2 列、第 4 列，这线性独立的三列作为行空间的基

这三列对应于图 graph 三条连线，它们将所有结点（共 4 个）连接起来，并不能构成 loop 环形回路，那么这三条连线所对应的列向量线性独立

说明

将所有结点连接起来，但并不能构成 loop 环形回路，这样的图称为树 tree

电路图描述

如果图 graph 是一个电网，可以使用数学公式对其各个属性进行描述

方程组 $e=Ax$ 描述的是各结点的电势差，其中 $A$ 是关联矩阵， $x$ 是电路中各个结点的电势，则 $e$ 的各行表示相应连线的两端的电势差
工程师可以基于欧姆定律得到一个矩阵 $C$ （该矩阵根据各连线的导电率，与电阻是倒数关系 $\frac{1}{R}$ ），得到方程组 $y=Ce$ 描述的是各连线的电流（连线两端存在电势差，而产生了电流），其中 $y$ 的各行表示相应连线的电流
根据基尔霍夫电流定律，可以得到方程组 $A^{T}y=0$ ，其中 $y$ 是相应连线的电流，该方程组表示流过各结点的电流之和
如果在电网中添加上电源，则以上的方程组变成 $A^{T}y=f$

综合以上的描述，对于一个具有电源的电网，可以用以下数学等式来描述

\begin{aligned} A^{T}CAx=f \end{aligned}

提示

以上等式 $A^{T}CAx=f$ 同时出现了 $A^{T}$ 和 $A$ ，如果两者直接相乘 $A^{T}A$ 会得到一个对称矩阵