一类特殊多项式系统的结式矩阵毕业论文.doc

《一类特殊多项式系统的结式矩阵毕业论文.doc》由会员分享，可在线阅读，更多相关《一类特殊多项式系统的结式矩阵毕业论文.doc（39页珍藏版）》请在三一办公上搜索。

1、一类特殊多项式系统的结式矩阵The resultant matrix for a special polynomial system摘 要本文是研究一类特殊多项式系统的结式矩阵。主要证明了：从双次数矩形支集的4个角上分别切去4个矩形子支集时，-结式Dixon矩阵公式仍然成立。首先给出了一些基本的概念和3个双次数多项式的Dixon矩阵；然后把论文的主要结论以定理的形式正式给出，定理的证明分为3部分：第一部分证明了当角上切去的矩形子支集中的单项式系数为0时，相应的行与列为0；第二部分证明了去掉的零行与零列之后，剩下的矩阵为方阵且它的元素仍是Dixon系数矩阵中的元素，这样就得到的子矩阵就是；第三部

2、分证明了，且它与-结式有相同的阶数，因此就是多项式支集为的的-结式；最后通过例子验证这些结论。关键词：Dixon矩阵；多项式支集；-结式ABSTRACTThis paper studies the resultant for a special polynomial system. It prove that the Dixon matrix formulation for -resultants survives when four corner rectangular sub-supports are cut off from the bi-degree rectangular suppo

3、rt .First, it has defined some notations and terminologies and presented the Dixon resultant formulation for three bi-degree polynomials in two variables. Then it states the main result of the paper formally as a theorem. The proof of the theorem is divided into three parts. Part 1 identifies the ze

4、ro rows and columns of the Dixon coefficient matrix. Part 2 ensures that the required number of non-zero rows and columns remain in the Dixon coefficient matrix. Part 3 asserts that the determinant of is non-zero and has the right degree, thus it is the -resultant for whose monomial support is . Las

5、t, it illustrates the various results with examples.Key Words：Dixon matrix; monomial support; -resultant 目 录绪 论11预备知识31.131.2 矩阵与行列式31.3 多项式32 经典双次数Dixon结式53 Dixon -结式74 矩形切角引起的零行和零列94.1 因式分解定理94.2 矩形的右上切角问题94.3 矩形的左上切角问题114.4 矩形的左下切角问题114.5 矩形的右下切角问题125 经矩形切角后的非零子矩阵135.1括号的行支集和列支集135.2 的非零行与非零列146

6、Dixon矩阵的行列式就是-结式177 举例说明188 结 论219 参考文献22致 谢24翻译原文25中文翻译31绪 论结式方法是消去法中的一种重要工具，在代数几何、自动几何定理证明、CAD/CAM、CAGD、计算机代数、计算机视觉、机器人和虚拟现实中有着广泛而深远的应用。所谓的结式，就是一个多项式，它由原多项式系统的系数所构成，它等于零的充分必要条件是原多项式系统存在公共根。正因如此，结式方法的优异，除了它的快速消元能力之外，还在于它能判定一个多项式系统是否有解。有了这个工具，我们就可以在求解之前先判定这个多项式系统是否有解，而不会碰到经过数天的计算之后，结果无解的情况出现,所以结式对于解

7、多项式方程组也是一个很有效的工具。由于多项式的支集与结式有着密切的关系，因此研究支集的缺失情况则对结式矩阵最后的规模有着重要的意义，其中切角问题(corner-cutting)被认为是最关键的问题。在多项式的支集构成的牛顿多面体中，内部点的缺失(对应着某些单项式在多项式中的缺失)不会影响整个Dixon结式矩阵的大小和奇异性，但是会影响所对应的曲面的次数，而位于四个角的点的缺失，则会影响结式矩阵的大小、退化性等问题。在这方面，Chionh 证明了对于非混合双变元多项式系统，如果位于四个角的缺失部分为矩形，也就是所谓的rectangular corner-cutting 的情况下，Dixon结式矩

