Schreier vector

---

title: "Schreier vector" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computational-group-theory", "permutation-groups"] topic_path: "general/computational-group-theory" source: "https://en.wikipedia.org/wiki/Schreier_vector" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

In mathematics, especially the field of computational group theory, a Schreier vector is a tool for reducing the time and space complexity required to calculate orbits of a permutation group.

Overview

Suppose G is a finite group with generating sequence X = {x_1,x_2,...,x_r} which acts on the finite set \Omega = {1,2,...,n}. A common task in computational group theory is to compute the orbit of some element \omega \in \Omega under G. At the same time, one can record a Schreier vector for \omega. This vector can then be used to find an element g \in G satisfying \omega^g = \alpha, for any \alpha \in \omega^G. Use of Schreier vectors to perform this requires less storage space and time complexity than storing these g explicitly.

Formal definition

All variables used here are defined in the overview.

A Schreier vector for \omega \in \Omega is a vector \mathbf{v} = (v[1],v[2],...,v[n]) such that:

1. v[\omega] = -1
2. For \alpha \in \omega^G \setminus { {\omega} } , v[\alpha] \in {1,...,r} (the manner in which the v[\alpha] are chosen will be made clear in the next section)
3. v[\alpha] = 0 for \alpha \notin \omega^G

Use in algorithms

Here we illustrate, using pseudocode, the use of Schreier vectors in two algorithms

• Algorithm to compute the orbit of ω under G and the corresponding Schreier vector

:Input: ω in Ω, X = {x_1,x_2,...,x_r}

:for i in { 0, 1, …, n }: ::set v[i] = 0

:set orbit = { ω }, v[ω] = −1

:for α in orbit and i in { 1, 2, …, r }: ::if \alpha^{x_i} is not in orbit: :::append \alpha^{x_i} to orbit :::set v[\alpha^{x_i}] = i

:return orbit, v

• Algorithm to find a g in G such that ω**g = α for some α in Ω, using the v from the first algorithm

:Input: v, α, X

:if v[α] = 0: ::return false

:set g = e, and k = v[α] (where e is the identity element of G)

:while k ≠ −1: ::set g = {x_k}g, \alpha = \alpha^{x_k^{-1}}, k = v[\alpha]

:return g

References

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::