Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T06:38:05.104Z Has data issue: false hasContentIssue false
  • English
  • Français

The Orbit-Stabilizer Problem for Linear Groups

Published online by Cambridge University Press:  20 November 2018

John D. Dixon
John D. Dixon*
Affiliation:
Carleton University, Ottawa, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let G be a subgroup of the general linear group GL(n, Q) over the rational field Q, and consider its action by right multiplication on the vector space Qn of n-tuples over Q. The present paper investigates the question of how we may constructively determine the orbits and stabilizers of this action for suitable classes of groups. We suppose that G is specified by a finite set {x1, …, xr) of generators, and investigate whether there exist algorithms to solve the two problems:

(Orbit Problem) Given u, v ∊ Qn, does there exist x ∊ G such that ux = v; if so, find such an element x as a word in x1, …, xr and their inverses.

(Stabilizer Problem) Given u, v ∊ Qn, describe all words in x1, …, xr and their inverses which lie in the stabilizer

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 37 , Issue 2 , 01 April 1985 , pp. 238 - 259
Copyright
Copyright © Canadian Mathematical Society 1985

References

1. Baumslag, G., Cannonito, F. B. and Miller, C. F. III, Computable algebra and group embeddings, J. Algebra 69 (1981), 186–212.Google Scholar
2. Borel, A., Groupes linéaires algebraiques, Ann. of Math. 64 (1956), 20–82.Google Scholar
3. Borevich, Z. I. and Shafarevich, I. R., Number theory (Academic Press, New York, 1966).Google Scholar
4. Boyd, D. W., Speculations concerning the range of Mahler's measure. Can. Math. Bull. 24 (1981), 453–469.Google Scholar
5. Butler, G. and Cannon, C. C., Computing in permutation and matrix groups I, Math. Comp. 37 (1982), 663–670.Google Scholar
6. Cassels, J. W. S., An introduction to the geometry of numbers (Springer-Verlag, Berlin, 1971).Google Scholar
7. Chou, T.-W. J. and Collins, G. E., Algorithms for the solution of systems of linear dwphantine equations, SIAM J. Comput. 11 (1982), 687–708.Google Scholar
8. Dixon, J. D., The structure of linear groups (Van Nostrand Reinhold, London, 1971).Google Scholar
9. Dobrowolski, E., On the maximal modulus of conjugates of an algebraic integer, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 26 (1978), 291–292.Google Scholar
10. Grunewald, F. and Segal, D., Some general algorithms I: arithmetic groups, Ann. of Math. 112 (1980), 531–583.Google Scholar
11. Ignatov, Ju. A., Free and nonfree subgroups of PSL2(C) that are generated by two parabolic elements, Mat. Sb. (NS) 106 (148) (1978), 372–379 = Math. USSR-Sb. 35 (1978), 49–56.Google Scholar
12. Kaltofen, E., Factorization of polynomials, in Computer algebra, symbolic and algebraiccomputation (Springer-Verlag, New York, 1982), 95–114.Google Scholar
13. Koblitz, N., P-adic analysis: a short course on recent work (LMS Lecture Notes 46, C.U.P., Cambridge, 1980).CrossRefGoogle Scholar
14. Kopytov, V. M., Solvability of the occurence problem infinitely generated solvable groups of matrices over an algebraic number field, Algebra i Logika 7 (1968), 53–63 (Russian).Google Scholar
15. Lang, S., Algebra (Addison-Wesley, Massachusetts, 1967).Google Scholar
16. Lenstra, A. K., Lenstra, H. W. Jr. and Lovász, L., Factoring polynomials with rational coefficients. Math. Annalen 261 (1982), 515–534.Google Scholar
17. Lyndon, R. C. and Ullman, J. L., Groups generated by two parabolic linear fractional transformations, Can. J. Math. 21 (1969), 1388–1403.Google Scholar
18. Marden, M., The geometry of zeros of a polynomial in a complex variable (Amer. Math. Soc, New York, 1949).Google Scholar
19. Mihailova, K. A., The occurence problem for direct products of groups, Dokl. Akad. Nauk SSSR 119 (1958), 1103–1105 (Russian).Google Scholar
20. Miller, C. F. III, On group-theoretic decision problems and their classification (Princeton U. P., Princeton, 1971).Google Scholar
21. van der Poorten, A. J. and Loxton, J. H., Multiplicative relations in number fields, Bull. Austral. Math. Soc. 16 (1977), 83–98; errata, ibid 77 (1977), 151–155.Google Scholar
22. Sarkisjan, R. A., Algorithmic problems for linear algebraic groups I & II, Mat. Sb. (NS) 113 (155) (1980), 179–216 and 400–436.Google Scholar
23. Shanks, H. S., The rational case of a matrix problem of Harrison, Discrete Math. 28 (1979), 207–212.Google Scholar
24. Wehrfritz, B. A. F., Infinite linear groups (Springer-Verlag, New York, 1973).CrossRefGoogle Scholar