8、阵不会产生多余因子。以往，个元多项式方程组的结式是一个多项式方程，此方程组的系数满足多项式方程当且仅当此方程组在维射影空间中有解。这样一个结式可以表示为一个Macaulay商式，但是对于特殊情况有更好的方法。对于个元线性方程，阶系数矩阵的行列式是结式。对于2个一元方程，它的结式可以通过Sylvester (西尔维斯特)法或Bezout (贝祖)法求得。经典结式考虑总次数不超过一个特定值的所有单项式；而-结式考虑的是构成多项式的单项式。Dixon构造了3个二元方程的一个结式：他是通过把Cayley多项式 扩展为Dixon多项式，其中Cayley多项式考虑的是两个一元多项式，而Dixon多项式考虑

9、的是3个关于，的双次数多项式，。然而Cayley多项式的系数矩阵给出一个关于总次数构形的经典结式，Dixon多项式的系数矩阵给出关于双次数构形的-结式。事实上，可以通过从一个总次数为的多项式中去掉某些适当的单项式，而得到一个双次数为的多项式。E.W. Chionh讨论了Dixon结式矩阵中项的表达式，有了这个公式，不用计算整个Dixon矩阵，就可以知道某个位置的项是什么。在文献5中另外一种公式也可以求出Dixon结式矩阵中的项，该公式计算简单，并且可以证明Dixon结式矩阵中的一些性质。1908年A. L. Dixon综合前人的结果，对由三个双变元多项式构成的多项式系统给出了三种结式的构造方法

10、，分别是基于Sylvester与Cayley 的方法，以及两者的混合方法。由于双变元多项式系统有更实际的背景，因此对相应的Dixon结式矩阵的研究也很多。本文主要基于Cayley quotient方法，求多项式的支集为的3个双次数多项式的Dixon结式矩阵，以及在rectangular corner-cutting 的情况下，求解并讨论-结式。论文首先根据论文需要给出了一些基本的概念、术语；第2节给出了和双次数多项式的Dixon结式矩阵的定义，并且给出Dixon结式矩阵中项的表达式；第3节把论文的主要结论以定理的形式正式给出,这就是论文的核心部分(定理3.1)，这个定理共有三个结论，因此接下来

11、我们将定理的证明分为三个部分.第4节证明了Dixon系数矩阵的零行和零列，即：当从的多项式支集四个角上分别切去四个矩形子支集时，的行支集和列支集也是对应的从其支集、的四个角上切去形状相同的四个矩形子支集(在这里，从、切去的子支集与的形状完全相同，只是在位置上有一个平移)，由于对，有，因此中对应的行与列均为0；第5节证明了去掉的个零行与个零列之后(其中)，剩下的矩阵是个方阵且它的每个向量均非零；第6节证明，且的次数与-结式的次数相等，因此就是我们所要的-结式。第7节通过一个例子将定理3.1的内容进行了验证。1预备知识这节给出的一些术语和概念与第2节定义的Dixon公式密切相关。1.1集合定义1.

12、1 整数的集合记为。集合的基数记为。定义1.2 令2个集合的差为。如果，从中去掉就得到；并且记：.定义1.3 如果，则。对，到的连续的整数集记为，且若，则.定义1.4 如果，两个连续的整数集的笛卡尔积记为：，且若或，则.1.2 矩阵与行列式一个方阵的行列式为.矩阵的零行（或列）是指这个行（或列）的元素的值全为0.1.3 多项式称为关于变量双次数为的多项式，如果关于的次数分别为.即:.的多项式支集是指的单项式指数向量的集合(其中是的一个单项式)，也就是说是的一项（若）.如果一个一般的多项式关于的双次数为，那么它的多项式支集记为： (1-1)很显然，是平面上的一个矩形点列。的多项式支集的凸包称为的

13、牛顿多面体。例如：，它的多项式支集和牛顿多面体如图1-1所示。图1-1.双次数为的多项式的多项式支集与牛顿多面体对于3个一般的双次数多项式， (1-2)定义： ，称此3阶行列式为括号.在不致引起混淆的情况下，为了节省空间，简记：例如：.2 经典双次数Dixon结式在这节中，主要介绍3个二元多项式方程的经典Dixon结式的构造过程。设3个多项式 (2-1)其中为的多项式支集，显然.下面我们就给出的Dixon多项式的定义：定义2.1 (2-2)当或时的分子为0，所以分子可以被分母整除，这也就意味着是关于的一个多项式。接下来我们就主要研究的矩阵形式： (2-3)其中系数矩阵称为多项式的Dixon矩阵

