（计算数学专业论文）双随机矩阵和双随机循环矩阵的素元研究.pdf

摘要 众所周知，在矩阵理论和矩阵计算中，矩阵的分解问题是非 常重要的问题当我们有了一个( 类) 矩阵的某种分解，我们对这 个( 类) 矩阵肯定会有更多的了解，更有利于我们的分析和计算 另一方面，矩阵的分解在实际中也有重要的应用例如，非负矩 阵的分解在信号处理、组合优化、复杂性理论、概率论和人口统计 学及经济学等中有重要的应用 本文研究的是非负矩阵中的素元这一方面是为研究非负矩 阵分解的需要；另一方面，在实际中也有重要的应用例如，在系 统与控制论中的有限值过程的随机实现问题、隐藏m a r k o v 模型的 实现问题、一个有限随机系统的实现问题和一个正线性系统( 投 入、状态和产出都取正值) 的实现问题等等( 上述实现问题中的主 要问题是刻划系统的极小性，最后可把问题归结为正线性代数中 的一类问题，即非负矩阵中素元的分类问题) 本文主要研究了双随机矩阵和双随机循环矩阵中的素元因 为任一n 阶双随机循环矩阵都可以唯一地表示为移位的n 一1 次一 元多项式和任一佗阶双随机矩阵都可以表示为置换矩阵的凸和， 从而可把双随机循环矩阵中素元的分类问题简化为解双随机循环 矩阵上的一个方程的问题，把双随机矩阵中素元的分类问题简化 为解双随机拉丁方上的一个方程的问题 本文第一章，我们将简单介绍研究非负矩阵中素元的理论和 实际意义和素矩阵的研究现状同时也将给出与本论文有关的几 类非负矩阵和几类半环中素元的定义和关系，以及有关的h u r w i t z 多项式的一些结果 第二章，主要研究了判别对应向量的正元素全部相邻的双随 机循环矩阵是否为素元的方法，研究了p i c c ig 等在文 4 7 】中所提 出的如下问题和猜想： 问题a 设a = c i r c ( a ) d s c 军+ x n , 4 n ( a ) n ，且 口= 嵋k ( a a ，a n ( 口) ，0 ，o ) 碑，k 一1 ( 即a 的正元素相邻) ，给出 判别a 是否是双随机循环矩阵中素元的方法 猜想a 设n 4 ，n 6 ，a = c i r c ( a ) d s 僻加，礼( 口) = n 一1 ，则 a 不是双随机循环矩阵中的一个素元 我们解决了问题a 和猜想a 当佗( 口) = 5 时的情形，也给出猜 想a 成立的一个充分条件 第三章，研究了判别对应向量的正元素不全相邻的双随机循 环矩阵是否为素元的方法，完全解决了如何判别有位数3 或4 且对 应向量的正元素不全相邻的双随机循环矩阵是否为素元的问题 第四章，研究了双随机矩阵中素元的判别方法，解决了p i c c i g 等在文 4 7 中所提出的如下问题： n ! 问题b设a d 霹加( n 3 ) 能唯一表示成a = a i p i ，a = ( a l j ，o 州) t 掣，n ( a ) = 3 则a 是双随机矩阵中的素元当且仅当 不存在向量b ，c 母，几( 6 ) ，死( c ) 2 ，使 a = l m ( 6 ) c 成立，其中k ：卑2 一剧黼2 是由置换乘法诱导出的拉丁方( 见后 面定义4 2 3 ) 而存在向量6 ，c 掣，礼( 6 ) ，礼( c ) 2 ，使上式成立当且 仅当下述下标方程和双随机拉丁方上的方程都有解： i ( 口) = ui ( l m ( 6 ) 巧) ， j e i ( e ) a t = l ，( 6 ) c r 其中a r = oi i ( 。) 肆，凡( o ，) = 3 ，岛= ci i ( 。) s “，n ( 白) = n ( c ) ，l ，( 6 ) = l m ( 6 ) k ) i ( 。) 上述下标方程的可解性条件已在文【4 7 】中刻划出，这里的问 题是：如何刻划上述双随机拉丁方上方程的可解性条件? 关键词：非负矩阵；双随机矩阵；双随机循环矩阵；素矩阵；非 负矩阵分解 i i a b s t r a c t t h ep r o b l e mo fm a t r i xf a c t o r i z a t i o n sa r ev e r yi m p o r t a n ti nm a t r i x t h e o r ya n dm a t r i xc o m p u t a t i o n s i fw ek n o wak i n dd e c o m p o s i t i o no fa m a t r i x ，t h e nw ew i l lk n o wm o r ea b o u tt h em a t r i x i ti s b e n e f i c i a lt oo u r a n a l y s e sa n dc o m p u t a t i o n s o nt h eo t h e rh a n d ，m a t r i xf a c t o r i z a t i o n sa r e u s e f u l li nr e a l i t y f o re x a m p l e ，f a c t o r i z a t i o n so ft h en o n n e g a t i v em a t r i c e sa r e i n t e r e s tt os i g n a lp r o c e s s i n g ，c o m b i n a t o r i a lo p t i m i z a t i o n ，c o m p l e x t yt h e o r y , p r o b a b i l i t y , d e m o g r a p h ya n de c o n o m i c se t c i nt h i sp a p e r ，p r i m e si nt h en o n n e g a t i v em a t r i c e sa r ee x p l o r e d o n o n eh a n d ，i ta r i s e si nd e c o m p o s i t i o n si nt h en o n e g a t i v em a t r i c e s ，o nt h e o t h e rh a n d ，i ti su s e f u l li nr e a l i t y f o re x a m p l e ，t h es t o c h a s t i cr e a l i z a t i o n p r o b l e mf o rf i n i t e - v a l u e dp r o c e s s ，t h er e a l i z a t i o np r o b l e mf o rt h eh i d d e n m o r k o vm o d e l ，t h er e a l i z a t i o np r o b l e mf o raf i n i t es t o c h a s t i cs y s t e m ，a n d t h er e a l i z a t i o np r o b l e mf o rap o s i t i v el i n e a rs y s t e m ( i nw h i c hi n p u t s ，s t a t e s ， a n do u t p u t st a k ep o s i t i v ev a l u e s ) e t c i nc o n t r o la n ds y s t e mt h e o r y ( t h e m a i nq u e s t i o nf o rt h e s er e a l i z a t i o np r o b l e m si st h ec h a r a c t e r i z a t i o no fm i n - i m a l i t yf o rt h e s es y s t e m s t h eq u e s t i o nr e d u c e st oap r o b l e mo fp o s i t i v e l i n e a ra l g e b r a ，i e ，t h ec l a s s i f i c a t i o np r o b l e mo fp r i m e si nt h en o n n e g a t i v e m a t r i c e s ) i nt h i sp a p e rw em a i n l yi n v e s t i g a t ep r i m e si nt h ed o u b l ys t o c h a s t i c m a t r i c e s a n di nt h ed o u b l ys t o c h a s t i cc i r c u l a n t s s i n c ea n y 佗nd o u b l y s t o c h a s t i cc i r c u l a n tm a t r i xh a sau n i q u er e p r e s e n t a t i o na sap o l y n o m i a lo f d e g r e en - 1 i nan 凡s h i f to p e r a t o r ，a n da n yn 佗d o u b l ys t o c h a s t i cm a t r i x h a sar e p r e s e n t a t i o na sac o n v e xs u mo fp e r m u t a t i o n s ，t h ee l a s s i f i c a t i o n p r o b l e mo fp r i m e si nt h ed o u b l ys t o c h a s t i cc i r c u l a n t sc a nb er e d u c e dt ot h e s o l u t i o no fa ne q u a t i o no v e rad o u b l ys t o c h a s t i cc i r c u l a n tm a t r i x ，a n dt h e c l a s s i f i c a t i o np r o b l e mo fp r i m e si nt h ed o u b l ys t o c h a s t i cm a t r i c e sc a nb e r e d u c e dt os o l v a b i l i t yo fa ne q u a t i o no v e rad o u b l ys t o c h a s t i cl a t i ns q u a r e i nc h a p t e r1 ，w eg i v eab r i e fi n t r o d u c t i o nt ot h ei m p o r t a n c eo fi n v e s - i i i t i g a t i n gp r i m e si nt h en o n n e g a t i v em a t r i c e si nb o t ht h e o r ya n dp r a c t i c e ， a n dt ot h ec u r r e n tr e s e a r c hs i t u a t i o no np r i m e s m o r e o v e r ，s o m ed e f i n i t i o n s a n dt h e i rr e l a t i no np r i m e si ns e v e r a lc l a s s e so ft h en o n n e g a t i v em a t r i c e s a n di ns e v e r a lc l a s s e so ft h es e m i r i n g sw h i c hr e l a t et ot h i sp a p e ra r eg i v e n a tf i n a l ，s o m er e s u l t so nh u r w i t zp o l y n o m i a l sw h i c ha l eo fi n t e r e s tt ot h i s p a p e ra r eg i v e n i nc h a p t e r2 ，w em a i n l yi n v e s t i g a t et h em e t h o d so nh o wt od i s t i n g u i s h w h e t h e ram a t r i xw h o s e c o r r e s p o n d i n gv e c t o ri so fc o n s e c u t i v ep o s i t i v ec o i n - p o n e n t si sap r i m ei nt h ed o u b l ys t o c h a s t i cc i r c u l a n t s ，a n dap r o b l e ma n d ac o n j e c t u r ew h i c hw e r ep o s e db yg p i c c ie t c i n 【4 7 】，t h a ti s p r o b l e mal e ta = c i r c ( a ) d s 四n x n ，4 n ( a ) 0 ，i l ，2 ，n ) 定义1 2 1 4r 中两多项式对夕( 入) ，九( 入) 称为组成正多项式对，系 指下述二者之一： 1 若m = d e g 【夕( a ) 】= d e g h ( a ) ，q t ，屈系夕( a ) 与h ( a ) 之根，它们均负 实数且有 胁 o r l 尾 q 2 风 a m 0 2 若m = d e 夕函( a ) 】= 如9 限( a ) + 1 ，此时9 ( 入) 与 ( 入) 之根啦，屈均负 实数且有 q l 岛 口2 风 0 ，l 0 ，3 0 ， 2 a o 0 ，n 2 0 ，a 2 0 ，a 4 0 ， 3 a o 0 ，口1 0 ，q 3 0 ，a m 0 ，a 3 0 ， 4 a o 0 ，a l 0 ，a 3 0 ，2 0 ，a 4 0 ， 定理1 2 1 7 1 6 3 设，( 入) = 0 n + 一1 a n 一1 + + 口l 入+ 咖吲刈， 则： 1 若吼有 ( a ) 吼 0 ，i = 0 ，1 ，n ， ( b ) o i + l i z i 3 吼+ 2 啦一l ，i = 1 ，2 ，n 一2 ，贝9 ，( 入) 是h u r w i t z 多项 式 2 若，( 入) 是h u r w i t z 多项式，则 ( a ) 毗 0 ，i = 0 ，1 ，n ， ( b ) 啦+ 1 啦 啦+ 2 啦一l ，i = 1 ，2 ，n 一2 1 3 素矩阵的研究现状及本文的结构 双随机矩阵和双随机循环矩阵的素元研究 6 7 0 年代，b e r m a na 和p l e m m l o n sr j 等利用非负矩阵的关联矩阵 ( 即把非零元换为非1 ，零元不变) 研究了非负矩阵中的素元，得到如 下充分条件： 定理1 3 1 设a 磁跏，五是a 的关联矩阵如果对于某些i ，k 磊，i k ，有a 村五幽则a 是可分解矩阵( 即a 不是素矩阵也不是单 项式矩阵) 定理1 3 2 设a 殿黼，n 2 如果a 是完全不可分矩阵，且对于 所有i ，七磊，i k ，有( a “) r i i 七1 ，9 1 0a 是素矩阵 及如下一个值得注意的结果： 定理1 3 3设a 毋加，n 2 则a 是碎”中的素矩阵当且仅 当存在一个完全不可分素矩阵b 皿( r 2 ) ，一个非奇异对角矩阵 d r 擘1 ”，和n 阶置换矩阵p , q ，使得p a q = bod ( 矩阵b 和d 的直和) 1 9 9 8 年，p i c c ig 等推广了定理1 3 3 ，得到如下定理： 定理1 3 3 ， 设a 兄n ，扎 2 则a 是雕”中的素矩阵当且 仅当存在一个完全不可分双随机素矩阵b r v 7 ( r 2 ) ，单位矩阵 i 兄粤_ r ( ”，和几阶单项式矩阵尸q ，使得p a q = j e 7o ，即a 单项式等价于b o ， 定理1 3 3 7 把非负矩阵中素元的分类问题归结为非负矩阵中完全不 可分双随机素元的分类问题，相关研究见 1 】 5 4 7 【5 3 5 7 】等因为非负 矩阵中的双随机素元也是双随机矩阵中的素元，因此，可把注意力集中 到研究双随机矩阵中的素元，见 4 7 】等 8 0 年代，陈继承等研究了非负矩阵的非负秩分解，提出了平凡和非 平凡秩分解的概念： 双随机矩阵和双随机循环矩阵的素元研究 7 定义1 3 4 设a 册n 有秩且a = b c 如果存在某个单项式矩 阵，使得b = a 蚜1 ，c = ，且 a ( 警) ， 则称b c 是a 的一个平凡秩分解否则称b c 是a 的一个非平凡秩分 解 并指出a 砰n 是一个素矩阵与a 只有平凡非负秩分解是等价 的得到定理1 3 1 3 的如下推广： 定理1 3 5 设a 殿x nn 2 ，五是a 的关联矩阵如果对于某些 i ，k 磊，i k ，有五“五幽则a 有非平凡非负秩分解 定理1 3 6 设a ，m 黼，n 2 如果a 是完全不可分矩阵，且对于 所有i ，k 磊，i k ，有( a “) r a 础1 ，则a 只有平凡非负秩分解 定理1 3 7 设a 殿黼则a 只有平凡非负秩分解当且仅当存在数 r 磊，一个完全不可分且只有平凡非负秩分解的矩阵b r 9 - n + r ) ， 一个非奇异对角矩阵d r 擘一) ( n 一，和m 阶及n 阶置换矩阵p q ， 使得p a q = bo d 因为由式子a = b c 可得a = b c ( a 表示a 的关联矩阵) ，因此， 若a 是布尔矩阵中的素元，则a 是非负矩阵中的素元d ec a e nd 和 g r e g o r yd a 研究了布尔矩阵中的素元，给出判别布尔矩阵中素元的几 个充分条件，通过布尔秩概念( 见下面定义1 3 8 ) 刻划了完全不可分 素布尔矩阵，相关研究见【1 0 5 7 等 定义1 3 8 设a 为一n 阶布尔矩阵使a = b c 成立的最小整数r 称为a 的布尔秩，其中b ，c 分别为nxr 和rxn 布尔矩阵 1 9 9 3 年， c h oh h 研究了布尔矩阵中的素元和布尔矩阵的分解特 双随机矩阵和双随机循环矩阵的素元研究8 性，证明了每一个非置换的布尔秩为几的布尔矩阵都能分解成布尔矩 阵中初等矩阵和素矩阵的乘积，见1 1 2 0 0 3 年，c h oh h ，k i ms r 利用链半环( 一个全序集其上的半环运算为a + b = m a x a 6 ，a b = m i n a 6 】- ，a ，b 是全序集半环上的元素) 上的半素矩阵( 素布尔矩阵和素 模糊矩阵的推广) 和他们的行空间的关系研究了链半环上的半素矩阵， 证明了任一个非单项式、有满半环秩( 半环秩的定义见下面定义1 3 9 ) 的矩阵都能分解成链半环上的初等矩阵和半素矩阵的乘积，见f 1 2 】 定义1 3 9 设a 螈( 冗) 为半环r 上的n 阶矩阵使a = b c 成立 的最小整数r 称为a 的半环秩，其中b ，c 分别为n r 和rx 佗阶矩 阵 利用任一n 阶双随机循环矩阵都可以唯一地表示为移位的n 一1 次 一元多项式和任一n 阶双随机矩阵都可以表示为置换矩阵的凸和的事 实，1 9 9 8 年，p i c c ig ，v a n d e nh o fj m 和v a ns c h u p p e nj h 等研究了 双随机矩阵和双随机循环矩阵中的素元，证明了如下重要结果：第一， 在双随机循环矩阵中： 定理1 3 1 0 设a d s 倪”具有位数n ，则a 不是双随机循环矩 阵中的素元 定理1 3 1 1 设a d s 僻炳( 3 ) 具有位数2 ，则a 是双随机循环 矩阵中的素元 定理1 3 1 2 设a = c i r c ( a ) d s c ? 期具有位数n ( o ) = 3 ，或4 ， 这里n = k ( a x ，a n ( 口) ，0 ，o ) 卑，k 心一1 ( 即口的正元素相邻) ， 则： 1 a 是双随机循环矩阵中的素元当且仅当： ( a ) 当n ( o ) = 3 时，a ； 0 2 口3 双随机矩阵和双随机循环矩阵的素元研究 9 2 当n ( a ) = 4 ，n = 5 时，a 不是双随机循环矩阵中的素元 第二，在双随机矩阵中： 定理1 3 1 3 矩阵a d 鼹黼，n 2 是双随机矩阵中的素元当且仅当 a = 只( 台j 0 ) 恳= p 1 ( a 。，) b ， 只，最p 似n ，n 1 ，n 2 n ，n 1 2 ，n 1 + n 2 = n ，a 1 d 踯1 期1 是双随机矩阵 中的完全不可分素元，i 兄? x n 。为n 2 阶单位矩阵 定理1 3 1 4设a d 肆黼，a = 妻a i p i ，n 3 ，口= ( o l ，一，口。! ) t 掣，n ( a ) = 2 ，则a 是双随机矩阵中的完全不可分素元当且仅当存在一 个8 ( 0 ，1 ) ，使a 置换等价于 s ，+ ( 1 一s ) = s 1 一s 0 o 0 8 0 0 0 0 s 1 一s 1 一s 0 0 s d 贸x n 定理1 3 1 5 设a d 宰3 ，a = 妻a i p i ，o = ( 口l 一，a 6 ) t 肆，亿( q ) = 3 ， 则a 是双随机矩阵中的一个完全不可分素元当且仅当a 置换等价于 ( 塞吼兰奶口2 三口5 ) ， 这里a 碑满足i ( n ) = ( 1 ，2 ，5 ) 见【4 7 本论文主要研究双随机矩阵和双随机循环矩阵中的素元在第二章， 研究了文 4 7 提出的如下问题和猜想： 问题a 设a = c i r c ( a ) d s 僻x n ，4 n ( a ) n ，且口= k ( 0 1 7 ，a n ( 口) ，0 ，o ) 。 艘，k m t ( 即。的正元素相邻) ，给出判别a 是否是双随机循环矩阵中 素元的方法 双随机矩阵和双随机循环矩阵的素元研究1 0 猜想a 设n 4 ，n 6 ，a = d r c ( a ) d s 僻黼，n ( a ) = n 一1 ，则a 不 是双随机循环矩阵中的一个素元 解决了问题a 和猜想a 当n ( o ) = 5 时的情形，也给出猜想a 成立 的一个充分条件在第三章，给出了判别有位数3 ，4 且对应向量的正 元素不全相邻的双随机循环矩阵是否为素元的方法在第四章，解决了 文 4 7 提出的如下问题： 一 问题b设a d 碑n ( n 3 ) 能唯一表示成a = 妻a i p i ，n = ( a l ，一，a n ! ) r 毋2 ，n ( o ) = 3 则a 是双随机矩阵中的素元当且仅当不存 在向量b ，c 础，n ( 6 ) ，佗( c ) 2 ，使 a = l m ( 6 ) c 成立，其中l m 是由置换乘法诱导出的拉丁方( 见后面定义4 2 3 ) 而存 在向量b ，c 毋2 ，n ( 6 ) ，n ( c ) 2 ，使上式成立当且仅当下述下标方程和双 随机拉丁方上的方程都有解： i ( o ) = ui ( l 。( 6 ) 町) j e i ( c ) a r = 厶( 6 ) c r 其中a r = 口i i ( 口) j s ：；，几( n ，) = 3 ，c r = ci i ( 。) 算引，n ( c r ) = 佗( c ) ，厶( 6 ) = l m ( 6 ) k ) i ( 。) 上述下标方程的可解性条件已在文【4 7 中刻划出，这里的问题是： 如何刻划上述双随机拉丁方上方程的可解性条件? 双随机矩阵和双随机循环矩阵的素元研究_ 1 1 1 4 基本符号 本文采用下面一些基本符号 非负整数集 o ，1 ，2 ，) 正整数集 集合 o ，1 ，2 ，n ) 集合 1 ，2 ，佗) 实数集 非负实数集 n 维实向量 n 维非负实向量 集合 z 霹l 鍪1 翰= 1 ) n 阶实矩阵集 n 阶非负矩阵集 双随机矩阵集 双随机循环矩阵集 n 阶置换矩阵集 n 阶布尔矩阵集 矩阵a 的转置 实系数多项式环 非负多项式半环( 非负多项式即系数为非负数的多项式) 系数和为l 的非负多项式半环 r 【z 】中所有h u r w i t z 多项式组成的集合 x 产 丸 2 瓦 心 磊 r 肌 舻 碑 鲜 胪 甲 畔 姗 严 玩 刖 酬 洲 删 双随机矩阵和双随机循环矩阵的素元研究 1 2 第二章判别对应向量的正元素全部相邻的双随机循环矩阵 是否为素元的方法 2 1 引言 利用任一几阶双随机循环矩阵都可以唯一地表示为移位的佗一1 次 一元多项式，文【4 7 研究了判别对应向量的正元素全部相邻的双随机循 环矩阵是否为素元的方法，得到如下结果： 1 设a d s q “是一个具有位数n 的双随机循环矩阵，则a 不是 双随机循环矩阵中的素元 2 设a d s q ”( 3 ) 是一个具有位数2 的双随机循环矩阵，则a 是双随机循环矩阵中的素元 3 设a = c i r c ( a ) d s c 2 - n 是一个具有位数竹( n ) = 3 ，或4 的双随 机循环矩阵，这里a = k ( 口1 - 一，a n ( 口) ，0 ，o ) 。卑，k 虬一1 ( 即a 的正元素相邻) ，则： ( a ) a 是双随机循环矩阵中的素元当且仅当： i 当n ( a ) = 3 时， a 2 a a ( b ) 当n ( o ) = 4 ，n = 5 时，a 不是双随机循环矩阵中的素元 并提出如下问题和猜想： 问题a 设a = c i r c ( a ) d s 僻黼，4 n ( a ) 6 时矩阵a 是否是素元的一个充要条件( 该结 果连同第二节的结果，实际上已解决了问题a 当n ( a ) = 5 时的情形) 2 2 判别有位数5 的6 阶矩阵是否为素元的方法 设向量口= 落( 0 1 ，a 2 ，a 3 ，a 4 ，a 5 ，o ) 。霹，n ( a ) = 5 ，5 ，如何判断 a = c i r c ( a ) 是否是素元? 我们有如下定理： 定理2 2 1 设向量a = 罐( 口1 ，a 2 ，a 3 ，a 4 ，a 5 ，o ) 2 碑，n ( a ) = 5 ，忌5 则a = c i r c ( a ) 不是双随机循环矩阵中的素元当且仅当向量a 的非零元 素至少满足下面条件之一： 1 a 2 a 3 a 4 一a l a 2 一a 5 a l o ； 2 a 2 a 3 6 4 - - a l a i - a 5 a ； 0 ，a 2 a 1 6 4 一a 3 a 2 一a 5 0 ，a 2 a 5 a 4 - - a l a 2 - - a 3 a i 0 ： 3 a 2 a l a 4 - a 3 a ；- a s a i = 0 ，或a 2 a 5 a 4 一a l 遁一a a a i = 0 ，或a 2 a 1 6 4 - - a 3 a ；一 a a a = 0 ，或a 2 a s a 4 一a l a ；一a s a i = o ； 4 a ( z ) = a s z 4 + 0 4 尹 4 - a 3 2 2 - 4 - a 2 z - 4 - a 1 = ( b 4 2 3 - 4 - b 3 2 2