Further results on the minimum rank of regular classes of (0,1)-matrices

详细信息    查看全文

• 作者：Jin Zhong^a ; ^{zhongjin1984@126.com" class="auth_mail" title="E-mail the corresponding author} ; Chao Ma^b ; ^c ; ^{machao0923@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：15A03 ; 05B20 ; 05C35
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 December 2016
• 年：2016
• 卷：511
• 期：Complete
• 页码：447-459
• 全文大小：331 K

文摘

Let B(n,k)$\mathcal{B}(n,k)$ be the set of all (0,1)$(0,1)$-matrices of order n with constant line sum k   and let $\tilde{\nu }(n,k)$ be the minimum rank over B(n,k)$\mathcal{B}(n,k)$. It is known that $\lceil n/k\rceil \le \tilde{\nu }(n,k)\le \hat{\nu }(n,k)\le \lfloor n/k\rfloor +k$, where $\hat{\nu }(n,k)$ is the rank of a recursively defined matrix $\hat{A}\in \mathcal{B}(n,k)$. Brualdi, Manber and Ross showed that $\tilde{\nu }(n,k)=\lceil n/k\rceil$ if and only if k|n$k|n$. In this paper, we show that 52ca963b340baa5">$\tilde{\nu }(n,k)=\lfloor n/k\rfloor +k$ if and only if (n,k)$(n,k)$ satisfies one of the following three relations: (i) n≡±1 (mod k)$n\equiv \pm 1(\mathrm{mod}k)$, 2c40635341f" title="Click to view the MathML source">k=2$k=2$ or 3; (ii) n=k+1$n=k+1$, k≥2$k\ge 2$; (iii) n=4q+3$n=4q+3$, k=4$k=4$ and q≥1$q\ge 1$. Moreover, we obtain the exact values of $\tilde{\nu }(n,4)$ for all n≥4$n\ge 4$ and determine all the possible ranks of regular (0,1)$(0,1)$-matrices in 2c45" title="Click to view the MathML source">B(n,4)$\mathcal{B}(n,4)$. We also present some positive integer pairs (n,k)$(n,k)$ such that $\tilde{\nu }(n,k)<\hat{\nu }(n,k)<\lfloor n/k\rfloor +k$, which gives a positive answer to a question posed by Pullman and Stanford.