有关组合矩阵论中图谱与符号模式矩阵的研究
【摘要】:组合矩阵论是一个近20余年来兴起并迅速发展的一个数学分支.它用矩阵论和线性代数来证明组合定理及对组合结构进行描述和分类.同时,也把组合论的思想和论证方法用于矩阵的精细分析及揭示阵列的内在组合性质.对图谱理论和符号模式矩阵的研究是组合矩阵论的重要组成部分.图谱理论是图论研究的一个非常活跃而又重要的研究领域,它在量子化学、统计力学、计算机科学、通信网络以及信息科学中均有着广泛的应用.在图谱理论中,为了研究图的性质,人们引入了各种各样的矩阵,诸如图的邻接矩阵、关联矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵等等.这些矩阵与图的结构都有着密切的联系.图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质(例如谱半径,谱唯一性,谱展,能量等等)反映出来.符号模式矩阵的研究在经济学、生物学、化学和社会学以及理论计算机科学中具有广泛的实际应用背景.对符号模式矩阵的研究包括符号模式矩阵的幂序列性质,可解性问题,稳定性问题等.本论文主要涉及的是对符号模式矩阵的幂序列性质的研究.在图谱理论方面,本论文主要研究了图的邻接谱、无符号拉普拉斯谱(Q-谱)、距离谱.主要对图的邻接矩阵、无符号拉普拉斯矩阵(Q-矩阵)、距离矩阵的谱半径、最小根以及谱展进行研究,试图建立它们与图的结构参数之间的一些关系;在符号模式矩阵方而,我们刻画了一些特殊图类的Lewin 指数极图,刻画了一些本原非可幂符号模式矩阵的基集和达到基的上
界的极图,继邵嘉裕老师、柳柏濂、尤利华和苗正科老师等对一般的本原非可幂符号模式矩阵的基集的研究成果和研究工作以及本人在硕士论文中的一些工作,给出一些关于基的界,同时证明了在基集中有一些新的问隔(“gaps”).本论文的主要内容如下:(一)在第一章中,我们首先回顾介绍了图论研究的背景和进展;接着介绍了一些图谱理论问题的研究背景和进展;最后介绍了符号模式矩阵的一些研究背景和进展.(二)在第二章中,我们研究n阶图的邻接谱.我们先介绍了一些基本概念、记号和一些引理.接着在第二、三节,我们探讨图子式(Minor)与图的谱之间的关系,寻找图的拓扑性质与代数性质的内在联系,对禁用子图K2,3的图类和边数最多的外平面二部图图的给出了一些结构性的刻画,通过已有工具对这些图类的邻接谱半径进行研究,给出了一些比较好的上、下界,甚至刻画达到一些界的极图.在本章最后,我们讨论了直径给定的双圈图中最小根,并对达到最小根的极图给出了一些结构刻画.(三)在第三章中,我们研究n阶图的无符号拉普拉斯谱.我们在第一节中介绍了一些基本概念、记号和一些引理.在第二节中讨论一般图的Q-谱半径的界,给出了一些上、下界并刻画了达到下界的极图.我们接着在第三、四节中讨论一些特殊图类的Q-谱半径的界,刻画了色数给定的图和θ-图类中达到Q-谱半径的上、界的极图.最后我们在第五节中考虑图的Q-谱的第二大根q2.刻画了q2=2的图;对n≥9阶连通非二部图,刻画了q2≤3的图;对n≥7阶连通二部图,刻画了q2≤3的图.我们证明了(i)如果n≥2,不存在n阶图G使得q2(G)∈((1,2)∪(3+(?)/2,2.7));(ii)如果n≥9,不存在n阶图G使得并q2(G)∈((1,3+(?)/2)
∪(3+(?)/2,2.7)),确定了3是q2的最小极限点.(四)在第四章中,我们研究n阶图的距离谱.在第一节中我们给出了几个增大或减小距离谱半径的移接变形定理,利用这些移接变形定理,对具有给定悬挂点数k的n阶简单连通图类,证明了具有最小距离谱半径的图是在一个n-k阶完全图的一点接k条悬挂边得到的图,具有最大距离谱半径的图是一个哑铃图.第二节中我们也给出了几个增大或减小距离谱半径的移接变形定理,利用这些移接变形定理,我们证明了Sn’(通过在星Sn的两个悬挂点之间加一条边得到)在所有的n阶单圈图中具有最小的距离谱半径;而Pn’(通过在K3的一点接一条悬挂路Pn-3得到)在所有的n阶单圈图中具有最大的距离谱半径.在本章最后,我们对般图的距离谱半径给出了较好的上、下界并刻画了达到该上、下界的极图;研究了一般图的距离谱展(即距离矩阵的谱半径与最小特征值之差)的下界,证明了完全图Kn是n阶图中达到距离谱展下界的唯一极图,完全二部图K[n/2][n/2]是n阶二部图中达到距离谱展下界的唯一极图.(五)在第五章中,我们研究n阶符号模式矩阵的幂序列性质.我们在第一节中介绍了一些基本概念、记号和一些引理;在第二节中刻画了围长为2或3达到Lewin指数上界的极图;在第三节中刻画了恰好具有d个非零对角元的本原非可幂符号模式矩阵的基集和达到基集上界的弧最少的极图;在第四节中刻画了对角元全为零的零对称本原非可幂符号模式矩阵的基集和达到基集上界的极图;在第五节中我们继续考虑一般本原非可幂符号模式矩阵的基集,给出一些关于基的界,同时证明了在基集中有一些新的”gaps”,而且刻画了一些给定基对应的符号模式矩阵.
【关键词】:邻接矩阵无符号拉普拉斯矩阵距离矩阵邻接谱半径无符号拉普拉斯谱半径距离谱半径距离谱展禁用子图最小根符号模式矩阵Lewin指数本原非可幂基极图单圈图双圈图色数无符号拉普拉斯谱第二大根极限点零对称
【学位授予单位】:华东师范大学
【学位级别】:博士
【学位授予年份】:2011
【分类号】:O157.5
【目录】:摘要6-9Abstract9-15第一章绪论15-30§1.1图论研究背景与进展15-16§1.2图谱理论的研究背景与进展16-22§1.3符号模式矩阵的研究背景与进展22-30第二章图的邻接谱30-65§2.1基本概念与常用工具30-37§2.2K_(2,3)-minorfree图的邻接谱半径的界37-45§2.3边数最多的外平面二部图的邻接谱半径45-53§2.4直径给定的双圈图的邻接谱最小根53-65第三章图的Q-谱65-98§3.1基本概念与常用工具65-68§3.2Q-谱半径的界68-72§3.3色数给定的图的Q-谱半径72-83§3.4几个关于Q-谱半径的移接变形及其应用83-88§3.5图的Q-谱的第二大根88-98第四章图的距离谱98-120§4.1给定悬挂点数的图的距离谱半径98-106§4.2单圈图的距离谱半径106-113§4.3图的距离谱半径和谱展的界113-120第五章符号模式矩阵的幂序列性质
120-169§5.1基本概念与常用工具120-126§5.2围长为2或3达到Lewin指数上界的极图126-134§5.3恰有d个非零对角元的本原非可幂符号模式矩阵的基134-147§5.4对角元全为零的零对称本原非可幂符号模式矩阵的基147-163§5.5本原非可幂符号模式矩阵的基集中的”gaps”163-169参考文献169-187攻读博士学位期间发表及完成的论文187-189致谢189 本论文购买请联系页眉网站。
2012矩阵论复习题 1. 设+=R V 是正实数集,对于任意的V y x ∈,,定义x 与y 的和为 y x y x ?=⊕ 对于任意的数R k ∈,定义k 与x 的数乘为 k x x k =? 问:对于上述定义加法和数乘运算的集合V ,是否构成线性空间,并说明理由. 2.对任意的2,R y x ∈,),(21x x x =,),(21y y y =定义x 与y 的和为 ),(112211y x y x y x y x +++=⊕ 对于任意的数R k ∈,定义k 与x 的数乘为 )2 )1(,(2121x k k kx kx x k -+=? 问:对于上述定义加法和数乘运算的集合2R ,是否构成线性空间,并说明理由. 3.设},022|),,{(321321R x x x x x x x S i ∈=++=,试证明S 是3R 的子空间,并求S 的一组基和S dim . 4.设)(R P n 表示次数不超过n 的全体多项式构成的线性空间, )}()(,0)0(|)({R P x f f x f S n ∈='= 证明S 是)(R P n 的子空间,并写出S 的一组基和计算S dim . 5. 设T 是2R 上的线性变换,对于基向量i 和j 有 j i i T +=)( j i j T -=2)( 1)确定T 在基},{j i 下的矩阵; 2)若j i e -=1 j i e +=32,确定T 在基},{21e e 下的矩阵. 6. 设T 是3R 上的线性变换,对于基},,{k j i 有 k j k j i T -=++)( i k j T =+)( k j i k T 532)(++=
第 1 页 共 6 页 (A 卷) 学院 系 专业班级 姓名 学号 (密封线外不要写姓名、学号、班级、密封线内不准答题,违者按零分计) …………………………………………密…………………………封……………………………………线………………………………… 考试方式:闭卷 太原理工大学 矩阵分析 试卷(A ) 适用专业:2016级硕士研究生 考试日期:2017.1.09 时间:120 分钟 共 8页 一、填空选择题(每小题3分,共30分) 1-5题为填空题: 1. 已知??? ? ? ??--=304021101A ,则1||||A =。 2. 设线性变换1T ,2T 在基n ααα ,,21下的矩阵分别为A ,B ,则线性变换212T T +在基n ααα ,,21下的矩阵为_____________. 3.在3R 中,基T )2,1,3(1--=α,T )1,1,1(2-=α,T )1,3,2(3-=α到基T )1,1,1(1=β, T )3,2,1(2=β,T )1,0,2(3=β的过度矩阵为A = 4. 设矩阵??? ? ? ??--=304021101A ,则 5432333A A A A A -++-= . 5.??? ? ? ? ?-=λλλλλ0010 01)(2A 的Smith 标准形为 6-10题为单项选择题: 6.设A 是正规矩阵,则下列说法不正确的是 ( ). (A) A 一定可以对角化; (B )?=H A A A 的特征值全为实数; (C) 若E AA H =,则 1=A ; (D )?-=H A A A 的特征值全为零或纯虚数。 7.设矩阵A 的谱半径1)( 南京航空航天大学2012级硕士研究生 二、(20分)设三阶矩阵,,. ????? ??--=201034011A ????? ??=300130013B ???? ? ??=3003003a a C (1) 求的行列式因子、不变因子、初等因子及Jordan 标准形; A (2) 利用矩阵的知识,判断矩阵和是否相似,并说明理由. λB C 解答: (1)的行列式因子为;…(3分)A 2121)1)(2()(,1)()(--===λλλλλD D D 不变因子为; …………………(3分)2121)1)(2()(,1)()(--===λλλλλd d d 初等因子为;……………………(2分) 2)1(,2--λλJordan 标准形为. ……………………(2分) 200011001J ?? ?= ? ??? (2) 不相似,理由是2阶行列式因子不同; …………………(5分) 0,a = 相似,理由是各阶行列式因子相同. …………………(5分) 0,a ≠共 6 页 第 4 页 三、(20分)已知线性方程组不相容. ?? ???=+=+++=++1,12,1434321421x x x x x x x x x (1) 求系数矩阵的满秩分解; A (2) 求广义逆矩阵; +A (3) 求该线性方程组的极小最小二乘解. 解答:(1) 矩阵,的满秩分解为 ???? ? ??=110021111011A A . …………………(5分)10110111001101A ??????=?????????? (2) . ……………………(10分)51-451-41-52715033A +?? ? ?= ? ??? (3) 方程组的极小最小二乘解为. …………(5分)2214156x ?? ? ?= ? ??? 共 6 页 第 5 页 武汉理工大学研究生考试试题(2010) 课程 矩阵论 (共6题,答题时不必抄题,标明题目序号) 一,填空题(15分) 1、已知矩阵A 的初级因子为223 ,(1),,(1)λλ-λλ-,则其最小多项式为 2、设线性变换T 在基123,,εεε的矩阵为A ,由基123,,εεε到基123,,ααα的过渡矩阵为P ,向量β在基123,,εεε下的坐标为x ,则像()T β在基123,,ααα下的坐标 3、已知矩阵123411102101,,,00113311A A A A -????????==== ? ? ? ?--???????? ,则由这四个矩阵所生成的子空间的维数为 4、已知0100001000011 000A ?? ? ?= ? ???,则1068A A A -+= 5、已知向量(1,2,0,)T i α=--,21i =-,则其范数 1α= ;2α= ;∞α= ; 二,(20)设1112112121220a a V A a a a a ??????==-=?? ?????? ?为22?R 的子集合, 1、证明:V 是22?R 的线性子空间; 2、求V 的维数与一组基; 3、对于任意的1112111221222122,a a b b A B a a b b ????== ? ????? V ∈,定义 2222212112121111234),(b a b a b a b a B A +++= 证明:),(B A 是V 的一个内积; 4、求V 在上面所定义的内积下的一组标准正交基。 三、(15分)设{} 23210[](),0,1,2i F t f t a t a t a a R i ==++∈=为所有次数小于3的实系数 多项式所成的线性空间,对于任意的22103()[]f t a t a t a F t =++∈,定义: 习题二 1.化下列矩阵为Smith 标准型: (1)222211λλλλ λλλλλ?? -?? -????+-?? ; (2)2222 00 000 00(1)00000λλλλλλ ?? ?? -? ? ??-?? -?? ; (3)2222 232321234353234421λλλλλλλλλλλλλλ?? +--+-??+--+-????+---?? ; (4)23014360220620101003312200λλλλλλλλλλλλλλ????++??????--????---?? . 解:(1)对矩阵作初等变换 23221311(1)100 10 000000(1)00(1)c c c c c c r λλλλλλλλλ+--?-???????????→-???→? ??? ????-++???? , 则该矩阵为Smith 标准型为 ???? ? ?????+)1(1λλλ; (2)矩阵的各阶行列式因子为 44224321()(1),()(1),()(1),()1D D D D λλλλλλλλλλ=-=-=-=, 从而不变因子为 22 2341234123()()() ()1,()(1),()(1),()(1)()()() D D D d d d d D D D λλλλλλλλλλλλλλλλ== =-==-==-故该矩阵的Smith 标准型为 2210000(1)0000(1)00 00(1)λλλλλλ?? ??-????-?? -??; (3)对矩阵作初等变换 故该矩阵的Smith 标准型为 ?? ?? ??????+--)1()1(112 λλλ; (4)对矩阵作初等变换 在最后的形式中,可求得行列式因子 3254321()(1),()(1),()()()1D D D D D λλλλλλλλλ=-=-===, 于是不变因子为 2541234534()() ()()()1,()(1),()(1)()() D D d d d d d D D λλλλλλλλλλλλλ==== =-==-故该矩阵的Smith 标准形为 2 1 0000 010 0000100000(1)00 00 0(1)λλλλ?????????? -?? ??-?? . 2.求下列λ-矩阵的不变因子: (1) 21 0021002λλλ--????--????-??; (2)100 1000 λαββλα λαββ λα+????-+? ???+??-+?? ; 习题三 1.证明下列问题: (1)若矩阵序列{}m A 收敛于A ,则{}T m A 收敛于T A ,{} m A 收敛于A ; (2)若方阵级数∑∞ =0m m m A c 收敛,则∑∑∞ =∞==?? ? ??00)(m m T m T m m m A c A c . 证明:(1)设矩阵 ,,2,1,)() ( ==?m a A n n m ij m 则 ,)()(n n m ji T m a A ?=,)()(n n m ij m a A ?=,,2,1 =m 设 ,)(n n ij a A ?= 则 n n ji T a A ?=)(,,)(n n ij a A ?= 若矩阵序列{}m A 收敛于A ,即对任意的n j i ,,2,1, =,有 ij m ij m a a =∞ →) (lim , 则 ji m ji m a a =∞ →)(lim ,ij m ij m a a =∞ →)(lim ,n j i ,,2,1, =, 故{} T m A 收敛于T A ,{} m A 收敛于A . (2)设方阵级数 ∑∞ =0 m m m A c 的部分和序列为 ,,,,21m S S S , 其中m m m A c A c c S +++= 10. 若 ∑∞ =0 m m m A c 收敛,设其和为S ,即 S A c m m m =∑∞ =0 ,或S S m m =∞ →lim , 则 T T m m S S =∞ →lim . 而级数∑∞ =0 )(m m T m A c 的部分和即为T m S ,故级数∑∞ =0 )(m m T m A c 收敛,且其和为T S , 即 ∑∑∞ =∞==?? ? ??00)(m m T m T m m m A c A c . 2.已知方阵序列{}m A 收敛于A ,且{} 1-m A ,1 -A 都存在,证明: (1)A A m m =∞ →lim ;(2){}1 1 lim --∞ →=A A m m . 证明:设矩阵 ,,2,1,)() ( ==?m a A n n m ij m ,)(n n ij a A ?= 若矩阵序列{}m A 收敛于A ,即对任意的n j i ,,2,1, =,有 ij m ij m a a =∞ →) (lim . (1) 由于对任意的n j j j ,,,21 ,有 ,lim ) (k k kj m kj m a a =∞ → n k ,,2,1 =, 故 ∑-∞ →n n n j j j m nj m j m j j j j m a a a 2121)()(2)(1) ()1(lim τ = ∑-n n n j j j nj j j j j j a a a 21212121) ()1(τ , 而 ∑-= n n n j j j m nj m j m j j j j m a a a A 2121) ()(2)(1)()1(τ, 华北电力大学硕士研究生课程考试试题(A 卷) 2013~2014学年第一学期 课程编号:50920021 课程名称:矩阵论 年 级:2013 开课单位:数理系 命题教师: 考核方式:闭卷 考试时间:120分钟 试卷页数: 2页 特别注意:所有答案必须写在答题册上,答在试题纸上一律无效 一、判断题(每小题2分,共10分) 1. 方阵 A 的任意一个特征值的代数重数不大于它的几何重数。 见书52页,代数重数指特征多项式中特征值的重数,几何重数指不变子空间的维数,前者加起来为n ,后者小于等于n 2. 设12,,,m αααL 是线性无关的向量,则12dim(span{,,,})m m ααα=L . 正确,线性无关的向量张成一组基 3.如果12,V V 是V 的线性子空间,则12V V ?也是V 的线性子空间. 错误,按照线性子空间的定义进行验证。 4. n 阶λ-矩阵()A λ是可逆的充分必要条件是 ()A λ的秩是n . 见书60页,需要要求矩阵的行列式是一个非零的数 5. n 阶实矩阵A 是单纯矩阵的充分且必要条件是A 的最小多项式没有重根. 二、填空题(每小题3分,共27分) (6)210021,003A ?? ?= ? ???则A e 的Jordan 标准型为223e 1 00e 0 ,00 e ?? ? ? ?? ?。 首先写出A e 然后对于若当标准型要求非对角元部分为1. (7)301002030λλλ-?? ?+ ? ?-??的Smith 标准型为10003000(3)(2)λλλ?? ?- ? ?-+?? 见书61-63页,将矩阵做变换即得 矩阵理论试卷(A )(2008级) (共1页) 成绩 学院班级__ _; 姓名___ __; 学号_ __ __ 1 (15分)给定 2222{()|}ij ij R A a a R ??==∈(数域R 上二阶实方阵按通常矩阵的加法与数乘构成的线性空间)的子集 221122i j {()|0, } i j V A a a a a R ?==+=∈ (1)证明V 是22R ?的子空间;(2)求V 的维数和一组基;(3)求3253A ??= ?-?? 在所求基下的坐标。 2 (15分)设α为n 维欧氏空间V 中的单位向量,对V 中任意一向量x , 定义线性变换: ()2(,)T T x x x αα=-, (1)证明:T 为正交变换; (2)证明 T 对应特征值1有n-1 个线性无关的特征向量;(3)问T 能否在某组基下的矩阵为对角阵,说明理由。 3 (15分)设矩阵010120110A ?? ?=- ? ?-?? (1)求A 的若当标准形;(2)求A 的最小多项式;(3)计算532()45g A A A A E =+-+。 4(10分)设3 R 中的线性变换T 如下:123122323(,,)(2,,) ; ()i T x x x x x x x x x x R =--+∈ (1) 写出T 在基T T T 123 =(1, 1, 0),=(0, 1, 1), =(0, 0, 1)βββ下的矩阵;(2) 求3()T R 及()Ker T 。 5 (10分)已知多项式矩阵 2210007(2)00()00(1)00 00(1)(5)A λλλλλλλ-?? ?++ ?= ?- ?++??,求()A λ的初等因子及史密斯标准形。 6(10分)在欧氏空间4R 中, 对任意两个向量12341234(,,,) , (,,,),T T a a a a b b b b αβ==定义内积 1122334(, )2a b a b a b a b αβ=+++ 求齐次方程组1234123 20 = 0x x x x x x x +-+=??+-? 的解空间的一组标准正交基。 7 (10分)(1) 设A 为可逆矩阵, 证明对任何矩阵的算子范数, 都有11||||||||--≥A A 。 (2)设???? ? ??--+-=21512363 11684i i A , 利用(1)的结论分别估计11||||-A 和∞-||||1A 的下界。 8(15分)已知200111113?? ?= ? ?-?? A , 求矩阵函数()e t f =A A 。 中国矿业大学 级硕士研究生课程考试试卷 考试科目矩阵论 考试时间年月 研究生姓名 所在院系 学号 任课教师 一(15分)计算 (1) 已知A 可逆,求 10 d At e t ? (用矩阵A 或其逆矩阵表示) ; (2)设1234(,,,)T a a a a =α是给定的常向量,42)(?=ij x X 是矩阵变量,求T d()d X αX ; (3)设3阶方阵A 的特征多项式为2(6)I A λλλ-=-,且A 可对角化,求k k A A ??? ? ??∞→)(lim ρ。 二(15分)设微分方程组 d d (0)x Ax t x x ?=???? ?=?,508316203A ?? ?= ? ?--??,0111x ?? ? = ? ??? (1)求A 的最小多项式)(λA m ; (3)求At e ; (3)求该方程组的解。 三(15分)对下面矛盾方程组b Ax = 312312 111x x x x x x =?? ++=??+=? (1)求A 的满秩分解FG A =; (2)由满秩分解计算+A ; (3)求该方程组的最小2-范数最小二乘解LS x 。 四(10分)设 11 13A ?=?? 求矩阵A 的QR 分解(要求R 的对角元全为正数,方法不限)。 五(10分) 设(0,,2)T n A R n αβαβ=≠∈≥ (1)证明A 的最小多项式是2 ()tr()m A λλλ=-; (2)求A 的Jordan 形(需要讨论)。 六(10分)设m n r A R ?∈, (1)证明rank()n I A A n r + -=-; (2)0Ax =的通解是(),n n x I A A y y R +=-?∈。 七(10分)证明矩阵 21212123 111222222243333 33644421(1)(1)n n n n n n n n n n ---? ? ? ? ? ? ?= ? ? ? ? ? ?+++? ? A (1)能与对角矩阵相似;(2)特征值全为实数。 2017—2018学年第一学期《矩阵论》试卷 (17级专业硕士) 专业 学号 姓名 得分 一.判断题(每小题3分,共15分) 1.线性空间V 上的线性变换A 是可逆的当且仅当零的原像是零, 即ker A =0。( ) 2.实数域上的全体n 阶可逆矩阵按通常的加法与数乘构成一个 线性空间。( ) 3.设A 是n 阶方阵,则k A ),2,1( =k 当∞→k 时收敛的充分 必要条件是A 的谱半径1)( 4. 设1][-n x P 是数域K 上次数不超过1-n 的多项式空间,求导算子D 在基12,,,,1-n x x x 以及基12)! 1(1,,!21, ,1--n x n x x 下的矩阵分别为 , 。 5.设A 是复数域上的正规矩阵,则A 满足: ,并 写出常用的三类正规矩阵 。 三.计算题(每小题12分,共48分) 1.在3R 中,试用镜像变换(Householder 变换)将向量T )2,2,1(-=α 变为与T e )1,0,0(3=同方向的向量,写出变换矩阵。 。南航矩阵论2013研究生试卷及答案
矩阵论武汉理工大学研究生考试试题科学硕士
研究生矩阵论课后习题答案(全)习题二
研究生矩阵论课后习题答案全习题三
硕士研究生课程考试试题矩阵论答案
研究生2008矩阵理论试卷
研究生矩阵论试题与答案
矩阵论试题
2016矩阵论试题A20170109 (1)