飞船空间跳跃问题

本文的问题出自 Williams 的教材《Probability with Martingales》,虽然不算很难但是综合使用了许多知识,展示了抽象的鞅理论其实有着丰富多彩的应用。

问题:一艘太空船正在宇宙中做星际航行时,飞船的控制系统出了故障,飞船不能正常地进行空间跳跃,而是只能预先设定一个距离,然后以此距离进行一次方向完全随机的跳跃。现在的问题是飞船想要返回太阳系。假设太阳系的半径是 \(r\),发生故障时飞船与太阳的距离为 \(R\),这里 \(R>r\)。在每个时刻,飞船能够知道自身与太阳系的距离。

求证:不论采用怎样的跳跃策略,飞船返回太阳系的概率都小于 \(r/R\);但是对任何 \(\epsilon>0\),可以采取适当的策略,使得飞船返回太阳系的概率大于 \((r-\epsilon)/R\),即 \(r/R\) 是最优概率。这个最优策略是什么?

Schur 多项式,Littlewood-Richardson rule 与 Hook 长度公式

在数学中有那么一些问题,它们的表述简单而初等,但是解决起来却非常困难,往往需要相当的奇思妙想和深刻的工具,而且围绕这个问题许多不同领域的数学交织在一起,演绎出许多奇妙的故事来。

Young 表就是其中一个精彩的例子,组合数学,表示论,概率论在这里发生了奇妙的交汇。

我们先从一个有趣的问题开始:

问题\(n\) 位选民要在一次选举中给 \(m\) 个候选人投票,每个选民只能投一票。已知第 \(i\) 位候选人最终的得票数为 \(\lambda_i\),这里 \(\sum_{i=1}^m\lambda_i=n\)\(\lambda_1\geq\cdots\geq\lambda_m\)。问题是:有多少种不同的得票序列,使得在投票过程中的任一时刻,对任何的 \(i<j\),第 \(i\) 位候选人所得的票数总不少于第 \(j\) 位候选人所得的票数?

举个例子,假设有 \(n=10\) 位选民和 \(m=4\) 个候选人,则得票序列 \[1, 2, 1, 3, 2, 1, 2, 4, 3, 1\] 表示第一个选民投票给 1 号,第二个选民投票给 2 号,第三个候选人投票给 1 号,第四个候选人投票给 3 号,依次类推。问题的要求等价于对任何 \(1\leq k\leq n\)\(1\leq i<j\leq m\),序列的前 \(k\) 项中数字 \(i\) 出现的次数都大于等于数字 \(j\) 出现的次数。

虽然问题的表述很简单,但其实答案相当复杂,绝非一般的初等方法所能解决。对付它的最好方法是 Schur 多项式的理论,我接下来就来介绍它。

线性代数杂题若干

二次型的惯性指数问题

我在研究生期间给学弟学妹们当高等代数课助教时,除了改改作业,讲讲习题,还经常需要出一些有点巧妙但又不太复杂的题目,帮助他们理解所学的内容。某一次我出了这样一道题:

