Equilibrated anti-Monge matrices (Q5947464)

Some new properties of the so-called Monge/anti-Monge matrices [cf. \textit{A. J. Hoffman}, Proc. Sympos. Pure Math. 7, 317-327 (1963; Zbl 0171.17801); \textit{R. E. Burkard}, \textit{B. Klinz}, and \textit{R. Rudolf}, Discrete Appl. Math. 70, No. 2, 95-161 (1996; Zbl 0856.90091)] are investigated. The anti-Monge real \(n\times m\) matrices \(C=(c_{ik})\) \((c_{ik}+ c_{jl}\geq c_{il} +c_{jk}\) for all \(i<j\), \(k<l)\) are called equilibrated matrices if all their row sums as well as column sums are equal to zero. The theorem is proved by which every square equilibrated anti-Monge matrix is similar to a nonnegative matrix; the similarity matrix transforms non-negative vectors into monotone vectors \((u=(u_i)\), \(u_1\geq u_2\geq \cdots\geq u_k;\;\Sigma u_i=0)\). It is shown that such class of anti-Monge matrices is closed under multiplication.