Page 40 - Textos de Matemática Vol. 39

30 RICHARD A. BRUALDI AND GEIR DAHL
3. Identification of Bruhat Shadows
We now consider how to identify whether a square (0,1)-matrix is the Bruhat shadow of a permutation matrix, that is, of a principal Bruhat ideal, and how to find such a permutation matrix. The 1’s in the Bruhat shadow must have a staircase pattern but this is not enough to conclude that a matrix is a Bruhat shadow (cf. Theorem 2.4).
We first return to the notion of Bruhat convex hull which we now extend to a general (0, 1)-matrix.
Let A be (0, 1)-matrix. The Bruhat convex hull of A, denoted by Bconv(A), is the (0,1)-matrix whose support is the union of all intervals Ii,j;i′,j′ where aij = ai′j′ = 1; see the previous section for the definition of such an interval. This definition agrees with our previous definition for permutation matrices.
The following lemma is easy to establish and we omit the proof. Lemma 3.1. Let B be a (0,1)-matrix. Then M has staircase pattern if and
only if B is the Bruhat convex hull of some (0,1)-matrix A.
Let B be a matrix with staircase pattern and let S be its support. Let (i,j) ∈ S and let B′ be the Bruhat convex hull of the matrix with support S \ {(i, j)}. Then (i, j) is an extreme position in B if B ̸= B′. As an example consider again the matrix A(P ) in (2.1). Its extreme positions are (3, 1), (5, 2), (7,4), (1,5) and (2,7). In general, the extreme positions of the shadow of a permutation matrix P can be determined directly from P as follows.
Remark 3.2. Let l1,l2,...,ln = n be the left-sequence and 1 = r1,r2,...,rn the right-sequence of a permutation σ = i1, i2, . . . , in in Sn. Then certain ele- ments of σ are determined by the left- and right-sequences. Let k be any integer between 1 and n such that k occurs in the right sequence. Let t be the largest integer such that rt = k. Then rt+1 > k, and it follows from the definition of the right-sequence that it = k. Similarly, if s is the smallest integer such that ls = j, then is = j. The positions (t,it) = (t,k) and (s,is) = (s,j) are extreme positions of the Bruhat shadow of σ and each extreme position arises in this way. We conclude that each longest constant subsequence of r1, r2, . . . , rn and each longest constant subsequence of l1, l2, . . . , ln determine an element (pos- sibly the same element) of the permutation σ and an extreme position of its shadow. Note the integers 1 and n in σ are specified in this way.
Lemma 3.3. The left- and right-sequences satisfy the following conditions:
(i) 1=r1 ≤r2 ≤···≤rn ≤n; (ii) 1≤l1 ≤l2 ≤···≤ln =n;
(iii) rk ≤ k ≤ lk for k = 1, 2, . . . , n;
(iv) For1≤k,j≤n,wehaverk =lj onlyifk=j.
Proof. Conditions (i) and (ii) are obvious from the definitions. Suppose that rk > k. Then each of the integers 1,2,...,k has to occur in the first k − 1