Sums of Permutation vectors

Helena Verrill

September 7, 1998

1 Introduction

Take a vector, (c_{i})_{i=1}^{n}, of length n, the entries being a permutation of 0, 1, ...n − 1. Then if n is odd, the sum of the entries is zero modulo n. Not all vectors (c_{i}) with ∑ c_{i} ≡ 0(n) are permutations, but here we will show that all such vectors are the sum of two permutation vectors.

1.1 Notation

Throughout, n is any fixed positive integer.

A null vector is a vector (c_{1}, c_{2}, … c_{n}) such that ∑_{i=1}^{n} c_{i} = 0.

A permutation vector is a vector (c_{1}, c_{2}, … c_{n}) such that {c_{1}, c_{2}, … c_{n}} = {0, 2, … n − 1}.

1.2 Example

The following shows an example of a null vector being the sum of two permutation vectors, for n = 7

(1, 3, 5, 0, 4, 2, 6 )
+ (0, 6, 4, 2, 3, 5, 1 )
(1, 2, 2, 2, 0, 0, 0 )

2 Proof of theorem

The result can be proved by induction on the length of the vector. We have the following result:

Lemma 2.1 For all integers d, 0 < d < n and for all c = (c_{i}) ∈ (ℤ/nℤ)^{d} there exists vectors a = (a_{1}, ...a_{d}) and b = (b_{1}, ...b_{d}) such that

c_{i} ≡ a_{i} + b_{i}(mod n)

and for i ≠ j a_{i} ≠ a_{j}, b_{i} ≠ b_{j}.

Proof. The result is clear for d = 1; we can take a = (c_{1}), b = (0).

Assume d < n − 1 Suppose we have the result for vectors of length 1, 2, … d. Given c of length d + 1, we will construct two vectors a and b with the required properties.

By induction, we have a and b of length d adding to give (c_{1}, … c_{d}):

a_{1}, a_{1}, a_{3}, … a_{d}
+ b_{1}, b_{2}, b_{3}, … b_{d}
c_{1}, c_{2}, c_{3}, … c_{d}

Let c_{d+1} = x. We would like to be able to add a further column, with u + v = x, so that a_{i} ≠ u, b_{i} ≠ v for i = 1, ...d. In the following table, on the right hand side, we write down a list of all possible pairs which add to give x:

a_{1}, a_{1}, a_{3}, … a_{d} ? 0, 1,  2,  3, … n − 1
+ b_{1}, b_{2}, b_{3}, … b_{d} ? x, x − 1, x − 2, x − 3, … x − n + 1
c_{1}, c_{2}, c_{3}, … c_{d} x, x, x,  x,  …  x

Cross out elements on the right hand side which we can not use:

a_{1}, a_{1}, a_{3}, … a_{d} ? …, α̸, β/, γ, …
+ b_{1}, b_{2}, b_{3}, … b_{d} ? …, δ̸, η, ξ/ …
c_{1}, c_{2}, c_{3}, … c_{d} x, x, x, x, … x

If there was any pair (i, x − i) with i, x − i both not crossed out, then we can take a_{d+1} = i and b_{d+1} = x − i.

Otherwise, for every i, for some j, a_{j} = i or b_{j} = x − i, and possibly both equalities hold.

Since we assume d < n − 1, there are at least two numbers u, v say, v ≠ u, with a_{i} ≠ u, v for i = 1, ...d. If n is odd, we may assume that u + v = x. This is because if this is not the case, let y = (x − u − v)/2. Since n is odd, 2 has an inverse modulo n, so we can divide by 2. Now consider the sum:

\begin{aligned}& a_{1} + y, & a_{1} + y, & a_{3} + y, & … & a_{d} + y & ? & …, & u + y, & …, & v + y, & … \\ + & b_{1} − y, & b_{2} − y, & b_{3} − y, & … & b_{d} − y & ? & …, & (x − u − y) ///////// , & …, & (x − v − y) ///////// , \\ & c_{1}, & c_{2}, & c_{3}, & … & c_{d} & x, & x, & x, & x, & … & x \end{aligned}

Since a_{i} ≠ a_{j} for i ≠ j, we also have a_{i} − y ≠ a_{j} − y for i ≠ j, and similarly for the b_{i}. So the new way of forming the sum still satisfies the required properties, and we can assume that we have u, v with u + v = x as required.

Now form a graph on the numbers 1, ...d. Add directed arrows, and arrow going from k to l if for some i, k = a_{i} and l = b_{i}

For example, for d = 6:

Diagram

Note that in such a graph every vertex will have degree at most two, and have at most one arrow coming in and at most one arrow going out, because two arrows going out from k for example, would mean that a_{i} = k and a_{j} = k for i ≠ j and this is impossible since a_{i} ≠ a_{j}, and similarly for arrows entering vertices, because of b_{i} ≠ b_{j} for i ≠ j.