14、；单项式和分别称为的行标和列标。而的计算公式由下式给出：定义2.2 行标的指数向量集记为：称之为的行支集。列标的指数向量集记为：称之为的列支集。由于 的分子 (2-4)所以中的值关于的每个系数都是线性的。在此我们将，相应地简记为，.很显然，关于的次数分别为.也就是说 ， (2-5)并且我们可以得到：，因此是一个阶的方阵。当时，行列式就是的经典Dixon结式。例如：3 Dixon -结式这节的主要内容就是介绍下面的这个定理：定理3.1 设的左下角、右下角、左上角、右上角的矩形子支集依次为： (3-1)若的多项式支集为，则有以下3个结论成立：(1).的行支集为， (3-2)列支集为. (3-3)(

15、2). (3-4)(3). 是方阵且其行列式是的-结式。其中： (3-5)且 (3-6)注：如果或，则；同理如果或，则；如果或，则；如果或，则.换句话说，定理是指如果将从其四个角上分别切去一个矩形子支集得到，那么和可以相应地从和对应角上切去相同的矩形而得到(见图3-1) 图3-1.利用的切角方法从、中对应角上切去同样的矩形。注：和，和，和分别是，的转化形式。定理的证明分为三部分见4-6节:首先要考虑多项式支集为的矩阵。因为对，有，所以第一步证明中零行与零列的个数均为(见第4节)；第二步证明去掉中的行和列零向量之后，矩阵的每个向量均非零，这样就得到的子矩阵就是 (见第5节)；最后证明，且的次数与

16、-结式的次数相等，因此就是我们所要的-结式(见第6节)。下面举例说明：由Dixon矩阵的计算公式可知：其中行标从上至下依次为，列标从左至右依次为。如果，那么. ()所以对于，将()式代入就有.去掉中的零行与零列就得到，其中行标从上至下依次为，列标从左至右依次为。下面的图示说明了，、之间的关系： 其中支集中的元素用“”表示，左下角被切去的矩形子支集中的元素用数字“1”表示。4 矩形切角引起的零行和零列在这节中，主要利用一个因式分解定理证明： 当时，, (4-1)4.1 因式分解定理从的右上角切去一个矩形子支集时，下面这个定理对于证明中的零向量是很有用的，它说明Dixon矩阵可以因式分解为一个Sy

17、lvester矩阵和类Bezout矩阵。定理4.1 双次数为的Dixon多项式可以表示为： (4-2)其中，且是一个矩阵。中指标为的值为： (4-3)而。这个定理的证明可参见。4.2 矩形的右上切角问题利用因式分解定理即可证明 。首先来介绍2个引理：引理4.1 如果从右上角切去矩形子支集，那么中指标为的个列向量均为0(其中)。证明：设，因为且(4-3)式的求和范围保证，所以从因式分解定理4.1中的(4-3)式可以得到：且.由于当且时，而，所以就有。即当且时，.因此中指标为的列向量为0.这就说明对于，中指标为的列向量为0。因此，或等价地有：引理4.2 如果从右上角切去矩形子支集，那么中指标为的个

18、行向量均为0(其中)。证明：设，其中：.由于对，有，因此.将引理4.1的结论应用到Dixon多项式就会有：当时，以为指标的列向量为0。令，则：又因为 ，所以当时中指标为的行向量均为0.因此.综合上述2个引理，就可以得到以下命题：命题4.1 如果从如果从右上角切去矩形子支集，那么 中指标为的个行向量均为0(其中)；中指标为的个列向量均为0(其中)。可以利用这个命题证明在其它三处切角问题的类似结论，也更易于说明：当且时， (4-4) 如果中的系数为0，那么：当且 (4-5)或且时， (4-6)中和的系数为0。4.3 矩形的左上切角问题在这部分主要证明 和 命题4.2 如果从如果从左上角切去矩形子支

