The \(d\)-step conjecture and Gaussian elimination (Q1361811)

Let \(\varDelta (d,n)\) denote the maximum diameter of a graph of a \(d\)-polytope that has \(n\) facets. The \(d\)-step conjecture was formulated by Hirsch and asserts that \(\varDelta (d,2d)=d\). It was proved by different authors in many special cases (see, for example, a survey by \textit{V. Klee} and \textit{P. Kleinschmidt} [Math. Oper. Res. 12, 718-755 (1987; Zbl 0632.52007)]). Moreover, counterexamples have been found for slightly stronger conjectures. In the paper under review the \(d\)-step conjecture is proved equivalent to the following statement: For each ``general position'' \((d-1)\times (d-1)\) real matrix \(M\), the set of \((d!)^2\) matrices \(\{Q_\tau MQ_\sigma : \sigma , \tau \in \text{Sym} (d)\}\), where \(\text{Sym} (d)\) is the symmetric group on \(d\) letters, contains at least one \(Q_\tau MQ_\sigma\) having a positive Gaussian elimination factorization (that is the equation \(Q_\tau MQ_\sigma =L^{-1}U\) holds in which \(L\) and \(U\) are lower triangular and upper triangular matrices, respectively, that have positive nontriangular elements). The number \(\# (M)\) of pairs \((\sigma ,\tau )\in \text{Sym} (d)\times \text{Sym} (d)\) giving a positive \(L^{-1}U\) factorization is proved to be equal to the number of \(d\)-step paths between two vertices of an associated Dantzig figure. Numerical experiments presented all satisfy \(\# (M)\geq 2^{d-1}\) for \(3\leq d\leq 15\). The authors prove this inequality for \(d=3\) and suggest that the \(d\)-step conjecture may be true in all dimensions in the strong form \(\# (M)\geq 2^{d-1}\). Nevertheless in a note added in proof the authors announce that this strong \(d\)-step conjecture has been proved for \(d=4\) and disproved for \(d\geq 5\) by F. Holt and V. Klee. The \(d\)-step conjecture remains open.