Note also that giving such a directed graph on n vertices, with d arrows, such that every vertex is the terminal vertex of at most one arrow, and the initial vertex of at most one arrow, is equivalent to giving the list of pairs (a_{i}, b_{i}) up to a permutation. For example:

Diagram

By assumption, there is no a_{i} with a_{i} = u or a_{i} = v, but there are i and j with b_{i} = u, b_{j} = v. This means that in the graph, u and v are both terminal vertices, not initial vertices. This means that u and v are both in different components of the graph, since all components of the graph are paths, with at most one terminal vertex. Now, take the path terminating in v, and reverse all the arrows in this path. This will give rise to a new pair of vectors a′ and b′. An example is shown in the diagram:

Diagram

Let P_{v} be the set of vertices in the path containing v. The vectors a′, b′ may be defined as follows:

\begin{aligned}a_{i} = w ∈ P_{v} & ⇒ & b′_{i} = w \\ b_{i} = w ∈ P_{v} & ⇒ & a′_{i} = w \\ a_{i} = w ∉ P_{v} & ⇒ & a′_{i} = w \\ a_{i} = w ∉ P_{v} & ⇒ & b′_{i} = w \end{aligned}

We still have a′ + b′ = c and now we have v ≠ b′_{i} for all i = 1, ...d (since v is not a terminal vertex in the graph for v), and u ≠ a_{i} for i = 1, ...d, by our assumption. So now we can define a_{d+1} = u, b_{d+1} = v, and we have achieved the induction step.

Above, we assumed that n was odd so that we could divide by 2. If this is not the case, suppose we have found u and v not in {a_{i}}, as before, but a − u − v is odd. Then add the vector (1, ....1) to the second and bottom row of the table, leaving the top row unchanged:

a_{1},  a_{1},  a_{3}, … a_{d}  ?  …,  u,  …,  v,  …
G+ b_{1} − 1, b_{2} − 1, b_{3} − 1, … b_{d} − 1 ?  …, (x − u − 1) ///////// …, (x − u − 1) ///////// …
c_{1} − 1, c_{2} − 1, c_{3} − 1, … c_{d} − 1 x − 1, x − 1,  x − 1,  x − 1,  …  x − 1

Now x + 1 − u − v is even, and we can then inductively find A, B, vectors of length d + 1, in the same way as above, with A + B = c + 1. Now define B′ = B − I where I is the vector of length d + 1 with all entries 1. Now we have A + B′ = c, again achieving the induction step.

Theorem 2.1 Any null vector is a sum of two permutation vectors (both vectors being in (ℤ/nℤ)^{n}).

Proof. Let c = (c_{1}, … c_{n}) be the null vector. By the lemma, there are vectors a and b of length n − 1 with a + b = (c_{1}, … c_{n−1}), with a_{i} ≠ a_{j}, b_{i} ≠ b_{j} for i ≠ j. Since c is a null vector, we have

c_{n} ≡ −c_{1} − c_{2} ⋯ − c_{n−1}.

Thus

\begin{aligned}c_{n} & ≡ & −(a_{1} + b + 1) − (a_{2} + b_{2}) ⋯ − (a_{n−1} + b_{n−1}) \\ & ≡ & (−a_{1} − a_{2} − ⋯ − a_{n−1}) + (−b_{1} − b_{2} − ⋯ − b_{n−1}) \end{aligned}

In the case n is odd, we can let

\begin{matrix}a_{n} ≡ (−a_{1} − a_{2} − ⋯ − a_{n−1}), \\ b_{n} ≡ (−b_{1} − b_{2} − ⋯ − b_{n−1}), \end{matrix}

Since ∑_{i=1}^{n} a_{i} ≡ 0, but also ∑_{i=1}^{n} i ≡ 0, we can write ∑_{i=1}^{n} a_{i} ≡ ∑_{i=1}^{n} i, then cancel from both sides equal terms; if for some i < n a_{i} = a_{n}, then we get a_{i} + a_{n} = a_{i} + s, for a_{i} ≠ s; then we get a_{i} = a_{n} = s ≠ a_{i}, a contradiction.

In the case n even,

\begin{matrix}a_{n} ≡ n/2 + (−a_{1} − a_{2} − ⋯ − a_{n−1}), \\ b_{n} ≡ n/2 + (−b_{1} − b_{2} − ⋯ − b_{n−1}), \end{matrix}

Since ∑_{i=1}^{n} a_{i} ≡ n/2, but also ∑_{i=1}^{n} i = n(n − 1)/2 ≡ n/2, we can write ∑_{i=1}^{n} a_{i} ≡ ∑_{i=1}^{n} i, then cancel as before; if for some i < n a_{i} = a_{n}, then we get a_{i} + a_{n} = a_{i} + s, for a_{i} ≠ s, again a contradiction.