# Full text of "On the X-rays of permutations"

## See other formats

On the X-rays of Permutations in o o (N Hi Cecilia Bebeacua Imperial College Toufik Mansour Univ. of Haifa Simone Severini Univ. of York February 1, 2008 Alexander Postnikov MIT O U c3 > m m \o o in o ^— > a S > X Abstract The X-ray of a permutation is denned as the sequence of antidiagonal sums in the associated permutation matrix. X-rays of permutation are interesting in the context of Discrete Tomography since many types of integral matrices can be written as linear combinations of permutation matrices. This paper is an invitation to the study of X-rays of permutations from a combinatorial point of view. We present connections between these objects and nondecreasing differences of permutations, zero-sum arrays, decomposable permutations, score sequences of tournaments, queens' problems and rooks' problems. 1 Introduction Let S n be the set of all permutations of [n] = {1,2, ...,n} and let P n be the per- mutation matrix corresponding to ir £ S n . For k = 2, ...,2n, the (k — l)-th antidi- agonal sum of P w is Xk-i(ir) = J2i+j=k[^]i,j- The sequence of nonnegative integers x(tt) = xi(ir)x2(7r) ■ ■ ■ X2 n -i(^) is called the (antidiagonal) X-ray of it. The diagonal X-ray of tt, denoted by 2^(71"), is similarly defined. Note that x(ir) = x(7r _1 ), for every ir E S n . The sequence x(ir) may be also seen as a word over the alphabet [n]. As an example, the following table contains the X-rays of all permutations in £3: TT x(ir) TT ic(7r) TT x(tt) TT x(tt) TT x(tt) 123 10101 231,312 OHIO 132 10020 213 02001 321 00300 Although X-rays of permutations are interesting object on their own, among the reasons why they are of general interest in Discrete Tomography 6 is that many types of integral matrices can be written as linear combinations of permutation matrices (for example, binary matrices with equal row-sums and column-sums, like the adjacency matrices of Cayley graphs). Deciding whether for a given word w = ui\ . . . W2 n -i there exists tt G S n 1 such that w = x(ir) is an NP-complete problem [3] (see also [3]). The complexity is polynomial if the permutation matrix is promised to be wrapped around a cylinder [3J. It is necessary to keep into account that permutations are not generally specified by their X-rays: just consider the permutation ir = 73142865 and a = 72413865; we have x(ir) = x(a) = 000110200002100, x d (vr) = x d (a) = 00021111100010 and vr / a' 1 . This hints that an issue concerning X-rays is to quantify how much information about ir is contained in x(ir). In this paper we present some connections between X-rays of permutations and a variety of combinatorial objects. From a practical perspective, this may be useful in isolating and approaching special cases of the above problem. The remainder of the paper is organized as follows. In Section 2 we consider the problem of counting X-rays. We prove a bijection between X-rays and nondecreasing differences of permutations. We define the degeneracy of an X-ray x(ir) as the number of permutations a such that x(tt) = x(a), and we characterize the X-rays with the maximum degeneracy. We prove a bijection between X-ray of length Ak + 1 having maximum degeneracy and zero-sum arrays. In Section 3 we consider the notion of simple permutations. This notion seems to provide a good framework to study the degeneracy of X-rays, but the relation between simple permutations and X-rays with small degeneracy remains unclear. Section 4 is devoted to binary X-rays, that is X-rays whose entries are only zeros and ones. We characterize the X-rays of circulant permutation matrices of odd order. Moreover, we present a relation between binary X-rays, the n-queens problem (see, e.g., [§]), the score sequences of tournaments on n vertices (see |10| Sequence A000571]), and extremal Skolem sequences, see Conjecture 2.2]. A number of conjectures and open problems will be explicitly formulated or will simply stand out from the context. We use the standard notation for integers sequences from the oeis pm. 2 Counting X-rays We begin by addressing the following natural question: what is the number of different X-rays of permutations in S n l Although we are unable to find a generating function for the sequence, we show a bijection between X-rays and nondecreasing differences of permutations. The difference of permutations ir, a € S n is the integers sequence it — a = {w\,W2, ■ ■ ■ , w n ), where w\ = -n\ — a±, W2 = ^2 — &2, ■ ■ ■ , w n = ir n — a n . For example, if -/r = 1234 and a = 2413, we have e — 2413 = (—1,-2,2,1). Let x n be the numbers of different X-rays of permutations in S n . Let d n be the number of nondecreasing differences of permutations in S n . The number d n equals the number of different differences e — a with entries rearranged in the nondecreasing order. In other words, d n equals the number of different multisets of the form M(a) = {1 — a±, 2 — o"2, . . . , n — cr n }, with entries rearranged in the nondecreasing order. The entries of x(ir) are then the entries of the vector ei_ CT1 + 62-0-2 + ■ • • + &n-a n i where is the z-th coordinate vector of length 2n — 1. For example, for 2 vr = 3124 we have x(3124) = 0101200 and ei_ 3 + e 2 -i + e 3 _ 2 + e 4 - 4 = (0, 1, 0, 0, 0, 0, 0) + (0, 0, 0, 0, 1, 0, 0) + (0, 0, 0, 0, 1, 0, 0) + (0, 0, 0, 1, 0, 0, 0) = (0, 1, 0, 1, 2, 0, 0). On the basis of this reasoning we can state the following result. Proposition 1 The number x n of different X-rays of permutations in S n is equal to the number d n (see 11 (A Sequence A 01 9589]) of nondecreasing differences of permutations in Let us define and denote the degeneracy of an X-ray x(ir) by S(x(tt)) = \{a : x(a) = x(ir)}\. If x(tt) is such that 5(x(ir)) > 5(x(a)) for all a G S n , we write x max = x(jr) and we say that x(ir) has maximum degeneracy. The following table contains x n , x^ ax and 5(x max ) for n = 1, . . . , 8. n T n ^(^max) n •En T n •^max ^(•^max) 1 1 1 1 5 59 001111100 6 2 2 020, 101 1 6 246 00011211000 12 3 5 oino 2 7 1105 0001111111000 28 4 16 0012100 3 8 5270 000011121110000 76 It is not difficult to characterize the X-rays with maximum degeneracy. One can verify by induction that for n even, x^ = 00... 011... 121... 110... 00, with n/2 left-zeros and right-zeros, and n/2 — 1 ones; for n odd, x™^ = 00..011... 110..00, with (n — l)/2 left-zeros and right-zeros, and n ones. Notice that if x(ir) = £ max (for n odd) then P n can be seen as an hexagonal lattice with all sides of length (n + 1) /2. In each cell of the lattice there is or 1, and 1 is in exactly n cells; the column-sums are 1 and the diagonal and anti-diagonal sums are 0. This observation describes a bijection between permutations of odd order whose X-ray is x max and zero-sum arrays. An (m, 2n + l)-zero- sum array is an m x (2n + 1) matrix whose m rows are permutations of the 2n + 1 integers — n, —n + 1, . . . , n and in which the sum of each column is zero [2]. The matrix " -1 1 " 1 -1 1 -1 is an example of (3, 3)-zero-sum array. Thus we have the next result. 3 Proposition 2 The number S(x'^ aSuX ) for n odd is equal to the number of (3, 2n + 1)- zero- sum arrays (see 11 (A Sequence A002047]). Before concluding the section, it may be interesting to notice that if we sum entry-wise the X-rays of all permutations in S n we obtain the following sequence of In — 1 terms: (n - 1)!, 2(n - 1)!, . . . , (n - l)(n - 1)1, n\, (n - l)(n - 1)!, . . . ,2(n - 1)!, (n - 1)!. The meaning of the terms of this sequence is clear. 3 Simple permutations and X-rays In the previous section we have considered the X-rays with maximum degeneracy. What can we say about X-rays with degeneracy 1? If 5(x(tt)) = 1 then it is an involution (in such a case P n = p- 1 ) but the converse if not necessarily true. In fact consider the involution vr = 1267534. One can verify that x(vr) = x(<r) = x(p) = 1010000212000, for p = 1275634 and a = 1267453. In a first approach to the problem, it seems useful to study what kind of operations can be done "inside" a permutation matrix P n in order to obtain another permutation, say P a , such that x(tt) = x(o~) and P^ ^ P~ l . A intuitively good framework for this task is provided by the notion of block permutation. A segment and a range of a permutation are a set of consecutive positions and a set of consecutive values. For example, in the permutation 34512, the segment formed by the positions 2, 3, 4 is occupied by the values 4,5,1; the elements 1,2,3 form a range. A block is a segment whose values form a range. Every permutation has singleton blocks together with the block 12 ... n. A permutation is called simple if these are the only blocks [Q. A permutation is said to be a block permutation if it is not simple. Note that if ir is simple then it is ir^ 1 . Let S = ("7Ti G cS ni , . .. ,7Tfc G S nk ) be an ordered set and let 7T G <Sfc. We assume that in S there exists 1 < i < k such that rij > 1. We denote by P(ir,S) the (ni + • • • + Uf,)- dimensional permutation matrix which is partitioned in k 2 blocks, Bx t i, . . . , f,, such that Bij = P Wt if 7r(«) = j and Bij = 0, otherwise. We denote by tt[tti, . . . , ir^] (or equivalently by (vr)[S']) the permutation corresponding to P(ir,S). For example, let S and vr = 231. Then and 23l[S] = 231[231, 21, 312] the X-ray of (7r)[S'] invariant: (231,21,312) -P231 P(231,5) = -P312 56487312. The matrix P(231,S") can be modified leaving P(231,(312,21,312)) -P312 312 P T ^231 P21 4 It is clear that 56487312 is a block permutation. Let it be a simple permutation then possibly 5(x(tt)) > 1. In fact, the permutation tt = 531642 is simple, but 5(x(ir)) = 6, since x(ir) = 00111011100 = x(526134) = x(461253), plus the respective inverses. The permutations 526134 and 461253 are decomposable. This means that there possibly exists a decomposable permutation a such that x(a) = x(ir), even if tt is simple. There relation between simple permutations and X-rays of small degeneracy is not clear. Intuitively, a simple permutation allows less "freedom of movement" than a block permutation. It is also intuitive that we have low degeneracy when the nonzero entries of the X-ray are "distributed widely" among the 2n — 1 coordinates. The following result is easily proved. Proposition 3 Let a = ir[S] = tt[tti, . . . ,TTk] be a block permutation. Then S(x(tt)) > 1 if one of the following two conditions is satisfied: (1) If tt ^ 12 ... n then there is at least one tti £ S which is not an involution; (2) If tt = 12 . . . n then there are at least two 7Tj, tti G S which are not involution. Proof. (1) Let tt ^ 12 . . . n be any permutation. Take ir^ 1 for some TTi € S. Let p = it[iti, . . . , tt^ 1 , . . . , 7Tfc]. Since a is a block permutation, x(a) = x(p). However, if vr^ ^ tt^ 1 then a / p and a -1 / a. It follows that x(a) does not specify a. (2) Let tt = 12 ... n. Let all elements of S be involutions except 7Tj. Take ttJ 1 . Let p = 7r[7ri, . . . , irj 1 , . . . , Tik]- Again, x(a) = x(p), but this time p = a^ 1 . Then x(a) possibly specifies a. If, for distinct i,j, there are TTi,7Tj G S such that vr^ ^ ir^ 1 and ttj ^ irj 1 then X(cr') = x(7r[7Tl, . . .,-JTi 1 , . . ^TTj 1 , . . . ,7Tfc]) = x{a), but x(a) does not specify a, given that p / a^ 1 . m This is however not a sufficient condition for having 5(x(ir)) > 1. Permutations with equal X-rays are said to be in the same degeneracy class. The table below contain the number of permutations in S n which are in each degeneracy class, and the number of different degeneracy classes with the same cardinality, for n = 2, . . . , 8. These numbers provide a partition on n\. We denote by C(n) the total number of degeneracy classes. We write a(b), where a is the number of permutations in the degeneracy class and b the number of degeneracy classes of the same cardinality: C(2) = 1 1(2) C(3) = 2 1(4),2(1) C(4) = 3 1(9),2(6),3(1) C(5) = 5 1(20),2(26),3(6),4(6),6(1) C(6) = 10: 1(49),2(100),3(19),4(43),5(1),6(19),7(2),8(11),9(1),2(1) C(7) = 20: 1(114),2(345),3(60),4(229),5(18),6(118),7(11),8(98), 10(29) 11(2), 12(33), 14(13), 16(14), 18(6),20(4),21(1),22(2),26(1),28(1). We conjecture that if 5(x(ir)) = 1 then x(ir) does not have more than 2 adjacent nonzero coordinates. However the converse is not true if ir G S n for n > 8: for tt = 17543628 and 5 a = 16547328, we have x(vr) = x{a) = 100000320010001, but there are no more than 2 adjacent coordinates. 4 Binary X-rays In general, it does not seem to be an easy task to characterize X-rays. A special case is given by X-rays associated with circulant permutation matrices, for which is available an exact characterization. An X-ray x(ir) is said to be binary if Xi(ir) € {0, 1} for every 1 < i < 2n — 1. The set all permutations in S n with binary X-ray is denoted by B n . Counting binary X-rays means solving a modified version of the n-queens problem (see, e.g., jHJ) in which two queens do not attack each other if they are in the same NorthWest- SouthEst diagonal. The permutations with binary X-rays associated to circulant matrices are characterized in a straightforward way. Let C n be the permutation matrix associated with the permutation c n = 23 . . . nl, that is the basic circulant permutation matrix. The matrices in the set C n = {C°, C n , C 2 , . . . , C™ -1 } is the identity matrix) are called the circulant permutation matrices. The matrix C k is associated to c\. Observe that x(tt) can be seen as a binary number, since Xi(ir) £ {0, 1} for every i. Let dj(7r) = 2 2n - 1 -i ■ Xj (7r), j = 1,2, . . . ,2n - 1, and d(7r) = Yh=T di(ir), that is the decimal expansion of x(ir). The table below lists the X-rays of Cz,C§ and Cj, and their decimal expansions: 7T x(ir) d(vr) TT x(it) 123 10101 21 12345 101010101 341 231 OHIO 14 23451 010111010 186 34512 001111100 124 For 7T = c^, one can verify that d(7r) = \2l n+1 2 +k - \2^ n+1 2 +k + i2§ n+ ^~ k - \2^ n+ ^- k = a(k) (2 n - 1) (2 n - 1) 25™- fc +5 , where a{k) = (2 2k ~ 1 + l)/3 (A007583). In the attempt to count binary X-rays, we are able to establish a bijection between these objects and score sequences of tournaments. A tournament is a loopless digraph such that for every two distinct vertices i and j either (i,j) or (j, i) is an arc |Hj. The score sequence of an tournament on n vertices is the vector of length n whose entries are the out-degrees of the vertices of the tournament rearranged in nondecreasing order. Proposit ion 4 Let b n be the number of binary X-rays of permutations in S n and let s n be the number of different score sequences of tournaments on n vertices (see \1(A Sequence A000571J). Then b n < s n . 6 Proof. The number s n equals the number of integers lattice points (pq, . . . ,p n ) in the polytope P n given by the inequalities po = p n = 0, 2pi — pi + \ — Pi-\ < 1 and pi > 0, for i = 1, . . . , n — 1, see 0. Let xi, . . . , x n be the coordinates related to pi, . . . ,p n by Pi = x\ + . . . + xi — i 2 , for i = 1 , . . . , n. We can rewrite the inequalities defining the polytope P n in these coordinates as follows: x\ + . . . + Xi > i 2 , Xi + \ > x^ + 1 and x\ + . . . + x n = n 2 . For a permutation w G S n with a binary X-ray, let U = U{w) be the position of the z-th '1' in its X-ray. In other words, the sequence (Zi, . . . , l n ) is the increasing rearrangement of the sequence {w\, u>2 + 1, W3 + 2, . . . ,w n + n — 1). Then the numbers 1%, . . . , l n satisfy the inequalities defining the polytope P n (in the x-coordinates) . Indeed, l\ + . . . + l n = w\ + (u>2 + 1) + • • • + (w n + n — 1) = n 2 ; > Zj + 1; and the minimal possible value of h H h /j is (1 + 0) + (2 + 1) H h (i + (i - 1)) = i 2 . This finishes the proof. In order, to prove that b n = s n it is enough to show that, for any integer point (x%, . . . ,x n ) satisfying the above inequalities, we can find a permutation w € S n with Xi = k(w). ■ Conjecture 5 All binary X-rays of permutations in S n are in a bijective correspondence with integer lattice points (xi, . . . , x n ) of the polytope given by the inequalities x\ + • • • + Xi > i 2 , i = 1, . . . , n; x\ H h x n = n 2 , Xi+i -Xi>l, i = 1, . . . ,n - 1. For a permutation w E S n , the corresponding sequence {x\, . . . , x n ) is defined as the in- creasing rearrangement of the sequence (wi,W2 + 1, W3 + 2, . . . , w n + n — 1). Again, it is clear that X-rays injectively map into the integer points of the above polytope. One needs to show that there will be no gaps in the image. Also, it can be shown that the above conjecture is equivalent to Conjecture 2.2 from [7j concerning extremal Skolem sequences. The conjecture turns out to be false, when not restricted to binary X-rays. We conjecture also that the number of different X-rays of permutations in S n whose possible entries are and 2 is equal to the number of score sequences in tournament with n players, when 3 points are awarded in each game (see |10[ Sequence A047729]). 5 Palindromic X-rays What can we say about X-rays with special symmetries? The reverse of x(tt), denoted by x(ir), is the mirror image of x(tt). If x(tt) = x(ir) then tt is said to be palindromic. The reverse of tt, denoted by W, is mirror image of tt. For example, if tt = 25143 then W = 34152. The permutation matrix is obtained by writing the rows of P n in reverse order. In general x(tt) 7^ x(w). In fact, for tt = 25143, we have x(tt) = 0011001200, x(vr) = 0021001100 and x(w) = 0020011010. We denote by |M and M the matrices obtained by writing the columns and the rows of a matrix M in reverse order, respectively. 7 Proposition 6 Let l n be the number of permutations in S n with palindromic X-rays and let i n be the number of involutions in S n (see \1(A Sequence A000085]). Then, in general, l n > i n . Proof. Recall that a permutation n is an involution if tt = tt^ 1 . Since P^ = -Pj, it is clear that the diagonal X-ray of an involution tt is palindromic. The X-ray of a such that P a = \P n is then also palindromic. This shows that l n > i n . Now, consider a permutation matrix of the form Prr Po P T p is for some permutation p which is not an involution. Then P p ^ Pj , P a ^ Pj and a not an involution, but the diagonal X-ray of a is palindromic. The X-ray of tt such that P n = \P a is then also palindromic. This proves the proposition. ■ The next contains the values of l n for small n: n In n n In n 2 2 4 12 6 128 8 2110 3 4 5 32 7 436 9 8814 Proposition 7 Let l n ,A=D be the number of permutations in S n with: (1) equal diagonal and antidiagonal X-rays; (2) palindromic X-rays. Let r n be the number of permutations in S n invariant under the operation of first reversing and then taking the inverse (see 11 (A Sequnce A097296]). Then, in general, 1 Uj a=d > r n . Proof. We first construct the permutations which are invariant under the operation of first reversing and then taking the inverse. Let tt G S n where n = 2k. We look at P n as partitioned in 4 blocks: r A B C D P^ If ' A B ' T ' B A ' T r C D D C (Bf (Df (A) T {C) T then A = (B) T ,B = (D) T ,C = (A) T and D = (C) T . This implies the X-ray of P n being palindromic and, moreover, the diagonal and antidiagonal X-rays being equal. Note that we can construct P n only if n = 0(mod4), and in this case r n ^ 0. However, fixed n 0(mod4), we have r r , i+i, since the permutation matrix ' A " ' B ' Pa = 1 + 1 D c 8 can be always constructed from P n . (Permutation matrices like P n and P a provide the solutions of the "rotationally invariant" n-rooks problem. This points out that A097296 and A037224 are indeed the same sequence.) Now, the proposition is easily proved by observing that, for p = 369274185, P p is not of the form of P a . A direct calculation shows that rg = 12 and lg,A=D = 20. ■ References [1] Albert, M. H., M. D. Atkinson, and M. Klazar, The enumeration of simple permuta- tions, Journal of Integer Sequences 6 (2003), Article 03.4.4, 18 pp. [2] Bennett, B. T. and R. B. Potts, Arrays and brooks, J. Austral. Math. Soc. 7 (1967), 23-31. [3] Brunetti, S., A. Del Lungo, P. Gritzmann, and S. de Vries, On the reconstruction of permutation and partition matrices under tomographic constraints, preprint. [4] Del Lungo, A., Reconstructing permutation matrices from diagonal sums. Selected papers in honour of Maurice Nivat. Theoret. Comput. Sci. 281:1-2 (2002), 235-249. [5] Gardner, R. J., P. Gritzmann, and D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays, Discrete Math. 202 (1999), 45-71. [6] Herman, G. T. and A. Kuba (Eds.), Discrete tomography: Foundations, Algorithms and Applications, Birkhauser Boston, 1999. [7] Nordh, G., Generalization of Skolem Sequences, Master's Thesis, LITH-MAT-EX- 2003/05, Department of Mathematics, Linkopings universitet, 2003. [8] Reid, K. B., Tournaments, The Handbook of Graph Theory, J. L. Gross and J. Yellen (editors), CRC Press, Boca Raton, FL, 156-184, 2004. [9] Ruskey, F., http://www.theory.csc.uvic.ca/~cos/inf/misc/Queen.html. [10] Sloane, N. J. A., (2005), The On-Line Encyclopedia of Integer Sequences, http : //www. research. att . com/~nj as/sequences/. 9