The maximal length of a chain in the Bruhat order for a class of binary matrices (Q649577): Difference between revisions

Let \(m\) and \(n\) be two positive integers and let \(R=(r_1,r_2,\dots,r_m)\) and \(S=(s_1,s_2,\dots,s_n)\) be positive integral vectors. The class of all \(m \times n\) \((0,1)\)-matrices with row sum vector \(R\) and column sum vector \(S\) is denoted by \({\mathcal{A}}(R,S)\). When \(m=n\) and \(R = S = (k,k,\dots,k)\) where \(k\) is a positive integer such that \(0 \leq k \leq n\), the notation \({\mathcal{A}}(n,k)\) is used instead of \({\mathcal{A}} (R,S)\). A Bruhat partial order \(\preceq\) on a nonempty class \({\mathcal{A}} (R,S)\) is defined using a characterization of the Bruhat order on \(S_n\), the symmetric group of \(n\) elements, seen as the set of permutation matrices of \({\mathcal{A}} (n,1)\). For an \(m \times n\) matrix \(A = (a_{ij})\), let \(\sum_{A} = ( \sigma_{ij}(A))\) be the \(m \times n\) matrix defined by \[ \sigma_{ij}(A) = \sum_{k=1}^{i} \sum_{\ell =1}^{j} a_{k\ell} \] for \(1 \leq i \leq m\) and \(1 \leq j\leq n\). If \(A_1,A_2 \in {\mathcal{A}} (R,S)\), then \(A_1 \preceq A_2\) if and only if \(\sum_{A_1} \geq \sum_{A_2}\) in the entrywise order, i.e., \(\sigma_{ij}(A_1) \geq \sigma_{ij}(A_2)\) for all \(1\leq i\leq m\) and \(1\leq j \leq n\). In [``More on the Bruhat order for \((0,1)\)-matrices,'' Linear Algebra Appl. 421, No.\,2-3, 219--232 (2007; Zbl 1161.05018)], \textit{R.A. Brualdi} and \textit{L. Deaett} characterized all families of the class \({\mathcal{A}}(n,k)\) with a unique minimal element. They posed a question about the maximal length of a chain in the Bruhat order in the class \({\mathcal{A}}(2k,k)\). In this paper, the authors answer this question on the maximal length of a chain.