19、集，那么 中指标为的个行向量均为0(其中)；中指标为的个列向量均为0(其中)。证明： 设，因为当且时，中的系数为0,所以根据命题4.1 有：当且 (4-7)或且 (4-8)成立时，中的系数为0。由于 (4-9)因此当(4-7)式或(4-8)式成立时就有：在中的系数为0。由(4-7)式有且；由(4-8)式有且。即当或时，中的系数为0，因此 且 .4.4 矩形的左下切角问题这部分证明 和命题4.3 如果从如果从左下角切去矩形子支集，那么 中指标为的个行向量均为0(其中)；中指标为的个列向量均为0(其中)。证明：与命题4.2的证明过程类似。设，由(4-9)式得：只需将(4-5)式和 (4-6)式中的

20、分别替换为即可得：且或且.即当或时，中的系数为0，因此 且4.5 矩形的右下切角问题最后证明 和 命题4.4 如果从如果从右下角切去矩形子支集，那么 中指标为的个行向量均为0(其中)；中指标为的个列向量均为0(其中)。证明：与上述证明过程类似。设，则有下面的等式成立：将(4-5)式和 (4-6)式中的替换为即可得：且或且.即：当或时，中的系数为0，因此 且. 5 经矩形切角后的非零子矩阵在这节中主要证明(4-1)式的集合包含关系实际上是满足下面的等式：.5.1括号的行支集和列支集称行指数向量集 为中括号的行支集；称列指数向量集为中括号的列支集；如果，则中指标为的行向量非零；类似的结果对列也同样

21、成立，即：如果，则中指标为的列向量非零。这样就有必要研究一下一个非零括号的行支集和列支集。首先通过下面的这个引理找出和：引理5.1 Dixon矩阵中括号的行、列指标由下面多项式中的项给出： .证明：设是有序数对的一个排列，Dixon多项式中系数为的项是：其中：是中的符号。因此，。因为互不相同的有序数对有6种排列，并且若中有任意两组相同的话，都会使得：，所以又由于和中有相同的单项式，进而引理得证。利用上述引理，可以得到和的表达式，即下面的命题：命题5.1 设，中括号的行、列支集分别为： (5-1)(5-2)(其中：，)证明：由引理5.1很容易得到的项： (5-3)设，则，它关于的次数最低为，最高

22、为；而，它关于的次数最低为，最高为；所以关于的次数范围就是：.同理：关于的次数范围就是：；关于的次数范围就是：；关于的次数范围就是：。从而(5-1)式和(5-2)式得证。同时，命题5.1也说明和与由点围成的三角形的面积有关。定理5.1 如果，且，则(其中).证明：因为由(5-1)式和(5-2)式得：，而；所以若和符号相同，则定理成立。5.2 的非零行与非零列前面已经证明的非零行由给出，非零列由给出。在下面的讨论中，设牛顿多面体的顶点分别为： (5-4)这些顶点是由(3-2)式限定的。定理5.2 如果，则 且 (其中：在定理3.1中给出)。证明：设,显然有个非零行和个非零列。考虑以下6个括号：与

23、之一一对应的6个三角形构成牛顿多面体的扇形三角剖分(见图5-1)图5-1. 牛顿多面体扇形三角剖分为6个三角形利用命题5.1有：又 可以看出集合构成的分割，并且构成的分割。根据前面的引理5.1有：因此注：很容易验证当中有集合为空时证明过程仍然成立，所以不失一般性，利用这种特殊的三角剖分可以找到非零的行标和列标。6 Dixon矩阵的行列式就是-结式下面的这个定理就完整了定理3.1的证明过程。定理6.1 由定理3.1的条件可知：就是的-结式。证明：前面已经证明是关于的非零子矩阵，且的阶数为.由(5-4)式可知它是牛顿多面体的面积的2倍.此外，中的每一个值都是括号的一个和，而关于的每一个系数都是线性

