三个问题

zgg___

我这里给大家提三个问题，但愿能够抛砖引玉，起到解闷的作用，呵呵。
这些问题个人觉得比较好玩，我想前人必然是做过的，但我没有什么很好的思路，请大家指点。

第一题：
这个问题的由来是这样滴：mathe曾在blog中提出所谓的“Fibonacci矩阵”（参见http://blog.csdn.net/mathe/archive/2007/05/08/1600057.aspx），后来发现是
传说中的Wythoff Array，（参见http://mathworld.wolfram.com/WythoffArray.html）。这个东东挺有意思的，它恰好历遍了自然数。另一方面，同志们也讨论过，在Fibonacci数列中的完全平方数只有有限个。所以第一个问题是问：是否在Wythoff Array的每一行里，平方数都只有那么几个呢（比方说不超过3个）？也就是猜测平方数是均匀分布在Wythoff Array的各行里。

第二题：
这个问题基于这样的感受：我们知道由2乘2矩阵T={{1,1},{0,1}}和S={{0,-1},{1,0}}通过矩阵乘法，可以凑出所有的矩阵行列式值为1的整数2乘2矩阵，简称为：矩阵S和T生成PSL(2,Z)，S和T称为生成元；另一方面，函数t(z)=z+1和s(z)=-1/z，通过迭代，可以得到所有的有理函数f(z)=(az+b)/(cz+d)（其中系数都是整数，且ad-bc=1）。这两个现象是相互对应的，所以怪好玩儿的，也是模形式理论的出发点之一。第二个问题针对其它的维度，是问：对于矩阵行列式值为1的
整数3乘3矩阵PSL(3,Z)，找出一组它的生成元。就是说找一些3乘3的整数矩阵，使它们通过矩阵乘法可以凑出PSL(3,Z)，而它们之间不能相互凑出。

第三题：
这个问题是一道几何题，但愿能说清楚这个问题。
平面上有一些点和一些直线，并且存在“某些点在某些直线上，某些直线上有某些点”这样的关系M。如果我们承认无穷远点是平行线的交点，也承认无穷远直线什么的。那么我们会发现，这些点和线在点光源的照射下，在另一平面的影子（假设逆着光源也有影子，简称这种变换为射影变换），也保持了关系M（当然也保持着所谓交比啥的）。第三个问题是反过来问：如果我们在保持关系M的前提下改变这些点和线的位置，在什么情况下，将存在破坏这种射影变换的可能？把这个问题换一种说法，我们已知平面上的一些点和一些直线（也就是关系M），这时可能有两种情况：一种是保持关系M的变换一定射影变换（比如说某三角形的三边和三个顶点）；另一种存在着保持关系M的变换但不是射影变换的变换（比如说一根直线和其上的四个点）。我们问对于给定的关系M，有什么简单的方法来判断它属于上面的哪种情况。

mathe

看上去都不容易。
第二个题目关于分数变换和2×2阶么模矩阵之间的联系你能给出一些更加详细的介绍吗？感觉挺有意思的。
第三题的确不大明白

无心人

问题二关键是如何找到候选
我想，要首先能确定矩阵元素的范围
这个不好做吧

zgg___

关于第一题：
大家看看有没有反例。

关于第二题：
设如果f(x)=(a*x+b)/(c*x+d)，且2乘2矩阵m={{a,b},{c,d}}，我们可以将f(x)和m对应起来。这里面有一个关系就是：如果f1(x)和m1对应，f2(x)和m2对应，那么f1(f2(x))和m1*m2对应。这个是容易验证的，所以书上或许不大强调。记得Longtimeago智星上，有一个问题是问：当a,b,c,d满足什么条件时，f(x)迭代n次后，恰好是正比例函数x？这个问题有一种做法就是求m的特征值。总之，某个分数变换（f(x)=(a*x+b)/(c*x+d)）、某个2乘2矩阵、某个一元二次方程（是左边那个矩阵的特征多项式）、某个递推关系的数列（左边的多项式是它的生成函数），都是完全对应的，甚至于可以看成相同的对象。

