The Extremal Matrix of RS-matrices

【作者】 谭学忠；

【导师】 柳柏濂；

【作者基本信息】 华南师范大学 ， 运筹学与控制论， 2003， 硕士

【摘要】 不可约矩阵是布尔矩阵家族中的重要成员。几十年来，不可约矩阵的性质一直是这一领域研究的热点，并已形成了比较完善的理论。一个不可约矩阵A，如果它的所有n-1阶主子矩阵均是可约的，我们称之为RS-矩阵，其对应的伴随有向图称为RS-图。设s(A)表示A中的“1”的个数，文献[1]证明了：对于n阶不可约矩阵A，如果s(A)≥[n(n-1)]/2+1，则A至少含有一个不可约的(n-1)阶主子矩阵。本文利用有向图的方法构造出含有[n(n-3)]/2+4个“1”的RS-矩阵，并猜想这种矩阵是n阶RS-极矩阵。如果猜想成立，这将是文[1]结果的一个改进。最后，借助一个C程序证明猜想对n=6是正确的。更多还原

【Abstract】 Let RS[A] be the set of irreducible matrices with all principal matrices of order (n-1) reducible. In this paper we obtain an RS-matrix containing s(A) = [n(n-3)]/2 + 4 "1’s" and conjecture that if s(A) > [n(n-3)]/2 + 5, then there exists at least one irreducible principal submatrix of order (n-1).With the help of a C-program we show it is true for n = 6.更多还原