问题:我们知道如果 \(A\) 是一个对称矩阵,\(T\) 是一个可逆矩阵,则 \(B=T'AT\) 也是对称矩阵且 \(A,B\) 合同 (congruent),所以它们有相同的正负惯性指数。如果 \(T\) 是不可逆矩阵呢?这时 \(A\)\(B\) 的正负惯性指数有怎样的关系?

当时班上无人能立刻给出答案。

其实这个题目不过是我把他们作业中的一道题改了改说法而已:

Artinian 环与 Wedderburn-Artin 定理

本文目的是介绍 Wedderburn-Artin 的关于半单代数的结构定理。

讲述 Wedderburn-Artin 定理的教材已经是汗牛充栋,证明途径也大同小异,所以本文并不包含新鲜的内容。Wedderburn-Artin 定理在介绍群表示论或者非交换环的书里面基本都可以找到,但是我发现讲群表示论的书往往只针对有限维半单代数的情形介绍最基本的结论,显得不太够用;而讲非交换环的书则往往从 Jacobson 根,密度定理等讲起,包含了过多环论的内容,对初学者又不太友好。这篇文章希望能补上这个空白,用尽可能简洁的篇幅,尽量采用容易理解和记忆的表述,介绍清楚 Wedderburn-Artin 定理证明的来龙去脉。这里采用的是当年 Wedderburn 的思路,即通过极大幂零理想来定义半单性。与通过完全可约性或者 Jacobson 根来定义半单性相比这个思路显得不够现代,但是我想它应该更容易被接受。

不可能的铺砌

依次将 \(1,2,\ldots,n\) 个全等的正六边形摞在一起,得到的图案记作 \(T_n\),下图是 \(n=7\) 的例子:

我们把连在一起的、对称中心在一条直线上的三个正六边形组成的图案叫做一块“骨头”,根据摆放的角度有三种不同的骨头:

我们的问题是:

问题:求证对任何 \(n\)\(T_n\) 都不可能用若干块骨头不重叠不遗漏地恰好铺砌。

这个题目出自 Conway 的论文 "Tiling with polyominoes and combinatorial group theory",在 Thurston 的文章 "Groups, tilings and finite state automata" 中也有讨论。这个题目的难点在于用传统的染色方法是得不出矛盾的,Conway 等人采用的是一个组合群论的途径,即用适当的群元素给铺砌作标记来获得某种铺砌的不变量,并说明区域 \(T_n\) 不满足这个不变量,从而导出矛盾。本文就来介绍这一方法。

关于中心单代数的三个基本结论

本文来自我在讨论班上的一个两小时左右的报告,目的是介绍中心单代数的三个最基本的结论:中心单代数对张量积运算是封闭的,Noether-Skolem 定理,双重中心化子定理。写这篇文章时参考了不少代数学的教材,经过提炼整理得到了本文,希望我的表述做到了清楚易懂。

Jordan 标准形

Jordan 标准形定理是线性代数中的基本定理,专门为它写一篇长文好像有点多余:这方面的教材讲义实在是太多了!一个陈旧的定理还能写出什么新意来呢?

理由有两个。第一个原因是我曾经在做助教给学生讲这个定理的时候,突然发现不知道该怎么启发他们为好。虽然我知道 Jordan 标准形定理的很多种证法,照念几个不在话下,但是感觉有点疙疙瘩瘩的:怎么才能说清定理背后的想法,让学生觉得定理的成立是顺理成章的呢?于是我知道我对这个定理的理解还有模糊的地方。

第二个原因是 Jordan 块有一个重要的代数性质是通常教材中不讲的,而这个性质是代数学中一类重要而常见的性质的雏形,这就是不可分解性。与之对应的是可对角化的线性变换的完全可约性。从一开始就让学生接触这些现象是有好处的。

矩阵空间的子空间

在数学里面经常可以提出这样一些问题:它们叙述起来很简单,答案看起来也很显然,但是要仔细证明却非常困难。即使是线性代数这样的“入门课”中也不缺少这样的问题:

问题:设域 \(\mathbb{F}\) 上的所有 \(n\) 阶矩阵构成的向量空间为 \(\mathbb{M}_n(\mathbb{F})\)\(M\)\(\mathbb{M}_n(\mathbb{F})\) 的一个子空间。

  1. 如果 \(M\) 中的所有矩阵关于矩阵乘法两两可以交换,那么 \(M\) 的维数最大是多少?
  2. 如果 \(M\) 中的所有矩阵的秩都不超过 \(r\),这里 \(0<r<n\),那么 \(M\) 的维数最大是多少?
  3. 如果 \(M\) 中所有矩阵都是幂零的,即对任何 \(A\in M\),存在一个正整数 \(m\) 使得 \(A^m=0\),那么 \(M\) 的维数最大是多少?
  4. 如果 \(M\) 中所有非零矩阵都是可逆矩阵,那么 \(M\) 的维数最大是多少?

棋盘的多米诺骨牌密铺

下面的问题与统计物理中的 Dimer 格点模型有关:

问题:一张 \(8\times8\) 的国际象棋棋盘,用 \(1\times2\) 的多米诺骨牌密铺,有多少种不同的方法?

下图是其中一种 (图片来自 wiki 百科):

答案是 12988816,非常大的一个数字,绝对不是一个一个数出来的。1961 年德国物理学家 Kasteleyn 借助于线性代数中的一个结论首先解决了这个问题,接下来就介绍他的方法。

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器