1 2 3 4 5 6 7 »

再谈矩阵与矩阵乘法

以前写了几篇相关的文章,见
《图示矩阵分块乘法》《理解矩阵与矩阵乘积(三)》《理解矩阵与矩阵乘积(二)》《理解矩阵与矩阵乘积(一)》
如果你从网上搜“理解矩阵”或“矩阵乘积”,还可以搜到孟岩写的系列文章《理解矩阵》以及很多其他作者写的文章。尽管经过很多人的努力,试图说清楚矩阵和矩阵的乘积的最本质的意义,这个问题似乎还在困扰着很多人。

我对矩阵和矩阵乘积的意义的认识,基本上在《图示矩阵分块乘法》中已经阐述,但之所以还要写这篇文章,是因为不论是我的文章,还是网络上其他相关文章,都没有做到把这个问题彻底讲清楚,我是学数学的,和很多其他学数学的人一样习惯上以数学抽象的概念去解释另一个概念,所以讲到矩阵总是会提向量空间,会提向量,但工科的学生往往是不会接触向量空间的概念,所以这种解释虽然我们看起来很直观,对工科的学生往往就很难理解了。还有一般的教材里都会讲到的从线性映射的复合的观点去定义矩阵的乘法,但仍然解释不清乘法规则的本质,尤其解释不了矩阵乘法为什么可以分块进行。

我博士的课题是研究随机矩阵,我的导师之一有无线通讯的背景,所以我有幸接触到一个能够更加直观阐释矩阵的概念和矩阵乘法规则的通讯模型,它虽然是个具体的模型,但我认为它有可能触及到了矩阵和矩阵乘法的最本质的东西。

如图一,考虑在 A 地建有一个发射站,其中有 n 个发射塔,B 地一个接收站,有 m 个接受塔。他们之间要传递的是一组由n 个数组成的信息 (x1,x2,...,xn),这样,这组信息可以由这n个发射塔同时发出,然后m个接收塔会同时收到它们发送过来的数据。

telecom
图一:无线通讯模型,发射-接收

但因为距离等因素的影响,每个发射塔发出的信息到不同的接收塔的过程中会有不同程度的衰减,比如第一个发射塔发出的信息x1到第一个接收塔就变成了 a11x1,等等,它们对应的关系可以列成一个方阵:

接收B\ 发射A    1             2             3         ......            n
1                     a11          a12         a13                       a1n
2                     a21          a22         a23                       a2n
...                     .....           ....          ....                         ....
m                    am1         am2         am3                     ann

这个对应关系的表格其实就是我们的矩阵了。有人可能觉得这只是形式上的对应关系,这些元素只是形式上构成了一个矩阵的形状,和我们数学上的矩阵有什么关系呢?矩阵的乘法在哪里呢?其实关系大得很。考虑一下发射站每发射一条信息 (x1,x2,...,xn),那么在接收站接收到的信息会是什么样子?比如第一个接收塔接到的是所有发射塔给它发的信息,那就是 y1=a11x1+a12x2+...+a1nxn,同理第二个接收塔收到的是 y2=a21x1+a22x2+...+a2nxn,等等。
如果凭直观感觉,如果很多发射塔同时发射信息,所有的接收塔收到的都是这些信息相互混杂的结果,似乎接收端很难分辨还原出原始的信息,就像一群人同时向另一群人喊话,每个人听到的只有混在一起的噪声,根本听不清谁到底说了什么,但是从数学上分析一下会发现,只要接收塔不比发射塔少,只要这个方阵的性质足够好,接收端就可以综合所有接收到的信息并计算还原出原始信息,这就是对线性方程组的研究得出的结论。

接下来考虑,如果B只是个中转站,它也要把它接受到的所有信息原封不动地传给C,那就是下图这样:

telecom2
图二:无线通讯模型:发射-中转-接收

那么C最后接到的信息会是什么样?如果像刚才那样分析从B到C的过程,那C接到的信息就是 z1=b11y1+b12y2+...+b1mym; z2=b21y1+...+b2mym,等等。但是,我现在想把B这个中转站从图中隐去,我想直接制定一个从A到C的发射-接收转换列表,我应该怎么制定呢?怎样才能把下面这个列表填完整呢?

接收C\ 发射A    1             2             3         ......            n
1                       ?
2
...
r

