We give two new criteria by which pairs of permutations may be compared in defining the Bruhat order (of type A). One criterion utilizes totally nonnegative polynomials and the other utilizes Schur Bruhat order on Sn is often defined by comparing permutations = (1) · · ·(n) and = (1) · · ·(n) according to the following criterion | Two new criteria for comparison in the Bruhat order Brian Drake Sean Gerrish Mark Skandera Dept. of Mathematics Brandeis University MS 050 . Box 9110 Waltham MA 02454 bdrake@ Dept. of Mathematics University of Michigan 2074 East Hall Ann Arbor MI 48109-1109 sgerrish@ Dept. of Mathematics Dartmouth College 6188 Bradley Hall Hanover NH 03755-3551 Submitted Sep 25 2003 Accepted Jan 20 2004 Published Mar 31 2004 MR Subject Classifications 15A15 05E05 Abstract We give two new criteria by which pairs of permutations may be compared in defining the Bruhat order of type A . One criterion utilizes totally nonnegative polynomials and the other utilizes Schur functions. The Bruhat order on Sn is often defined by comparing permutations n n 1 n n and ơ Ơ 1 ơ n according to the following criterion n Ơ if Ơ is obtainable from n by a sequence of transpositions i j where i j and i appears to the left of j in n. See . 7 p. 119 . A second well-known criterion compares permutations in terms of their defining matrices. Let M n be the matrix whose i j entry is 1 if j n i and zero otherwise. Defining i 1 . i and denoting the submatrix of M n corresponding to rows I and columns J by M n ij we have the following. Theorem 1 Let n and Ơ be permutations in Sn. Then n is less than or equal to Ơ in the Bruhat order if and only if for all 1 i j n 1 the number of ones in M n i j is greater than or equal to the number of ones in M M O . See 1 2 3 6 pp. 173-177 8 for more criteria. Using Theorem 1 and our defining criterion we will state and prove the validity of two more criteria. Our first new criterion defines the Bruhat order in terms of totally nonnegative polynomials. A matrix A is called totally nonnegative TNN if the determinant of each square submatrix of A is nonnegative. See . 5 . A polynomial in n2 variables f x1 1 . xnn is called totally nonnegative TNN if for each TNN matrix A aitj THE ELECTRONIC JOURNAL OF COMBINATORICS .
