一个线性代数的应用实例

作者: , 共 887 字 , 共阅读 0
系列:数学之美

查看该系列所有文章

利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:

是否存在不全相等的\(2n+1\)个数\(x_1,x_2,\cdots,x_{2n+1}\),使得任意删除一个数,剩下\(2n\)个数可以均分为 2 组,每组\(n\)个数的和都相等。

如果限定\(x_i\)是整数,这就是一个简单的高中(初中?)数学竞赛中的数论题,

由于\(2n+1\)个数,任意去掉一个数剩下的数的和都是偶数,这意味着所有\(2n+1\)个数的奇偶性相同。如果它们都是偶数,那么将它们都除以 2 ,如果都是奇数,将它们减一再除 2。这样操作之后得到的数仍然满足上面的条件,这样经过若干步之后所有数都相等(等于 0 或者-1 ),这意味着原来的原来的\(2n+1\)个数必然全部相等。

很可惜,如果不要求\(x_i\)是整数,上面的证明就失效了。但利用线性代数里的一些简单事实,我们很快就能得出同样的结论,这样的\(x_i\)必然全部相等

记\(x\)为列向量\((x_1,x_2,\cdots,x_{2n+1})\),假设去掉\(x_i\)之后,剩下来的数可以分为和相等的两等分子集,那么存在行向量\(a_i\)使得\(a_ix=0\),其中\(a_i\)的第\(i\)个位置为 0 ,其余\(2n\)个元素恰好有\(n\)个 1 和-1。

令矩阵\(A=[a_i]\),其中\(a_i\)是\(A\)的第\(i\)行。那么\(Ax=0\),我们证明\(x\)的所有元素都必然相等。

令\(J\)为同样大小的全 1 矩阵,那么\(A+J\)除了对角线上都是 1 之外,其余位置都是偶数,这样矩阵行列式\(det(A+J)\)的表达式中有一个唯一的奇数,这意味着\(det(A+J)\neq 0\),从而\(rank(A+J)=n\),所以\(rank(A)\geq rank(A+J)-rank(J)=n-1\)。

故\(Ax=0\)至多一个非零解,可验证\(x=(1,1,\cdots,1)\)就是它的唯一解。

Q. E. D.

系列: 数学之美 »
写篇三门问题的终结版。欢迎补充材料。
数学 » 概率, 数学之美
这个题目是当年北大概率课上陈大岳老师出的练习题目,当时是一个简单情形,球上 4 个点组成的四面体包含球心的概率。最近在 MITBBS 上看到又有人提及。我在这里写一下解答。
类似文章:
相似度: 0.115
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
【提示: GIF 动画图片较大,有时需等会儿才能显示动画效果。】
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过$ \frac{u}{n}\sum_{i=u}^{n-1}\frac1i$ ,其中$ u$ 为满足$ \sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值。这个$ u$ 大约为 37%,最后成功的概率大约为 40%。
IBM 的 Ponder This 项目每个月会发出一个谜题,这个月的题目是加倍交换数字游戏
数学 » open问题, 图论
孙博告诉我的,求证
数学 » 数学游戏, 概率
600 个人站一排,每次随机杀掉一个奇数位的人,几号最安全?
相似度: 0.063
珍爱生命,远离政治。今天我们讨论一个数学问题。
理论计算机(I)课上讲的一个问题,很有意思。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
发现一个奇怪的现象,对于猪流感,中国和美国的表现完全不同。
碎碎念 » 中国政府
中国政府有些事情管的不严。可有的事情乐此不疲,哪怕有世界舆论的压力一样顶风做。