24、的。又由定理5.2的证明可知，每个出现的次数为，且它们出现在不同的行和列，所以是的一项，也就是说。根据-结式理论(见)，由于与-结式有相同的阶数，所以就是的-结式。注：上面的项有其几何意义：设三角形的面积为，可以验证它满足定理5.1的2个条件，因此中的一项可以表示为： 7 举例说明设多项式支集(它是通过将进行矩形切角得到的),如下图： 其中“”代表中的元素，“2”，“3”，“4”分别代表角上的子支集中的元素。注意此时。验证：由已知条件有：，并且 根据定理3.1有： 所以的行支集、列支集如下图所示： 根据定理3.1，这就说明为7阶方阵，下面就需要求出，并验证且-结式的次数也为7，就可以说明就是-

25、结式。计算，并且令中的单项式的系数为0，则有：其中行标(从上到下)依次为：；列标(从左到右)依次为：.去掉中的零行和零列，并取其行列式得：因为，所以牛顿多面体的扇形三角剖分实际上就只有2个非零区域：和(见图7-1)图 7-1. 的多项式支集和牛顿多面体的扇形三角剖分又约定，322300和230100在中出现的次数分别为5和2，同时也说明-结式的次数为7.由中的“*”标记发现：为的一项，这也就证实了上面的这个结论，同时也说明。因此就证明了就是-结式。8 结 论论文证明了：从双次数矩形支集的四个角上分别切去一个矩形子支集时，-结式的Dixon矩阵公式仍然成立。证明由3部分组成。第一部分主要证明：当

26、多项式支集的角上切去的子支集中的单项式系数为0时，相应的行与列的每个元素为0，并且中零行与零列的个数均为；第二部分证明了去掉中的行和列零向量之后，剩下的矩阵为方阵且每个向量均非零，这样就得到的子矩阵就是；第三部分证明了，且它与-结式有相同的次数，因此就是多项式支集为的3个双次数多项式的-结式。换言之，是的秩子矩阵，而且就是-结式。的行支集和列支集由的转化形式表示：， (其中是角上切去的矩形子支集)。在证明的过程中会发现，给定2个简单的条件：且.在中出现的次数为三角形的面积的2倍，也就等于。此外，牛顿多面体的一个扇形三角剖分造成行支集与列支集的一个分割。由于当这些矩形子支集中有几个甚至全部为空时

27、，这个结论仍然成立，所以这个分割对于一般情况也成立。本论文研究的是rectangular corner-cutting切角问题，我们可以在此基础上将问题扩展，进一步就corner edge cutting切角问题、6-point isosceles triangular corner cutting切角问题以及它们的混合切角问题，讨论其相应的Dixon 结式矩阵。9 参考文献1 杨路, 张景中, 侯晓荣. 非线性代数方程组与定理机器证明.上海科技教育出版社, 上海, 1996.2 吴文俊. 数学机械化. 科学出版社. 北京. 20033 Bikker, P., Uteshev, A.Y.(19

28、99).On the Bezout construction of the resultant. J. Symbolic. Compute, 28, 45-88.4 Chionh,E.W.,Zhang,M.,Goldman,R.N.(1999).The block structure of three Dixon resultants and their accompanying transformation matrices. Technical Report TR99-341. Department of Computer Science, Rice University.5 Chionh

29、,E.W.,(2001).Rectangular corner cutting and Dixon A-resultants.J.Symbolic Comput.31,651-6696 Chtcherba,A.D.,Kapur,D.(2000). Conditions for exact resultants using the Dixon formulation. In Proceedings of the 2000 International Symposium on Symbolic and Algebric Computation, pp. 62-70. Scotland.7 Chtc

30、herba, A.D., Kapur, D., (2002). A complete analysis of resultants and extraneous factors for unmixed divaricates polynomial systems using the Dixon formulation. In:RWCA02, Proceedings of the 8th Rhine Workshop on Computer Algebra, Mannheim, Germany, March 2002, pp. 136-166.8 Cox, D., Little, J., OSh

