边看边说序列的宇宙学(六)

摘要

我们可以用线性代数的语言和工具来表述和研究边看边说序列的演化问题。算术定理叙述的,实际上就是当n趋向于无穷时,矩阵Mn的性质。康威在论文中提到的Perron–Frobenius定理,就是这样一个阐述矩阵的幂的极限性质的定理。

(图片来源:https://en.wikipedia.org/wiki/Linear_algebra)

(图片来源:https://en.wikipedia.org/wiki/Linear_algebra)

八、线性代数的语言

现在我们来讨论本文最有意思的部分,关于算术定理的证明。这部分证明必须用到线性代数的知识,所以从现在起我假设读者了解线性代数的一般知识。

根据元素列表中的“一天后衰变物”一栏,我们定义一个92×92的矩阵M,它在第i行第j列处的值为第j号普通元素一天后衰变物中的第i号普通元素的数量。比如说1氢的一天后衰变物仍是1氢,于是矩阵的第1列只有在第1行处的值为0,其余均为0;而31镓的一天后衰变物是63208912030锌,于是M的第31列在第1、30、63和89行处的值为1,在第20行处的值为2,在其余行处的值为0。我们把这个矩阵称为边看边说矩阵

矩阵M的规模比较大,在网页上不容易完整地表示出来。好在它的元素很简单,大多数是0,其余的基本都是1,只有一个值是2,所以我们可以用下图中点阵的方式来表示这个矩阵,其中每个白点表示此处值为0,黑点表示1,红点表示2。

M的点阵表示

M的点阵表示

矩阵M包含了普通化合物演化的几乎所有信息。说“几乎”是因为它和第六节中的计算一样,忽略了演化过程中各元素间顺序的信息。对任意一个普通化合物C,我们都可以写出一个有92个分量的列向量u来,它的第i个分量是C中第i号普通元素的数量,我们称它为普通化合物C对应的向量

任何一个普通化合物C,如果它在次日演化成C',那么容易看出,C'对应的向量u'=Mu,也就是说“左乘M”代表了“演化1天”的操作(但是忽略了元素次序)。想知道C'再过一天的演化结果所对应的向量,只要在u'左边再乘以一个M,所以是M2u,这是C演化2天后所得化合物对应的向量。如此下去,C在第n天的演化结果所对应的向量就是Mnu这就把(忽略了元素顺序的)普通化合物演化过程完全地用线性代数的语言表述出来

比如第六节中那个表格现在就可以用矩阵的语言相当简明地表达。令u是第50、72分量为1,其余分量为0的列向量(对应于第8天的普通化合物7250锡),“化合物中元素个数”一栏表述的其实就是向量Mn-8u的各个分量,其中n是以1开始的边看边说序列的项数。

于是我们可以用线性代数的语言和工具来表述和研究边看边说序列的演化问题。算术定理叙述的,实际上就是当n趋向于无穷时,矩阵Mn的性质。康威在论文中提到的Perron–Frobenius定理,就是这样一个阐述矩阵的幂的极限性质的定理。我们先来看一下它的经典形式。

 

九、Perron–Frobenius定理

如果A是一个其中元素都是正实数的m阶正方矩阵。Perron–Frobenius定理断言,A的特征多项式必定有一个单的正实根μ,而且它严格大于所有其他的根的绝对值(其他的根有可能是复数)。我们知道这个根μ是A的一个特征值,Perron–Frobenius定理说,它必定有一个所有分量都是正实数的特征向量v。因为μ是单根,所以它的特征空间是1维的,就是由v生成的。

当我们说一个矩阵的“特征向量”时,我们通常指的是它的特征向量,也就是说Avvv是一个列向量(或可以说是一个m×1的矩阵)。但A同样也有关于μ的特征向量w,它可以看作是A的转置矩阵tA的(右)特征向量的转置,是一个行向量(或可以说是一个1×m的矩阵),满足wAww当然也可取成其中分量都是正实数的,而且我们还增加一个要求,要求wv=1(行向量乘以列向量的结果可以看作是一个数,也叫这两个向量的内积),这可以通过将w乘以合适的系数做到。

Perron–Frobenius定理进一步说,当自然数n趋向于无限时,矩阵序列{(1/μn)An}的极限是矩阵vw(不要和上面的wv=1的要求搞混了,列向量乘以行向量的结果是m阶正方矩阵)。

这实在是一个非常漂亮的定理!要是它适用于边看边说矩阵M的话,Mn在n趋于无穷时的性质就可以通过计算M的特征值和特征向量得到,算术定理也就唾手可得了。

很遗憾,至少是在康威写作论文的那个时代,Perron–Frobenius定理对M并不适用——它的系数充满了不是正数的0。Perron–Frobenius定理也存在着其他一些形式。在某些形式里,条件被放宽为矩阵的元素可以是大于或等于0的实数,但矩阵必须是不可约的或是对称的,或是存在某个k使得Mk的元素都严格大于0,这些也是M所不能满足的——因为M显然不对称,而由于1氢元素的性质,M的第一列除了第一项外都等于0,这使得它是可约的,而且对任何自然数n,Mn的第一列除了第一项外也都等于0。

在这里岔开去说一点,Perron–Frobenius定理是相当有用的一个定理。在实际当中我们常会碰到元素均大于0或是均大于等于0的矩阵,最常见的有马尔科夫链的状态转移矩阵和图论中的邻接矩阵。Google公司搜索引擎的核心技术PageRank(网页排名)就是基于转移矩阵理论和对上面所说的那个特征值的计算,而Perron–Frobenius定理则保证了这个特征值的存在性。从理论上来说,Google要对付的那个矩阵的行和列数,和它搜集的网页数相等,是当之无愧的巨无霸矩阵。如何对它作特征值计算,大概是Google最重要的商业秘密之一,当然这是本文的题外话了。

 

参考文献:

[1] John Horton Conway, The weird and wonderful chemistry of audioactive decay, Eureka 46:5-16 (1985); reprinted in Open Problems in Communication and Computation, T.M. Cover & B. Gopinath, eds., Springer-Verlag, New York, 173–188 (1987).

 

扩展阅读:

边看边说序列的宇宙学(一)

边看边说序列的宇宙学(二)

边看边说序列的宇宙学(三)

边看边说序列的宇宙学(四)

边看边说序列的宇宙学(五)

您还未添加分享代码,请到主题选项中,添加百度分享代码!

您可以选择一种方式赞助本站

安安以迁迁

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

图片 表情