How to pick a random integer matrix? (and other questions)

Rivin, Igor

doi:10.1090/mcom/2986

How to pick a random integer matrix? (and other questions)
HTML articles powered by AMS MathViewer

by Igor Rivin PDF

Math. Comp. 85 (2016), 783-797 Request permission

Abstract:

We discuss the question of how to pick a matrix uniformly (in an appropriate sense) at random from groups big and small. We give algorithms in some cases, and indicate interesting problems in others.

References

G.E.P. Box and M.E. Muller, A note on the generation of random normal deviates, The Annals of Mathematical Statistics 29 (1958), no. 2, pp. 610–611.
W. Duke, Z. Rudnick, and P. Sarnak, Density of integer points on affine homogeneous varieties, Duke Math. J. 71 (1993), no. 1, 143–179. MR 1230289, DOI 10.1215/S0012-7094-93-07107-4
Herbert Edelsbrunner, Geometry and topology for mesh generation, Cambridge Monographs on Applied and Computational Mathematics, vol. 7, Cambridge University Press, Cambridge, 2001. MR 1833977, DOI 10.1017/CBO9780511530067
Alex Eskin and Curt McMullen, Mixing, counting, and equidistribution in Lie groups, Duke Math. J. 71 (1993), no. 1, 181–209. MR 1230290, DOI 10.1215/S0012-7094-93-07108-6
Pedro Jorge Freitas, On the action of the symplectic group on the Siegel upper half plane, ProQuest LLC, Ann Arbor, MI, 1999. Thesis (Ph.D.)–University of Illinois at Chicago. MR 2699568
E. Fuchs and I. Rivin, How thin is thin, in preparation, 2012.
Nicolas Gama, Nick Howgrave-Graham, and Phong Q. Nguyen, Symplectic lattice reduction and NTRU, Advances in cryptology—EUROCRYPT 2006, Lecture Notes in Comput. Sci., vol. 4004, Springer, Berlin, 2006, pp. 233–253. MR 2423546, DOI 10.1007/11761679_{1}5
Jane Gilman, Two-generator discrete subgroups of $\textrm {PSL}(2,\textbf {R})$, Mem. Amer. Math. Soc. 117 (1995), no. 561, x+204. MR 1290281, DOI 10.1090/memo/0561
Alexander Gorodnik and Amos Nevo, Splitting fields of elements in arithmetic groups, Math. Res. Lett. 18 (2011), no. 6, 1281–1288. MR 2915481, DOI 10.4310/MRL.2011.v18.n6.a16
Alex Gorodnik, François Maucourant, and Hee Oh, Manin’s and Peyre’s conjectures on rational points and adelic mixing, Ann. Sci. Éc. Norm. Supér. (4) 41 (2008), no. 3, 383–435 (English, with English and French summaries). MR 2482443, DOI 10.24033/asens.2071
Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1990. Corrected reprint of the 1985 original. MR 1084815
Martin Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327–354. MR 2342639, DOI 10.1007/s00222-007-0065-y
Martin Kassabov, Universal lattices and unbounded rank expanders, Invent. Math. 170 (2007), no. 2, 297–326. MR 2342638, DOI 10.1007/s00222-007-0064-z
Anthony W. Knapp, Representation theory of semisimple groups, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 2001. An overview based on examples; Reprint of the 1986 original. MR 1880691
Anthony W. Knapp, Lie groups beyond an introduction, 2nd ed., Progress in Mathematics, vol. 140, Birkhäuser Boston, Inc., Boston, MA, 2002. MR 1920389
J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), no. 2, 142–186. MR 604862, DOI 10.1016/0196-6774(80)90021-8
A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), no. 4, pp. 515–534.
Martin W. Liebeck, Nikolay Nikolov, and Aner Shalev, Groups of Lie type as products of $\textrm {SL}_2$ subgroups, J. Algebra 326 (2011), 201–207. MR 2746060, DOI 10.1016/j.jalgebra.2008.12.030
Alexander Lubotzky, Finite simple groups of Lie type as expanders, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 5, 1331–1341. MR 2825166, DOI 10.4171/JEMS/282
Joseph Maher, Asymptotics for pseudo-Anosov elements in Teichmüller lattices, Geom. Funct. Anal. 20 (2010), no. 2, 527–544. MR 2671285, DOI 10.1007/s00039-010-0064-9
Joseph Maher, Random walks on the mapping class group, Duke Math. J. 156 (2011), no. 3, 429–468. MR 2772067, DOI 10.1215/00127094-2010-216
Morris Newman, Counting modular matrices with specified Euclidean norm, J. Combin. Theory Ser. A 47 (1988), no. 1, 145–149. MR 924457, DOI 10.1016/0097-3165(88)90048-9
P. Nguyen, Lattice reduction algorithms: Theory and practice, Advances in Cryptology–EUROCRYPT 2011, pages 2–6, 2011.
Phong Q. Nguyen and Damien Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algorithms 5 (2009), no. 4, Art. 46, 48. MR 2571909, DOI 10.1145/1597036.1597050
F. Nielsen and R. Nock, Hyperbolic voronoi diagrams made easy, Computational Science and Its Applications (ICCSA), 2010 International Conference on, pages 74–80. IEEE, 2010.
A. Page, Computing arithmetic kleinian groups, arXiv preprint arXiv:1206.0087, 2012.
Igor Rivin, Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms, Duke Math. J. 142 (2008), no. 2, 353–379. MR 2401624, DOI 10.1215/00127094-2008-009
Igor Rivin, Walks on graphs and lattices—effective bounds and applications, Forum Math. 21 (2009), no. 4, 673–685. MR 2541479, DOI 10.1515/FORUM.2009.034
I. Rivin, Generic phenomena in groups–some answers and many questions, arXiv preprint arXiv:1211.6509, 2012.
Carl Ludwig Siegel, Symplectic geometry, Amer. J. Math. 65 (1943), 1–86. MR 8094, DOI 10.2307/2371774
G. W. Stewart, The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal. 17 (1980), no. 3, 403–409 (loose microfiche suppl.). MR 581487, DOI 10.1137/0717034
B. Vallée, A. Vera, et al., Lattice reduction in two dimensions: analyses under realistic probabilistic models, Proceedings of the 13th Conference on Analysis of Algorithms, AofA, volume 7, 2007.
Brigitte Vallée, Gauss’ algorithm revisited, J. Algorithms 12 (1991), no. 4, 556–572. MR 1130316, DOI 10.1016/0196-6774(91)90033-U