Page 48 - Textos de Matemática Vol. 39

38 RICHARD A. BRUALDI AND GEIR DAHL
maximal element of I, and (ii) P has the largest number of inversions
of any permutation matrix P with P ≤ M.
(2) Given an arbitrary (0,1)-matrix M of order n, what is a permuta-
tion matrix P with P ≤ M having the largest (respectively, smallest) number of inversions. (This may very well be an NP-hard problem in general.)
(3) Let M be a (0, 1)-matrix of order n with a staircase pattern such that M has total support and In ≤ M. Define the Bruhat rank of M to be the smallest number rB(M) of permutation matrices Q such that if I is the Bruhat ideal generated by the Q’s, S(I) = M. Determine either a formula for the Bruhat rank of M or an algorithm for evaluating it.
References
[1] A.V. Borovik, I.M. Gelfand, N. White, Coxeter Matroids, Birkh¨auser, Boston-Basel- Berlin, 2003.
[2] R.A. Brualdi. Combinatorial Matrix Classes, Encyclopedia of Mathematics and its Ap- plications Vol. 39, Cambridge University Press, Cambridge, 2006.
[3] R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory, Encyclopedia of Mathe- matics and its Applications Vol. 108, Cambridge University Press, Cambridge, 1991.
[4] R.A. Brualdi and L. Deaett, More on the Bruhat Order for (0, 1)-Matrices, Linear Al-
gebra Appl., to appear.
[5] R.A. Brualdi and Suk-Geun Hwang, A Bruhat order for the Class of (0, 1)-matrices with
Row Sum Vector R and Column Sum Vector S, Electronic J. Linear Algebra, 12: 6–16,
2004.
[6] P. Magyar, Bruhat order for two flags and a line, J. Algebraic Combin., 21 (2005),
71–101.
Department of Mathematics University of Wisconsin
Madison, WI 53706, USA
E-mail address: brualdi@math.wisc.edu
Center of Mathematics for Applications Department of Informatics
University of Oslo
P.O. Box 1053 Blindern
NO-0316 Oslo, Norway
E-mail address: geird@math.uio.no