Counting dope matrices (Q2685364)

Given a complex polynomial \(P(x)\) of degree \(n\) and an \(m\)-tuple \(\Lambda = (\lambda_1,\ldots,\lambda_m)\) of distinct complex numbers, the authors define the {\em dope matrix} of \(P\) with respect to \(\Lambda\) to be the \(m\times (n+1)\) \(\{0,1\}\)-matrix \(D_P(\Lambda) = (\delta_{ij})\) where, for each \(i\in [1,m]\) and \(j\in [0,n]\), one has \[ \delta_{ij} = \begin{cases} 1 & \text{if } P^{(j)}(\lambda_i) = 0\\ 0 & \text{otherwise}\end{cases} \] where \(P^{(j)}\) is the \(j\)-th derivative of \(P\). A \(\{0,1\}\)-matrix is {\em dope} if it equals \(D_P(\Lambda)\) for some \(P\) and \(\Lambda\). These and the related multiplicity matrices of polynomials were recently studied by \textit{M. B. Nathanson} in [J. Algebra 614, 154--176 (2023; Zbl 07615767)]. The present authors first provide necessary and sufficient conditions for a \(2\times (n+1)\) matrix to be dope; in particular, it contains at most \(k\) nonzero entries in its last \(k+1\) columns for each \(k\in[0,n]\). They use this nice characterization to show that the number of \(2\times (n+1)\) dope matrices is \(\frac{1}{n+2}\binom{2n+2}{n+1}\), the \((n+1)\)-th of the ubiquitous Catalan numbers. They also provide upper bounds on the number of \(m\times (n+1)\) dope matrices as well as on the number of such dope matrices \(D_P(\Lambda)\) for each fixed \(\Lambda\). The authors also answer in the affirmative the extension problem (Open Question 4) posed by \textit{M. B. Nathanson} [loc. cit.]: Given any \(m\times (n+1)\) \(\{0,1\}\)-matrix \(D\), there is a polynomial \(P\) and an \(m\)-tuple \(\Lambda\) of distinct complex numbers for which \(D\) is the submatrix of \(D_P(\Lambda)\) consisting of the first \(n+1\) columns. They indeed prove a stronger statement: Given \(D\) and \(\Lambda\), it is possible to find \(P\) for which \(D\) is the submatrix of \(D_P(\Lambda)\) consisting of the first \(n+1\) columns; also, it is possible to choose \(P\) so that \(n\leq \deg(P)\leq m(n+2)\). Finally, some interesting comments are given and new open problems are posed.