正则(0,1)矩阵类的最小秩问题及其反问题

This project mainly study two kinds of important problems in (0,1) matrices, i.e., minimum rank problem of regular classes of (0,1) matrices and minimum rank solution of the (0,1) matrix equation A^m=J. Those problems are either new problems or closely related to some unsolved problems for many years. The research details include: 1. Solve a problem posed by Pullman and Stanford, and then find a general way for solving the minimum rank problem of regular classes of (0,1) matrices; 2. Study some kinds of minimum semiring rank of regular classes of (0,1) matrices, such as minimum Boolean rank and minimum nonnegative integer rank, and apply the obtained results and methods to the corresponding graph theory problems; 3. Study the inverse problem of the minimum rank problem of regular classes of (0,1) matrices, investigate the properties of regular classes of (0,1) matrices when the minimum rank is given. 4. Study the minimum rank solutions of the (0,1) matrix equation A^m=J, and discuss the theoretical meaning in the finite-time average consensus problems. Tools from matrix theory, graph theory, combinatorics, algebra and so on will be used for studying, and we aim to develop some new ideas and technologies in the research process，and solve some important and interesting problems in combinatorial matrix theory.

本项目主要研究(0,1)矩阵中的两类重要问题，即正则(0,1)矩阵类的最小秩问题和(0,1)矩阵方程A^m=J的最小秩解问题，这些问题要么是一些新颖的问题，要么与一些多年来未解决的问题密切相关。具体研究内容包括：1. 解决Pullman和Stanford提出的问题，找到解决正则(0,1)矩阵类最小秩问题的一般思路；2. 研究正则(0,1)矩阵类的一些最小半环秩问题，如最小布尔秩和最小非负整数秩等，并将所得结论和方法应用到相关图论问题中；3. 研究正则(0,1)矩阵类最小秩问题的反问题，在给定最小秩的情形下探索正则(0,1)矩阵类的特征；4. 研究(0,1)矩阵方程A^m=J的最小秩解问题，并讨论其在有限时间平均一致性问题中的理论意义。我们在研究方法上将综合运用矩阵论的技巧以及图论、组合、代数等数学工具，力争在研究过程中发展一些新的思想和方法, 并解决组合矩阵论中一些重要和有趣的问题。

在(0,1)矩阵问题的研究中，人们通常会关心某个参数的最值以及取到这个最值的矩阵或图的性质和结构，如正则(0,1)矩阵类的最小秩问题。正则(0,1)矩阵类的最小秩问题是组合矩阵论中一个重要且有趣的问题，该问题提出于上世纪八十年代并得到大量研究，其中Brualdi等人确定了2-正则和3-正则（0,1）矩阵类等一些特殊情形的最小秩，但对于更大的k未有进一步的结果。. 本项目研究了正则（0,1）矩阵类的最小秩问题、正则（0,1）矩阵的行并存数、（0,1）矩阵与其补矩阵的秩的关系等问题。本项目在正则（0,1）矩阵类的最小秩问题中做出了一些成果，包括：(i)确定了4-正则（0,1）矩阵类的最小秩，其科学意义在于为今后确定更大k时的正则（0,1）类的最小秩增添了信心；(ii)给出了阶数不超过20的5-10正则（0,1）矩阵类的最小秩，这为确定5-10正则（0,1）矩阵类的最小秩提供了很好的参考；(iii)回答了Pullman和Stanford提出的一个问题，这使得正则（0,1）矩阵类的最小秩问题变得更加清晰，给该问题指出了今后的研究方向；(iv)给出了正则(0,1)矩阵类行并存数的上下界，通过构造性的方法说明在某些情形下该上下界是精确的，其科学意义在于通过考虑正则（0,1）矩阵的行之间的内积来了解该矩阵的组合性质和结构，同时通过行并存数来计算正则（0,1）矩阵的行列式与奇异值等；(v)分别从一般情形和对称情形确定了一个(0,1)矩阵与其两类补矩阵的秩的和与差的可能范围，该理论结果可应用于有向图和无向图中一个图与其补图的秩的关系问题中。