# Circular shift
A circular shift (also called a cyclic shift or end-around shift) is an operation on a sequence, such as a vector or string, in which elements are moved a given number of positions and the elements that fall off one end are reinserted at the other, so the length of the sequence is unchanged. Shifting a length-
sequence by
places is equivalent to shifting by
places, because the operation repeats with period
.
| Key fact | Detail |
|---|---|
| Definition | Elements shifted beyond the last position are re-introduced at the first; the output has the same shape as the input[1](https://numpy.org/doc/1.20/reference/generated/numpy.roll.html) |
| Index map | A shift of
places maps
to
| Matrix form | The operation is multiplication by an
[permutation matrix](https://www.edgepedia.org/permutation-matrix)
built from the standard basis vectors,
[2](https://terpconnect.umd.edu/~adrian/enee222/lecture_notes/enee222lectures.pdf) • [3](https://scg.ece.ucsb.edu/publications/theses/Pals_2005_Thesis.pdf) |
| Fourier behavior | A circular shift of a vector multiplies its discrete Fourier transform componentwise by a trigonometric function (modulation)[3](https://scg.ece.ucsb.edu/publications/theses/Pals_2005_Thesis.pdf) |
| Coding theory | A linear code is cyclic precisely when every cyclic shift of a codeword is again a codeword[4](https://bpb-us-w2.wpmucdn.com/sites.umassd.edu/dist/f/1260/files/2022/08/bwj-bookchapter.pdf) |
| Combinatorics on words | Cyclic shifts generate the equivalence classes called necklaces, or circular words[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol345-mfcs2025/html/LIPIcs.MFCS.2025.48/LIPIcs.MFCS.2025.48.html) |
## The operation
For a sequence of length
, a right circular shift by one position moves the last element to the front and every other element one place to the right; a left shift by one moves the first element to the end. NumPy's `numpy.roll` implements this for arrays: rolling the ten-element array `[0, 1, ..., 9]` by 2 gives `[8, 9, 0, 1, 2, 3, 4, 5, 6, 7]`, and rolling by −2 gives `[2, 3, 4, 5, 6, 7, 8, 9, 0, 1]`[1](https://numpy.org/doc/1.20/reference/generated/numpy.roll.html). The function accepts an `axis` argument; by default the array is flattened before shifting and the original shape is restored afterward, and since version 1.12.0 it supports rolling over multiple dimensions simultaneously[1](https://numpy.org/doc/1.20/reference/generated/numpy.roll.html).
Because shifting by
positions reproduces the original sequence, the shift amount is naturally taken modulo
.
## Matrix form and the Fourier connection
The circular shift is a linear operator. Acting on a column vector of length
, a shift by one position is multiplication by the
permutation matrix
formed from the shifted standard basis vectors,
[2](https://terpconnect.umd.edu/~adrian/enee222/lecture_notes/enee222lectures.pdf). A shift by
places is the
-th power of this matrix, and the index map is
The shift property of the discrete [Fourier transform](https://www.edgepedia.org/fourier-transform) states that a circular shift of a vector
is equivalent to a modulation of its Fourier spectrum, a componentwise product with a trigonometric function. With the Fourier matrix
and
, the property is expressed as
, where
[3](https://scg.ece.ucsb.edu/publications/theses/Pals_2005_Thesis.pdf). Since this holds for arbitrary
,
, so the powers of the shift matrix are simultaneously diagonalized by the Fourier matrix; the diagonal entries of
are the second column of
[3](https://scg.ece.ucsb.edu/publications/theses/Pals_2005_Thesis.pdf). This is why the discrete Fourier transform treats a signal as periodic, or circular, rather than as a finite segment[6](https://spseducation.tue.nl/disciplines/discrete/discretesignalprocessing_transforms_dft_properties/).
## Cyclic codes
In coding theory, a linear code
of length
over a field is called a cyclic code if it is invariant under the cyclic shift transformation
[7](https://repositorio.udec.cl/bitstreams/a07549a0-ce11-4cd4-8487-e9de06a93c1c/download). Equivalently, any end-around shift of a codeword produces another codeword[4](https://bpb-us-w2.wpmucdn.com/sites.umassd.edu/dist/f/1260/files/2022/08/bwj-bookchapter.pdf). The cyclic shift map is a linear operator on
, and cyclic codes can be studied as linear subspaces invariant under this operator[8](https://store.fmi.uni-sofia.bg/fmi/algebra/bojilov/CYCLIC_CODES_AS_INVARIANT.pdf).
The invariance gives cyclic codes a practical advantage: the encoding operation can be implemented with simple shift registers with feedback connections, which is one reason cyclic codes are widely used in data links and on sequential-access devices such as tapes and disks[4](https://bpb-us-w2.wpmucdn.com/sites.umassd.edu/dist/f/1260/files/2022/08/bwj-bookchapter.pdf). Algebraically, identifying a vector
with the polynomial
of degree less than
shows that a cyclic code consists of all multiples, in the ring of polynomials modulo
, of its generator polynomial
[9](https://personalpages.manchester.ac.uk/staff/yuri.bazlov/code/notes/ch9.html). Generalizations partition the coordinates into several subsets, each shifted cyclically on its own, as in double and triple cyclic codes[10](https://arxiv.org/abs/1410.5604).
## Words, necklaces, and Lyndon words
In combinatorics on words, two words are equivalent if one is a cyclic shift of the other, and the equivalence classes are called necklaces, or circular words[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol345-mfcs2025/html/LIPIcs.MFCS.2025.48/LIPIcs.MFCS.2025.48.html) • [11](https://lib.ysu.am/disciplines_bk/df8ef580dc1f3f479cab7a36e31f6b13.pdf). Properties such as the weight of a word, the count of a given symbol, are invariant under shift, so the weight of a necklace can be defined from any of its representatives[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol345-mfcs2025/html/LIPIcs.MFCS.2025.48/LIPIcs.MFCS.2025.48.html).
A [Lyndon word](https://www.edgepedia.org/lyndon-word) is a primitive string, one that is not a power of a shorter word, that is lexicographically smallest among the cyclic permutations of its characters[12](https://arxiv.org/abs/1301.0103). Lyndon words are used for constructing bases in free Lie algebras, constructing de Bruijn sequences, and finding the lexicographically smallest rotation of a string[12](https://arxiv.org/abs/1301.0103).
## Other applications
In network coding, an
-dimensional circular-shift linear code of degree
over
(2) restricts its local encoding kernels to sums of at most
cyclic permutation matrices of size
[13](https://arxiv.org/abs/1707.02163). Cyclic shift permutation matrices also appear in the construction of quasi-cyclic codes, where a permutation matrix performs a downward cyclic shift of the rows of a parity-check matrix
[14](https://ycassuto.net.technion.ac.il/files/2018/05/5-8.pdf).
## References
1. [numpy.roll, NumPy v1.20 Manual](https://numpy.org/doc/1.20/reference/generated/numpy.roll.html)
2. [ENEE 222 lecture notes: circular shift and reversal, University of Maryland](https://terpconnect.umd.edu/~adrian/enee222/lecture_notes/enee222lectures.pdf)
3. [Pals 2005 thesis, UCSB](https://scg.ece.ucsb.edu/publications/theses/Pals_2005_Thesis.pdf)
4. [Cyclic codes book chapter, University of Massachusetts Dartmouth](https://bpb-us-w2.wpmucdn.com/sites.umassd.edu/dist/f/1260/files/2022/08/bwj-bookchapter.pdf)
5. [Generalized De Bruijn Words, Invertible Necklaces, and the Burrows–Wheeler Transform, MFCS 2025](https://drops.dagstuhl.de/storage/00lipics/lipics-vol345-mfcs2025/html/LIPIcs.MFCS.2025.48/LIPIcs.MFCS.2025.48.html)
6. [DFT properties, SPS Education, TU Eindhoven](https://spseducation.tue.nl/disciplines/discrete/discretesignalprocessing_transforms_dft_properties/)
7. [Cyclic Codes chapter, Universidad de Concepción](https://repositorio.udec.cl/bitstreams/a07549a0-ce11-4cd4-8487-e9de06a93c1c/download)
8. [Cyclic Codes as Invariant Subspaces, Radkova and Bojilov, Sofia University](https://store.fmi.uni-sofia.bg/fmi/algebra/bojilov/CYCLIC_CODES_AS_INVARIANT.pdf)
9. [Cyclic codes notes, Yuri Bazlov, University of Manchester](https://personalpages.manchester.ac.uk/staff/yuri.bazlov/code/notes/ch9.html)
10. [Z2-double cyclic codes, arXiv](https://arxiv.org/abs/1410.5604)
11. [Cyclic shifts and primitive words, course text](https://lib.ysu.am/disciplines_bk/df8ef580dc1f3f479cab7a36e31f6b13.pdf)
12. [2D Lyndon Words and Applications, arXiv](https://arxiv.org/abs/1301.0103)
13. [Circular-shift Linear Network Coding, arXiv](https://arxiv.org/abs/1707.02163)
14. [Quasi-cyclic codes construction, Technion](https://ycassuto.net.technion.ac.il/files/2018/05/5-8.pdf)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Enumerative combinatorics › Combinatorics on words › Necklaces and bracelets*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license