原文衔接
线性代数最被低估的一个实际：矩阵是图，图是矩阵。
将矩阵编码为图是一种取巧的行为(cheat code)，它其使杂乱的行为变得易于研究。
让我告诉你怎么做！
1. 非负矩阵的有向图 （The directed graph of a nonnegative matrix）
假如你看了上面的比如，你或许就明白了这个规矩。
每一行都是一个节点，每个元素代表一条有向加权边。零元素的边被省略。第 i 行第 j 列中的元素对应于从 i 到 j 的一条边。
得到的图称为矩阵的有向图（或有向图）。
为了略微打开一下界说，让咱们检查第一行，它对应于从第一个节点传出的边。
类似地，第一列对应于传入第一个节点的边。
这是完好的图片，节点被明确符号。
2. 图表明的好处(Benefits of the graph representation)
为什么有向图表明对咱们有利？
其一，矩阵的幂对应于图中的搬运(the powers of the matrix correspond to walks in the graph)。
看一下方阵的元素。一切或许的 2 步 搬运(2-step walk)均计入界说 A 元素的总和中。
假如有向图表明马尔可夫链的状况，则其搬运概率矩阵的平方本质上表明该链在两步后具有某种状况的概率。 . 这种联系还有更多内容。
例如，它让咱们深入了解非负矩阵的结构。
为了了解图表明为矩阵的状况，咱们来讨论一下强连通重量的概念。
3. 图的连通性(The connectivity of graphs)
假如每个节点都能够从每个其他节点抵达，则有向图是强连通的。
假如这不建立，则该图不是强连通的。
下面，您能够看到两者的示例。
对应于强连通图的矩阵称为不行约矩阵。一切其他非负矩阵都称为可约矩阵。很快，咱们就会知道原因。(判别矩阵是否是一个不行约矩阵还有一个等价方法，便是看矩阵对应的有向图是否是强连通图)
（为简略起见，我假定每条边都有一个单位权重，但实际中每个权重能够是任意非负数。）
回到一般状况！
尽管并非一切有向图都是强连通的，但咱们能够将节点划分为强连通的 子组件。
让咱们符号这个图的节点并结构相应的矩阵！
（为简略起见，假定一切边都有单位权重。）您留意到某种模式了吗？
图对应的矩阵能够简化为更简略的方法！
它的 对角矩阵 由图强连通的 子矩阵块组成。 （也便是说，子矩阵块是不行约的。）此外，对角线下方的块为零。
关于一切非负矩阵都是如此吗？
你猜猜。下边进入Frobenius normal form。
4. The Frobenius normal form
一般来说，咱们刚刚看到的这种块矩阵结构称为Frobenius normal form。
假如你的眼睛很敏锐，而且有点强迫症，你或许会留意到我略微改动了颜色。从现在开始，不行约块（又叫对应于强衔接图的矩阵）将是米黄色，而可约块将是浅蓝色。
让咱们把问题反过来：咱们能够将任意非负矩阵转换为 Frobenius normal form？
是的，在有向图的协助下，这比纯粹运用代数更简略显现。
这是闻名定理的完好方法。
但什么是置换矩阵（permutation matrices）？
5. Permutation matrices 置换矩阵
让咱们看一个特别状况：假如咱们 将 2 x 2 矩阵乘以
一个简略的零一矩阵 ？经过快速核算，您能够验证
当从左面相乘时它会切换行，
当从右侧相乘时它会切换列。
像这样：
从左边和右侧乘以 P 会产生复合作用：它会切换行和列。
（趁便说一下，这是一个类似改换，由于咱们特别的零一矩阵是它自己的逆矩阵。这不是偶然的；稍后会具体介绍。）
咱们为什么要看这个？由于在幕后，这种转换（类似改换即从左边和右侧乘以 P ）不会改动底层的图结构，只是从头符号其节点！
您能够轻松地手动验证这一点，但我在下面为您可视化了它。
在一般的 n x n 状况下也存在类似的现象。在这里，咱们经过交换单位矩阵的第 i 行和第 j 行来界说所谓的转置矩阵：
与转置矩阵(transposition matrix)相乘具有相同的作用：从左边切换行，从右侧切换列。
咱们不会具体说明它（由于过于杂乱的符号使它特别痛苦），但您能够手动验证这确实是正在发生的工作。
这是一个简短的总结。请记下这些，由于它们很快就会变得至关重要。
对咱们来说最重要的性质：运用转置矩阵(transposition matrix)的类似改换只是从头符号两个节点，但在其他方面使图结构保持不变。
现在，关于前面说到的置换矩阵（permutation matrices）。置换矩阵只是转置矩阵（ transposition matrices）的乘积。
置换矩阵(Permutation matrices)从其构建块承继了一些性质。最重要的是，
their inverse is their transpose,
-
它们的逆是它们的转置，
-
它们的
类似改换只是节点的从头符号，使图结构保持不变。
要了解后一个，请考虑下面的观点。
(Recall that transposing a matrix product switches up the order, and transposition matrices are their own transposes.)
（回想一下，转置 一个 矩阵乘积 会改动次序，而转置矩阵便是它们自己的转置。）
Conversely, every node relabeling is equivalent to a similarity transformation with a well-constructed permutation matrix.
相反，每个节点从头符号相当于具有结构良好的置换矩阵(permutation matrix)的类似改换。
咱们为什么要谈论这个？由于节点的正确符号是 Frobenius normal form的关键。
6. 有向图及其强连通重量（Directed graphs and their strongly connected components）
现在，咱们来谈谈图。咱们将看到每个有向图如何分解为强通的重量。为此，让咱们看一个具体的。
从给定节点能够抵达多少个节点？纷歧定是全部。比如说，关于右下角的那个，只能拜访图表的一部分。
然而，彼此可达的节点集要小得多。
从代数上来说，“a和b互可达”的联系是等价联系。换句话说，它将节点集划分为不相交的子集，使得
-
来自同一子集的两个节点彼此可达，
-
而且来自不同子集的两个节点不能彼此可达。
（等价联系是数学的主力。假如您不熟悉它们，请检查这篇关于分区的维基百科文章，了解它们之间的联系。）
该分区的子集称为强连通重量，咱们总是能够用这种方法分解有向图。
现在，让咱们将一切内容衔接在一同！ （不是以图的方法，但你知道，以健康的数学方法。）
7. 将图和置换矩阵放在一同 (Putting graphs and permutation matrices together)
咱们距离证明每个非负方阵都能够经过置换矩阵改换为 Frobenius normal form还有两步。
这是方案。
-
为咱们的非负矩阵构建图。
-
找到强连通重量。
-
以奇妙的方法从头符号节点。
便是这样！为什么？由于，正如咱们所见，从头符号图节点与运用置换矩阵(permutation matrix)的类似改换相同。
只要一个小问题：最好的完成方法是什么？接着往下看！
首先，咱们“骨架化”图：将 组件（components） 以及它们之间的任何边兼并在一同。将每个 组件 视为一个黑盒子：咱们不关怀里边有什么，只关怀它们的外部衔接。
在这个骨架中，咱们能够发现无法从其他组件进入的组件。这些将是咱们的起点，即第零类组件。在咱们的示例中，咱们只要一个。
Now, things get a bit tricky. We number each component by the longest path from the farthest zero-class component from which it can be reached.
现在，工作变得有点棘手。咱们按照距离最远的零类组件的最长路径对每个组件进行编号。
这甚至都很难阅览，更不用说理解了。所以，这便是发生的工作。
关键是，假如您能够从第 n 级抵达第 m 级，则 n < m。
最后，咱们有以下内容。
这界说了组件的次序。 （假如您想更精确，则为部分排序。）
现在，咱们符号里边的节点，这样
-
高阶类优先(higher-order classes come first,)
-
假如或许的话，连续索引是来自同一组件的标签节点。(and consecutive indices are labeling nodes from the same component if possible.)
便是这样。
假如图本身来自实际矩阵，则这种从头符号会产生 Frobenius normal form！
下面是这个特定示例中的矩阵，为了简略起见，运用了 0 和 1：
咱们奇妙符号的图的邻接矩阵
现在一切都已完成，Frobenius normal form改换背后的“证明”也完成了！
提醒您，这是该定理的完好方法：
8. 定论
咱们所看到的只是冰山一角。例如，借助矩阵，咱们能够界说图的特征值！这个想法催生了谱图理论这个诱人的论题，这是一个美丽的数学范畴。
使用矩阵和图之间的联系关于图论和线性代数来说都是非常有利可图的。
假如你对细节感兴趣，我有两本书推荐给你。其中之一是 Richard A. Brualdi 和 Dragos Cvetkovic 撰写的精彩的《矩阵理论及其应用的组合方法》，这是我最喜欢的关于该主题的学习资源。
其次，我最近写完了机器学习的线性代数书。尽管这篇文章的内容还不是本文的一部分，但电子书格式的好处是我能够随时返回并添加新的章节。
因此，我方案将这篇文章扩展为类似教科书的章节，并或许附带交互式代码示例。假如您有兴趣，请检查我的书的前两章！