根据这个表中元素的定义,第一行第一列的元素(记为c11)应该是最原始的信息中的第一个元素 x1 被发射到最终位置C的第一个接收塔的过程中的衰减系数,而从图中不难看出,这个信息元 x1 首先经过一次衰减到达B的m个中转塔,也就有了 m 个分身a11x1, a21x1,...,am1x1,然后这m个分身又分别经过第二次衰减,并集合到C的第一个接收塔那里,于是变成了 a11b11x1+a21b12x1+...+am1b1mx1,那么自然就有
c11=a11b11+a21b12+...+am1b1m。
同理,A的第 i 个发射塔发出的信息要经过 B 的所有中转塔才能最终到达C处的第 j 个接收塔,这就是乘法矩阵中的 cij 要这样定义的原因。对应下面这个矩阵乘法BA的示意图:发射数据 xi 与矩阵 A 的第i列元素相乘之后到达 B 的 m 个中转塔,得到 yk=akixi,然后中转塔的这 m 个数据又分别和矩阵 B 的第 j 行元素乘积,并在 C 的第 j 个塔那里整合起来,于是就有了 cij 的又乘又加的表达式。
telecom3

这个模型里的通信模型只是用来帮助理解和想象,现实生活中有很多模型都可以体现这样的运算关系,比如把通信站换成物流公司,把信息换成货物,矩阵的元素换成路程或运输成本,这就变成了一个物流模型;把信息换成空间中的向量,每个通信塔换成空间的基底,这就能解释空间中的线性映射,等等。

下面接着用通信模型解释矩阵的分块运算。首先理解什么是矩阵的一个子块:让我们先回到(图一)的没有中转站而只有发射和接收站的情形,然后考虑,原有的系统支持n个信息同时发射,但假设我现在要发射的信息没有那么多,只有 m(<n) 个分量,那么我可以只用其中的m 个发射塔;同时因为发射的数据减少了,也就不需要那么多接收塔了,所以我可以把其中的一些发射塔和接收塔关闭。假设剩下的塔之间传递信息的转换关系不变,那么剩下的那些塔就是原来的一个子系统。因为有些塔不工作,所以我也无需考虑跟它们相关的衰减系数,我们把原来矩阵中所有和关闭的塔相关联的行或列都去掉,剩下的矩阵就是这个子系统对应的衰减系数矩阵。

这样就好解释了为什么矩阵分块的乘法也具有同样的运算法则:还是考虑(图二)描述的发射-中转-接收模型,但我们这次以不同的眼光看:我们把发射、中转和接收塔都分别编组,把一组通信塔看成一个整体,那么一个发射组+一个中转组+一个接收组就构成了一个子系统,它们中间的衰减矩阵自然是大矩阵里的子块;而如果我们对这些子系统进行分析,它们之间的传递关系自然和把它们当成单个通信塔的情形是一模一样的:以下是我以前的文章《图示矩阵分块乘法》里贴过的图,想象每个方格里是一组通信塔,再结合那篇文章中论述的向量空间的模型,就不难理解其中的道理了。
zrclip-003n7bdf3aa5.png

最后多说几句我对线性代数中“线性”的认识。我们上面所有的分析,都是在我们所描述的系统可以分拆这个假设的基础上的,也就是上面所说,假定它的任何一个子系统的运行状态不受系统其它部分的干扰,只有这样,我们才能把输入的原始信息分成若干分量,它们通过系统传递之后再进行整合;也只有这样,我们把系统进行分拆,分别研究各个子系统之后再进行综合才是有意义的。所以,线性代数就是拆拆合合的技术,“线性”是我们进行拆拆合合的基础。

连续的一一映射,其逆映射怎样才连续?

在拓扑学中有很多的反例能够说明,从一个拓扑空间到另一个拓扑空间的连续一一映射,其逆映射不一定是连续的,即使假定两个拓扑空间都是距离空间。

反例1:

 \begin{aligned}f:[0,2\pi) & \to C(0,1) \\ t & \to e^{it}\end{aligned}

它是连续映射,但是其逆映射在单位圆的 (1,0) 点是不连续的。
反例2:

