Skip to main content

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