Generating Random Elements in SLn (Fq) by Random Transvections
Martin Hildebrand
DOI: 10.1023/A:1022472220105
Abstract
This paper studies a random walk based on random transvections in SL n( F q ) and shows that, given Ĩ \in > 0, there is a constant c such that after n + c steps the walk is within a distance Ĩ \in from uniform and that after n - c steps the walk is a distance at least 1 - Ĩ \in from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL n( F q ) to compare them with random transvections.
Pages: 133–150
Keywords: transvection; random walk; representation theory; upper bound lemma
Full Text: PDF
References
1. E. Artin, Geometric Algebra, John Wiley, New York, 1957.
2. P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA, 1988.
3. P. Diaconis and M. Shahshahani, "Generating a random permutation with random transpositions," Z. Wahrscheinlichkeitstheorie Verw. Gebeite 57 (1981), 159-179.
4. P. Diaconis and M. Shahshahani, "The subgroup algorithm for generating uniform random variables," Probab. Informat. Sci. 1 (1987), 15-32.
5. J.A. Green, "The characters of the finite general linear groups," Trans. Amer. Math. Soc. 80 (1955), 402-447.
6. J.G. Kemeny and J.L. Snell, Finite Markov Chains, Springer-Verlag, New York, 1976.
7. I.G. Macdonald, Symmetric Functions and Hall Polynomials. Clarendon Press, Oxford, 1979.
8. A. Rudvalis, Unpublished manuscript, 1988.
9. J.P. Serre, Linear Representations of Finite Groups, Springer-Verlag, New York, 1977.
10. M. Suzuki, Group Theory I, Springer-Verlag, New York, 1982.
11. A.V. Zelevinsky, Representation Theory of Finite Classical Groups: A Hopf Algebra Approach, Lecture Notes in Mathematics 869, Springer-Verlag, Berlin, 1981.
2. P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA, 1988.
3. P. Diaconis and M. Shahshahani, "Generating a random permutation with random transpositions," Z. Wahrscheinlichkeitstheorie Verw. Gebeite 57 (1981), 159-179.
4. P. Diaconis and M. Shahshahani, "The subgroup algorithm for generating uniform random variables," Probab. Informat. Sci. 1 (1987), 15-32.
5. J.A. Green, "The characters of the finite general linear groups," Trans. Amer. Math. Soc. 80 (1955), 402-447.
6. J.G. Kemeny and J.L. Snell, Finite Markov Chains, Springer-Verlag, New York, 1976.
7. I.G. Macdonald, Symmetric Functions and Hall Polynomials. Clarendon Press, Oxford, 1979.
8. A. Rudvalis, Unpublished manuscript, 1988.
9. J.P. Serre, Linear Representations of Finite Groups, Springer-Verlag, New York, 1977.
10. M. Suzuki, Group Theory I, Springer-Verlag, New York, 1982.
11. A.V. Zelevinsky, Representation Theory of Finite Classical Groups: A Hopf Algebra Approach, Lecture Notes in Mathematics 869, Springer-Verlag, Berlin, 1981.