\begin{aligned}f:[0,1)\cup \{2\} & \to [0,1] \\ t & \to \left\{\begin{matrix}t & t<1\\ 1 & t=2 \end{matrix}\right.\end{aligned}

在相对拓扑意义下,f 是连续的,但是其逆映射不连续。

但是,数学各个分支中又有很多定理表明,如果加了某些条件,一个连续的一一映射,其逆映射可以保证也是连续的。如:

命题1:定义在一段连续区间上的实值函数,如果是连续单射,那么它的反函数也是连续的。
命题2(泛函分析中的开映射定理):定义在两个巴拿赫空间之间的连续线性算子,如果是满射,那么它是开映射,即将开集映为开集,那么它如果可逆,其逆映射就一定是连续的。
命题3:复平面上的解析映射是开映射,跟上一个例子类似,如果它可逆,那么它的逆映射是连续的。
更一般的,在拓扑中有这样的事实:
命题4:紧致空间的连续映射的像是紧致的,因此从紧致空间 X 到距离空间 Y 的连续映射是闭映射。

这些例子分别处在不同的数学分支,证明方法也不一样,那么现在的问题是,他们之间是否有某种联系?是否可以从拓扑的角度统一地处理这些问题?是否能在拓扑上提出一个充要条件使得逆映射的连续性能够得到保证?

上面的第四条其实就是对空间提出的拓扑条件,可惜的是,紧致性的条件太苛刻,以至于其它三个例子都不能从4 直接推出来。

Continue reading

用超限归纳法证明《实变函数论》中另一命题

为了建立实数轴上的 Lebesgue 测度,首先需要找一个适当的集合环,在上面建立起满足可数可加性的测度。因此,通常是在环

\mathscr R_0=\left\{\bigcup_{i=1}^n(a_i,b_i]\,|\,a_i,b_i\in\mathbf R,i=1,2,\dots,n \right\}

上定义集合函数

m(E)=\sum_{i=1}^n(b_i-a_i)

其中区间 (a_i,b_i] 为 E 的初等分解。

《实变函数论》中在证明了这个定义的合理性(即 E 的函数值与 E 的初等分解方式无关)之后,作者通过134页(2009清华版124页)引理2.3.2 证明了这个集合函数的一系列性质,包括有限可加性,单调性和有限次可加性,最后证明这个集合函数是环 \mathscr R_0 上的测度,即满足空集的函数值为0;此函数非负,且具有可数可加性。

应该说,引理2.3.2 论证的内容是十分直观的,因为环 \mathscr R_0 上的元素都十分简单,只是有限个左开右闭区间的并。而引理2.3.2的核心内容无非是说,可数多个互不相交的左开右闭区间的总长度,是这些区间长度的和。比如,我们高中理解等比数列和

\sum_{n=1}^{\infty}\frac{1}{2^n}=1

的时候,就是把单位线段无限地二等分,然后看到单位线段的长度等于这些小线段的总长度,这是多么直观的事情。但引理2.3.2的建立过程却非常曲折,为了证明所定义的函数是测度,引理2.3.2被分解成了四个部分,最后一个部分还用到了 Heine-Borel 有限覆盖定理,而这个定理应用的也是极不自然,因为,这里并不是一些开集覆盖住了一个有界闭集,为了应用有限覆盖定理,还必须得给每个区间做一些小手术,这是不容易想得到的。

有没有可能就像高中证明那个无限二分线段长度之和为1那样直接证明这个命题?就是通过有限可加性取极限,就能直接得到可数可加性?用通常的分析思想会有些困难,因为,这里讨论的是可数无限分割,而这种分割的结构可以相当复杂。比如,就在一个简单的连续区间里,这种分划点的极限点就可以有很多甚至无限多,而这些极限点又可能有极限点的极限点,比如上面那个分划的每一个小区间  (\frac{1}{2^n},\frac{1}{2^{n+1}}] 中又可以有可数多个小区间,因此想用取极限的方式去证明一般的命题,有可能需要考虑极限的极限,而且嵌套无穷多次。

Continue reading

徐森林《实变函数论》中有关超限归纳法的一处疏漏

我想趁着假期的时候多复习些内容,所以现在有几门功课正在齐头并进,以便于在一门功课看累了的时候可以换换主题。这其中有实变函数,用的是徐森林的《实变函数论》中科大2002年版。

这本书第68页定理1.5.7(对应于2009清华版59页定理1.4.6):"布莱尔集与实数集等势"的证明过程中,用到了超限归纳法。作者首先以实数集为基础,构造良序集 A,以便有足够多的序数对 \mathscr R\mathscr R_\sigma(\mathscr R) 扩充的无限过程编号。A 实际上等同于最小的不可数序数之前的所有序数构成的集合,即所有可数序数构成的集合。(对于序数的直观描述可参见本博客文章《0.00...1是个什么数?》 打开连接之后在页内搜索"序数")有意思的是,A 中任意一个元素,前面都只有可数多个元素,但 A 本身却是不可数的。这有点类似于自然数集 \mathbf N,任意一个自然数都是有限的,但自然数集本身却是无限的。当然,可数序数和有限序数都没有最大元。

有了合适的序数集,作者便用递归的方式,通过差运算和可数并运算将 \mathscr R 一步步向 \mathscr R_\sigma(\mathscr R) 扩充。第0步,\mathscr R_{a_0}=\mathscr R。假设第 \lambda\in A 步已经完成,那么在第 \lambda +1 步,令

\mathscr R_{\lambda+1}=\left\{\bigcup_{i=1}^{\infty}E_i, E_2-E_1\,|\, E_i\in \mathscr R_\lambda, i=1,2,\dots\right\}

则作者认为对于每一个 a\in A, \mathscr R_a 都定义好了。

我认为,实际上这个递归定义的结果,最多是对于所有的有限序数,即自然数 n 定义好了 \mathscr R_n,而无法遍历 A 中所有的可数序数。因为我们知道,不是所有的序数都是另一个序数的后继,比如第一个无限序数 \omega 就不是任何一个序数的后继,这样的序数称为超越序数。而 A 是个不可数集合,其中无法避免地会出现超越序数。

因此,我把上面的定义过程修改如下:

Continue reading

概率处处有奇论——三门问题和男孩女孩问题

最近,在 mickeylili 的博客 上看到了两个问题,颇有概率奇论的味道,让我想起了当初学习概率的感觉:如履薄冰,甚至怀疑,概率这东西到底是不是一个确定的理论呢?这两个问题是这样:

第一个问题是有名的"三门问题", 亦称"蒙提霍尔问题":

三门问题出自美国电视游戏节目 Let's Make a Deal,问题的名字来自该节目的主持人 Monty Hall.

游戏玩法是:参赛者面对三扇关闭的门,其中一扇门的后面有汽车,另两扇门的后面各有一只山羊,选中后面有车的那扇门就可以赢得汽车,当参赛者选定一扇门,但未开启它时,知道门后情形的节目主持人会开启剩下两扇门的其中一扇,露出其中一只山羊,主持人其后会问参赛者要不要换另一扇仍然关闭的门。

问题是:参赛者换另一扇门会否改变参赛者赢得汽车的概率?

初看问题,会感觉自己陷入两难境地:主持人打开了一扇有山羊的门,给我留下了另外两扇,我不知道这两扇哪一扇后面会有汽车。我第一次选定的,和另外一扇未打开的门,似乎没有什么不同。换,或不换也似乎没有不同。再以概率的角度想,我开始选中有车的门的概率是 1/3,当主持人打开一扇有山羊的门之后,因为已经知道其中一只山羊藏在哪里了,那就相当于在这个条件下,我选中有车的门的"条件概率"变成了 1/2,而另一扇门有车的概率也是 1/2。想想觉得有道理。于是继续看后面答案。

后面给出两种分析,其一大意为,汽车在我选中的门后的概率为 1/3,在另外两扇门之一后面的概率是 2/3,既然另两扇门其一被打开,后面是山羊,那么这 2/3 的概率就集中到另一扇关着的门了,因此应该换门。
另一个大意为,下面三种情况等可能(概率均为 1/3):
我选山羊一号门,主持人选山羊二号,换门将赢得汽车;
我选山羊二号门,主持人选山羊一号,换门将赢得汽车;
我选汽车门,主持人选山羊一号或二号,换门失败。
三种情况有两种换门会赢得汽车,只有一种换门失败,因此换门赢得汽车的概率为 2/3。

老实说,看到这两种分析之后,我头脑里闪现的念头是,这两种分析都有漏洞,都是错的。对于第一种,两扇关着的门是一样的,为什么后面有车的概率一个不变,另一个就变成 2/3 了?为什么不都变成 1/2?难道就因为我选了和我没选的区别?对于第二种,我曾觉得似乎应该是四种情况:
我选山羊一号门,主持人选山羊二号,换门将赢得汽车;
我选山羊二号门,主持人选山羊一号,换门将赢得汽车;
我选汽车门,主持人选山羊一号,换门失败;
我选汽车门,主持人选山羊二号,换门失败。
两成功两失败,不能说换门就提高成功概率。

但是我又无法坚信自己的分析而否定文档的分析,这样我就陷入两难:到底是我错了,还是文档错了?

如果是数学的其它分支,如果两个人得到结果不一样,我们可以很容易验证,因为答案是确定的,大多数情况只要代入一个特殊值,或考虑一个特殊情况,马上就可以验证孰是孰非。但是一个事情发生的概率,你说是1/3,我说是1/2,怎么验证呢?毕竟概率这东西看不到摸不着,它就是可能性的大小,如果不是必然事件或不可能事件,这个可能性的大小是很难捉摸的。即使做实验,它也有可能发生有可能不发生,即使计算频率,而即使频率倾向于支持你的答案,理论上也无法完全否定我。这就是我当初讨厌概率的地方。我总是在想,到底概率这东西有没有意义?客观上存在一个叫概率的东西吗?

对这个问题第二次深入分析,最后文档中第二种分析说服了我。因为我首先看到的是,主持人知道所有门后面的情况,因此他只开有山羊的门。在这种情况下,如果我每次都换门,那么我换门之后得到的东西完全取决于我第一次选中的门。也就是说,既然主持人永远开羊门,那么 如果我开始选中了羊门,换了之后就是汽车;如果我开始选中车门,换了之后就是羊。因此,文档中例举的三个过程,只有第个一步骤是带有随机性的,后面的两个步骤:主持人开羊门,换门得结果,都是在第一步之后就确定下来的。因此,第一步选中羊,等价于换门后得到汽车,其概率显然是 2/3;而第一步选中汽车,也等价于换门后是羊,其概率为 1/3。而如果我坚持不换门,那么第一步选中羊,等价于第三步打开这个羊门,其概率显然是 2/3;而第一步选中汽车,也等价于第三步打开得汽车,其概率为 1/3。

那么到底怎么样利用条件概率来分析这个问题?我先前的分析为什么不对?经过简单的搜索,我发现这个问题还有不同的提法,例如,如果主持人不知道门后的情况,他也是随机地开门,那么在他恰好开了羊门之后,我换或不换,中奖的概率就都是 1/2 了。

主持人开的都是羊门,为什么他知道或不知道门后的情况会影响到我得奖的概率呢?按照日常生活经验是无法理解的。

经过分析,我认为,如果主持人在我选定之后随机地开其余两扇门,然后如果我每次都换门,那么这个过程就相当于把三个不同的门随机排列,假设三个门分别为羊一,羊二,车,那么三个门排列的次序有以下几种等可能情况:
羊一,羊二,车;
羊二,羊一,车;
车,羊一,羊二;
车,羊二,羊一;
羊一,车,羊二;
羊二,车,羊一。
如果已知第二项是羊,那就相当于发生了上面前四种情况之一,在这个条件下,换门中奖的概率为 1/2。同理,不换门中奖的概率也是 1/2,这个问题与条件概率的理论吻合得正好。

如果主持人知道门后的情况而故意不开车门,那么,上面的最后两种排列就演变成了前两种排列,即六种排列演变成:
羊一,羊二,车;
羊二,羊一,车;
车,羊一,羊二;
车,羊二,羊一;
羊一,羊二,车;
羊二,羊一,车;
这样六种情况等可能,那么有四种情况换门得奖,两种情况换门失败。

如果用条件概率公式

P(A_1A_2A_3)=P(A_1)P(A_2|A_1)P(A_3|A_1A_2)

来解释,设 A1 表示我第一次选到羊,A2 表示主持人开了个羊门,A3 表示我换门之后得到车,那么要想换门之后得奖,这三件事必须顺次发生。在主持人知道门后情况的时候,P(A_2)=P(A_2|A_1)=1,否则 P(A_2)=\frac{2}{3}, P(A_2|A_1)=\frac{1}{2}。而 P(A_3|A_1A_2)=1 在两种情况下都成立。那么主持人知情时,有

P(A_1A_2A_3)=P(A_1)P(A_2|A_1)P(A_3|A_1A_2)=\frac{2}{3}

而当主持人不知情时,有

P(A_1A_2A_3)=P(A_1)P(A_2|A_1)P(A_3|A_1A_2)=\frac{1}{3}

但是注意这里已经知道主持人开了羊门,即 A2 已经发生,因此这里求的实际上是

P(A_1A_2A_3|A_2)=P(A_1A_2A_3)/P(A_2)=\frac{1}{2}

这与上面的例举吻合完好。

由此,文档中的第一种分析就有些问题了,因为第一种分析没有用到主持人知情这个条件,它可以完全不加改变地应用到主持人不知情而恰巧开启羊门的情况,同样得到这时换门的胜算更大。而实际上这时换不换门得奖的概率是一样的。

第二个问题是关于生男生女的概率问题,这个问题出现在有关条件概率的内容后面。首先讨论了这样的问题:人的生育过程决定,每次生育,生男孩和生女孩的概率基本一样。那么一个家庭有两个孩子,以下四种情况就有等可能的机会出现:男男,男女,女男,女女。现在已知一个家庭至少有一个女孩,那么另一个也是女孩的概率是多少。因为已知至少有一个女孩,排除了第一种男男的可能性,在剩下三种可能当中,最后一种是符合要求的组合,因此这个概率是 1/3。

现在问题变化一下,已知一个朋友家里有两个孩子,你去了他家,开门的是女孩,现在问另一个你还没见到的孩子是女孩的概率。

如果受到上一题目影响,开门的是女儿,但是不知道开门的是老大还是老二,因此我们只能由此推断出,他家至少有一个女孩,那么另一个孩子是女孩的概率就是 1/3。

但是,我又明显感觉到这里面有问题,因为,如果这个推理正确,那么,假设一位母亲怀了双胞胎,排除同卵的情形,临产时先生出个女孩,那么护士是否可以说,老二是女孩的概率是 1/3?这和上面排列推断出的概率不同,因为已知老大是女孩的情况下,老二是男是女依然各占一半。再设想,抛开两个孩子出生顺序,只是假设一个屋子里有两个人,每个人是男是女概率各占一半,那么第一次出来个女的,问屋子里剩下的那个人是女的概率?这样根据出屋顺序,也有四种可能:男男,男女,女男,女女。第一个是女的,排除两种情况:男男、男女。则剩下个女的可能性是 1/2。

那么问题出在哪里?难道"我见到一个孩子是女孩"和"已知一个孩子是女孩"不一样?

因为这个问题在文档中以思考题出现,文档中没有答案,所以我也不知道正确答案到底是哪个。经过分析,我认为,之所以出现 1/3 这个数,是因为我们始终坚持认为出生时的四种排列顺序(男男,男女,女男,女女)是等可能出现的。这是正确的。而"我去他家,见到开门的孩子是女孩",相当于做了另一个随机试验,再一次引入一个随机事件,即"两个孩子,随机地见到一个,是女孩",这就跟"确定至少有一个女孩"有所不同了。如果用试验模拟"随机见到女孩"的过程,那么这个试验大概如下:

从一堆红球白球里随机地抽出两个放在黑盒子里,每次抽取红球和白球的概率都是1/2;然后再从黑盒子里任意掏出一球,发现是白球,问剩下的球是白球的概率。

将黑盒子里两球编号,那么两球有四种情况等可能出现:M1=1红2红,M2=1白2白,M3=1红2白,M4=1白2红。然后在每种情况下分析第二次随机试验。设 A 事件为,"第一次摸出白球",B 事件为"剩下那个是白球"。问题归结为求 P(B|A)。首先,P(AB)=1/4(因为 AB 发生等价于上面的 M2)。那么接下来只要求出 P(A) 即可。而根据全概率公式,

P(A)=P(A|M_1)P(M_1)+P(A|M_2)P(M_2)+P(A|M_3)P(M_3)+P(A|M_4)P(M_4)=\frac{1}{2}

因此最后结果为

P(B|A)=P(AB)/P(A)=\frac{1}{2}

这样,在一段时间的努力下,两个险些毁三观的问题终于没有逃脱出概率论的框架。