线性代数的终极彩蛋：矩阵就是图

luyuanhong

线性代数的终极彩蛋：矩阵就是图

原创 JJJohn AGI Hunt 2024 年 08 月 13 日 01:06 北京

你眼中枯燥无味的线性代数，其实暗藏着一个超级彩蛋！

Santiago 今天在推特上发文爆料道：

线性代数中最被低估的事实：

矩阵就是图，图就是矩阵。

用图来编码矩阵简直就是开挂，让复杂的行为变得易于研究。

Santiago 是一位计算机科学家和作家，他偶尔还在 YouTube 上教授硬核机器学习。

不过 Santiago 也很诚实，这个爆料其实是来自 @TivadarDanka 。三年前，Tivadar 就开始写一本关于机器学习数学的书，其称这本书是“你能读到的最好的书”。

那么，这个“矩阵=图”的彩蛋究竟是什么样的呢？

Santiago 给出了一个简单的例子：



相信聪明的你看图就能猜到规则了。

每一行代表一个节点，每个元素代表一条有向加权边。我们省略了所有权重为零的边。

第 i 行第 j 列的元素对应着从 i 到 j 的一条边。

比如，我们来看第一行，它对应着从第一个节点出发的所有边：



同理，第一列对应着所有指向第一个节点的边：



这样，我们就得到了完整的图：



有网友看到这里就兴奋了：

我的天，这不就是我们在做社交网络分析时用的邻接矩阵吗？原来它在线性代数里还有这么深的含义！

没错，这个表示方法确实在很多领域都有应用。但是，它的威力远不止于此。

Santiago 指出，矩阵的幂对应着图中的“行走”。

看看矩阵的平方，所有可能的 2 步行走都被考虑在内了：



如果这个有向图表示的是马尔可夫链的状态，那么它的转移概率矩阵的平方本质上就显示了链在两步之后处于某个状态的概率。

我大学的线性代数老师怎么就没讲过这个？这么看图也太形象了。

但这只是冰山一角。Santiago 接着介绍了“强连通分量”的概念。

一个有向图如果从任何节点都能到达任何其他节点，就叫做强连通的。如果不是这样，那就不是强连通的。



对应于强连通图的矩阵被称为不可约的。所有其他非负矩阵被称为可约的。

（为了简单起见，Santiago 假设每条边的权重都是 1 ，但实际上每个权重可以是任意非负数。）



即使不是所有的有向图都是强连通的，我们也可以将节点划分为强连通分量：



让我们给这个图的节点贴上标签，然后构造对应的矩阵：



看出规律了吗？

这个图对应的矩阵可以简化成一个更简单的形式！

它的对角线由一些块组成，这些块的图是强连通的。（也就是说，这些块是不可约的。）而且，对角线下方的块是零。



一般来说，这种块矩阵结构被称为 Frobenius 标准型。



那么，反过来，我们能把任意非负矩阵变成 Frobenius 标准型吗？

答案是肯定的，而且借助有向图，这比纯粹使用代数要容易得多。



这还只是冰山一角。例如，借助矩阵，我们甚至可以定义图的特征值！

利用矩阵和图之间的关系，对图论和线性代数都产生了极大的推动作用。

看到这里，是不是终于明白为什么那些搞机器学习的人总是在谈论矩阵和图了？因为它们就是一回事啊！

这个连接确实非常重要。Santiago 最后也强调，这个帖子只是完整内容的 30% 左右。如果想了解更多，可以去看 Tivadar 的书。

你找不到比这更好的解释了。相信我，这是你想读的书。

看完这个帖子，有没有再次感受到数学才是科学的基础？

数学就像一个巨大的宝库，每一个概念背后都隐藏着无数的宝藏。只是我们平时学习的时候，往往只看到了表面，没有深入挖掘。

Tivadar 书中展示的，就是其中一个宝藏。它不仅让我们对线性代数有了新的理解，还能让人们更轻松地通向机器学习的大门。

你有没有在学习过程中发现过类似的“彩蛋”呢？

相关链接

[1] https://twitter.com/svpino/status/1822966774985560542

AGI Hunt