Page 35 - Textos de Matemática Vol. 39

THE BRUHAT SHADOW OF A PERMUTATION MATRIX
RICHARD A. BRUALDI AND GEIR DAHL
For Eduardo Marques de Sa´ on his 60th birthday.
Abstract. In this paper we consider the Bruhat order for permutation matri- ces, and several questions related to interchange operations on the set of per- mutation matrices. The notion of Bruhat shadow, which is related to Bruhat ideals, is introduced and investigated. In particular we characterize the Bruhat shadow of permutation matrices. Moreover, we give a result on the maximum number of inversions of a permutation matrix where the ones can lie in a certain type of pattern.
1. Introduction
Let Sn denote the set of all permutations σ = i1,i2,...,in of {1,2,...,n}. Aninversionofσisapairik,il withk<lbutik >il,thatis,apairofintegers out of their natural order. Let τ = j1, j2, . . . , jn be another permutation in Sn. Then σ is below τ in the Bruhat order (see e.g. [1] and [6]), written σ ≼B τ, provided that σ can be obtained from τ by a sequence of inversion-reducing transpositions of the form
(1.1) (a1,...,ai,...,aj,...,an)→(a1,...,aj,...,ai,...,an), whereai>aj.
With the Bruhat order, Sn is a partially ordered set, graded by the number of inversions. The unique minimal permutation is the identity permutation 1,2,...,n with no inversions. The unique maximal permutation is the anti- identity permutation n, n − 1, . . . , 2, 1 with n(n − 1)/2 inversions.
The permutation σ = i1,i2,...,in can be identified with a permutation matrix P = [pjk] where
pjk = 1 ifk=ij, (1≤j,k≤n) 0 otherwise.
Using this identification, we can reformulate the Bruhat order on permutations in terms of permutation matrices [5, 4, 2]. Let
L2=0 1andI2=1 0. 10 01
2000 Mathematics Subject Classification. 05B20, 06A07, 15A36.
Key words and phrases. Permutation matrix, Bruhat order, Bruhat shadow, interchange, inversions.
25