decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1

Question

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in this paper (Theorem 3). However, the proof is kinda difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.

Answer 1

Let me illustrate the construction in the proof by examples. I will match the variables used in the paper, so we are looking for a decomposition of a $(n+1)$-vertex complete directed graph into $n+1$ directed cycles of length $n$.

The even case (example: $n=6$)

Here, we will label the vertices $0, 1, \dots, n-1$ and $\infty$, and we will do arithmetic modulo $n$ on the first $n$ of these vertices. When $n=6$, we have $7$ vertices: $0, 1, 2, 3, 4, 5, \infty$.

We start with the cycle $$\infty \to 0 \to n-1 \to 1 \to n-2 \to \dots \to n/2+1 \to n/2 - 1 \to \infty$$ In other words, if $\infty$ is the $1^{\text{st}}$ vertex, then the $(2k)^{\text{th}}$ vertex is $k-1$ and the $(2k+1)^{\text{th}}$ is $n-k$, up until the $n^{\text{th}}$ vertex; every vertex except $\frac n2$ appears in the cycle. When $n=6$, this gives us the cycle $$C_1 : \infty \to 0 \to 5 \to 1 \to 4 \to 2 \to \infty$$ To generate $n-1$ more cycles, we add a constant $1$ to $n-1$, modulo $n$, to every finite vertex. When $n=6$, this gives us the cycles $$C_2 : \infty \to 1 \to 0 \to 2 \to 5 \to 3 \to \infty$$ $$C_3 : \infty \to 2 \to 1 \to 3 \to 0 \to 4 \to \infty$$ $$C_4: \infty \to 3 \to 2 \to 4 \to 1 \to 5 \to \infty$$ $$C_5:\infty \to 4 \to 3 \to 5 \to 2 \to 0 \to \infty$$ $$C_6 : \infty \to 5 \to 4 \to 0 \to 3 \to 1 \to \infty$$ To verify correctness, we verify the differences between consecutive terms. The first cycle contains edges of the form $x \to x+2$, $x \to x+3$, $x \to x+4$, and so on through $x \to x+(n-1)$, each exactly once. It also contains exactly one edge to $\infty$ and exactly one edge from $\infty$. When we generate the other $n-1$ cycles, we use up all edges of these forms. What's left is every edge of the form $x \to x+1$, and those end up being our last cycle:

$$C_7 : 0 \to 1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 0$$

The odd case (example: $n=7$)

The overall strategy is the same, and the vertices are labeled in the same way. When $n=7$, we have $8$ vertices: $0,1,2,3,4,5,6,\infty$.

If we used the same pattern for the starting cycle as we did before, we would not end up cycling through all possible differences. To fix this, we switch halfway through: the first half of the cycle is $$ \infty \to 0 \to n-1 \to 1 \to n-2 \to \dots \to \lfloor n/4\rfloor - 1 \to \lfloor 3n/4\rfloor + 1 \to \lfloor n/4\rfloor$$ which follows the same pattern as before, but it continues from here as $$\lfloor n/4\rfloor \to \lfloor 3n/4\rfloor - 1 \to \lfloor n/4\rfloor + 1 \to \dots \to \lfloor n/2\rfloor - 1 \to \lfloor n/2\rfloor \to \infty$$ Just before we would have gone to vertex $\lfloor 3n/4\rfloor$, we switch patterns on the odd vertices: from then on, the $(2k+1)^\text{th}$ vertex is $n-k-1$, so we end up skipping $\lfloor 3n/4\rfloor$. When $n=7$, this gives us the cycle $$C_1 : \infty \to 0 \to 6 \to 1 \to 4 \to 2 \to 3 \to \infty$$ We generate $n-1$ more cycles in the same way as before. When $n=7$, we get $$C_2 : \infty \to 1 \to 0 \to 2 \to 5 \to 3 \to 4 \to \infty$$ $$C_3 : \infty \to 2 \to 1 \to 3 \to 6 \to 4 \to 5 \to \infty$$ $$C_4 : \infty \to 3 \to 2 \to 4 \to 0 \to 5 \to 6 \to \infty$$ $$C_5 : \infty \to 4 \to 3 \to 5 \to 1 \to 6 \to 0 \to \infty$$ $$C_6 : \infty \to 5 \to 4 \to 6 \to 2 \to 0 \to 1 \to \infty$$ $$C_7 : \infty \to 6 \to 5 \to 0 \to 3 \to 1 \to 2 \to \infty$$ The edges that end up skipped along the way are all edges of the form $x \to x + \lfloor n/2\rfloor + 1$, so we use the cycle made up of all such edges as our last cycle. When $n=7$ and $\lfloor n/2 \rfloor + 1 = 4$, this is $$C_8 : 0 \to 4 \to 1 \to 5 \to 2 \to 6 \to 3 \to 0$$