31、ea, D.(1998). Using Algebraic Geometry. New York, Springer-Verlag.9 DAndrea, C., (2002). Macaulay style formulas for the sparse resultant. Trans. Amer. Math. Soc. 354, 2579-2594.10 Emiris, I.Z., Mourrain, B. (1999).Matrices in elimination theory. J. Symbolic. Compute, 28, 3-44.11 Macaulay, F.S.(1902

32、).Some formulae in elimination. Proc. London Math.Soctland,35,3-27.12 Macaulay, F.S.(1921).Note on the resultant of a number of polynomials of the same degree. Proc. London Math.Soctland,21,14-2113 Saxena, T.,(1997).Efficient variable elimination using resultants. Ph. D. Thesis, State University of

33、New York14 Zhang, M., Goldman, R.N.(2000).Rectangular corner cutting and Sylvester A-resultants. In Proceedings of the 2000 International Symposium on Symbolic and Algebric Computation,pp.301-308.Scotland.15 D. Kapur, T. Saxena (1996): Sparsity Considerations in the Dixon Resultant Formulation. In P

34、roc. ACM Symposium on Theory of Computing, Philadelphia致 谢在本文即将成文之际，我要由衷地感谢在我毕业设计阶段，帮助和支持过我的老师和同学！首先衷心地感谢我的导师！在这十几周里，老师一直对我悉心指导，在学习和科研方面给了我大量的辅导，文中的每一步都倾注着孙老师无微不至的关怀、教导和鼓励.经过这一段时间的学习，我不仅学到了知识，掌握了研究此类问题的方法，这为我以后继续学习提供了宝贵的经验。此外，我要感谢与我一起生活和学习的各位同学，成文期间许多同学为我的论文提供了宝贵的建议。最后，衷心地感谢在百忙之中抽出时间审阅本论文的各位专家教授。翻译原

35、文2.2 One-Way Functions: DefinitionsIn this section, we present several definitions of one-way functions. The first version, hereafter referred to as a strong one-way function (or just one-way function), is the most popular one. We also present weak one-way functions, non-uniformly one-way functions,

36、 and plausible candidates for such functions.2.2.1 Strong One-Way FunctionsLoosely speaking, a one-way function is a function that is easy to compute but hard to invert. The first condition is quite clear: Saying that a function is easy to compute means that there exits a polynomial-time algorithm t

37、hat on input outputs . The second condition requires more elaboration. What we mean by saying that a function is hard to invert is that every probabilistic polynomial-time algorithm trying, on input ,to find an inverse of under may succeed only with negligible (in ) probability, where the probabilit

38、y is taken over the choices of (as discussed later).A sequence (resp., a function ) is called negligible in if for every positive polynomial and all sufficiently large s, it holds that . Further discussion follows the definition.Definition 2.2.1(Strong One-Way Functions): A function is called (stron

39、gly) one-way if the following two conditions hold:1. Easy to compute: There exists a(deterministic) polynomial-time algorithm A such that on input (i.e., ).2. Hard to invert: For every probabilistic polynomial-time algorithm ,every positive polynomial ,and all sufficiently large s, Recall that denot

40、es a random variable uniformly distributed over . Hence, the probability in the second condition is taken over all the possible internal coin tosses of , with uniform probability distribution. Note that is not require to output a specific pre-image of ; any pre-image(i.e., element in the set ) will

41、do. (Indeed, in case is 1-1, the string is the only pre-image of under ; but in general there may be other pre-images).The Auxiliary Input . In addition to an input in the range of , the inverting algorithm is also given the length of the desired output (in unary notation). The main reason for this

42、convention is to rule out the possibility that a function will be considered one-way merely because it drastically shrinks its input, and so the inverting algorithm just does not have enough time to print the desired output(i.e., the corresponding pre-image). Consider, for example, the function defi

43、ned by such that is the binary representation of the length of (i.e., ). Since , no algorithm can invert on in the time polynomial in ; yet there exists an obvious algorithm that inverts on in time polynomial in (e.g., by ). In general, the auxiliary input , provided in conjunction with the input ,

44、allows the inverting algorithm to run in time polynomial in the total length of the main input and the desired output. Note that in the special case of length-preserving functions (i.e. for all s), this auxiliary input is redundant. More generally, the auxiliary input is redundant if, given only , one can generate in time polynomial in (See Exercise 4 and Section 2.2.3.2.)Further DiscussionHardness to invert is interpreted