关于第三题：
第三个问题举一个例子说明一下。一天老师在黑板上给大家布置作业，画了三个图，如下，第一个图有1根直线4个点，第二个图有3根直线3个点，第三个图有一堆直线一堆点。同学们在作业本上抄题，点和线的包含关系是不会抄错的，但是位置总是有误差的，甚至于有的同学没有去上课，根本就没有看见图，只是通过电话知道有哪些点和线，谁在谁上面。老师批改作业时，凡是作业本上的图和黑板上的图满足射影变换的就得5分，不满足的得4分（扣卷面分，呵呵）。可以看到，第二题大家都会得5分的，而第一题就不一定了。哪么第三个图呢？如何判断哪些图一定大家都得5分呢。

mathe

第三题是不是说设计一个算法,判断一个给定的点线关系(可以用一个矩阵来描述),是否所以满足这个点线关系的图可以相互通过射影变换得到?
比如例子1,只有给定点线关系,会得到两个相互之间不能通过射影变换得到的图.
但是例子2和例子3,应该怎么画出来的结果都是可以相互通过射影变换得到的

zgg___

是的。
就是寻找一组判据。

mathe

现在感觉第三题最简单.
首先所有的点应该通过边相互连接起来(除了点的数目等于2的特殊情况)
而仅三个没有任何线连接起来的点根据你的定义算不算不是很清楚.(通常情况应该三点不共线,都是等价的,但是特殊情况可以三点共线,和不共线的情况不等价).
同样,所有的线要通过点的关系连通.

然后在所有点通过线的关系连通的情况,如果某条直线上有一个点没有其它直线通过,通常情况应该不唯一确定. (除非总的点的数目很少的特殊情况);同样,某条直线上只有一个点的情况(对偶情况)也不能唯一确定.

此外,如果我们能够从图上删除一个点,余下的点不再连通,那么通常这个图也不是唯一确定的.(可以想象其中一个连通分支绕这个点旋转一个角度得到另外一个图);同样对偶情况也不行.

第三,如果我们能够从图上删除两个点,余下的点不再连通,那么这个图也不是唯一确定的.(可以考虑仅仅将其中一个分支压扁,但是保持这两个点不动);同样对偶情况也不行.

第四,如果我们能够从图上删除三个不共线的点,余下的点不再连通,那么这个图应该也是不唯一确定的(唯一确定一个射影变换好像应该需要四个点,我们可以取其中一个连通分之中一个点,移动它的位置,而那三个点不变,可以构成这个连通分支的一个射影变换);同样对偶情况不行.

不过我觉得如果上面测试都通过了,应该是射影变换下唯一的(不过没有证明).而这个算法时间复杂度已经不小了,应该是$O(n^4)$的

shshsh_0510

关于第一题:  "同志们也讨论过，在Fibonacci数列中的完全平方数只有有限个。"  在哪讨论的？
关于第二题: PSL(3,Z)的生成元，这个感觉应该有结论吧，回头查一下。 （假如没有现成结论的话，这个应该就不是一般难的问题了）
关于第三题: 第一道作业题为什么大家做不对呢？是因为比例画不对吗？即使去上课了，比例也不好画对呀。如果只是电线关系，四点一线怎么能画错呢？ 另外，按照比例也一定的要求，第3个图应该不是符合要求的吧（两条平行的线间距离可以有一定移动的自由度）

mathe

第三题按照zgg的要求,要求图像满足射影变换下可以互变换.而对于一条直线上4个点,射影变换前后满足交比不变,所以第一个题肯定比例画不好.当然去上课的,比例也不能画好(可能相对好一些).不过上课只是zgg打个比方.

gxqcn

原帖由 shshsh_0510 于 2008-7-15 08:21 发表
关于第一题:  "同志们也讨论过，在Fibonacci数列中的完全平方数只有有限个。"  在哪讨论的？
...

在CSDN上：猜想：斐波拉切数列中完全平方数的个数只有有限个
我在其4楼进行了答复：[quote]Fibonacci 数列中为完全平方数的有且仅有5个：
    F(0)=0, F(-1)=F(1)=F(2)=1, F(12)=144

证明见：Square Fibonacci Numbers, Etc.