On the X-rays of permutations

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