Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Author: Igor Rivin
Journal: Math. Comp. 85 (2016), 783-797
MSC (2010): Primary 20H05, 20P05, 20G99
DOI: https://doi.org/10.1090/mcom/2986
Published electronically: June 17, 2015
MathSciNet review: 3434881
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] 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 (94k:11072), https://doi.org/10.1215/S0012-7094-93-07107-4
  • [3] Herbert Edelsbrunner, Geometry and Topology for Mesh Generation, Cambridge Monographs on Applied and Computational Mathematics, vol. 7, Cambridge University Press, Cambridge, 2001. MR 1833977 (2002k:65206)
  • [4] Alex Eskin and Curt McMullen, Mixing, counting, and equidistribution in Lie groups, Duke Math. J. 71 (1993), no. 1, 181-209. MR 1230290 (95b:22025), https://doi.org/10.1215/S0012-7094-93-07108-6
  • [5] 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
  • [6] E. Fuchs and I. Rivin,
    How thin is thin,
    in preparation, 2012.
  • [7] 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 (2009f:94042), https://doi.org/10.1007/11761679_15
  • [8] Jane Gilman, Two-generator discrete subgroups of $ {\rm PSL}(2,{\bf R})$, Mem. Amer. Math. Soc. 117 (1995), no. 561, x+204. MR 1290281 (97a:20082), https://doi.org/10.1090/memo/0561
  • [9] Alexander Gorodnik and Amos Nevo, Splitting fields of elements in arithmetic groups, Math. Res. Lett. 18 (2011), no. 6, 1281-1288. MR 2915481, https://doi.org/10.4310/MRL.2011.v18.n6.a16
  • [10] 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 (2010a:14047)
  • [11] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439-561 (electronic). MR 2247919 (2007h:68055), https://doi.org/10.1090/S0273-0979-06-01126-8
  • [12] Roger A. Horn and Charles R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1990. Corrected reprint of the 1985 original. MR 1084815 (91i:15001)
  • [13] Martin Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327-354. MR 2342639 (2008g:20009), https://doi.org/10.1007/s00222-007-0065-y
  • [14] Martin Kassabov, Universal lattices and unbounded rank expanders, Invent. Math. 170 (2007), no. 2, 297-326. MR 2342638 (2009b:20079), https://doi.org/10.1007/s00222-007-0064-z
  • [15] Anthony W. Knapp, Representation Theory of Semisimple Groups: An Overview Based on Examples, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 2001. Reprint of the 1986 original. MR 1880691 (2002k:22011)
  • [16] Anthony W. Knapp, Lie Groups Beyond an Introduction, 2nd ed., Progress in Mathematics, vol. 140, Birkhäuser Boston, Inc., Boston, MA, 2002. MR 1920389 (2003c:22001)
  • [17] 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 (83e:90112), https://doi.org/10.1016/0196-6774(80)90021-8
  • [18] A. K. Lenstra, H. W. Lenstra, and L. Lovász.
    Factoring polynomials with rational coefficients,
    Mathematische Annalen 261 (1982), no. 4, pp. 515-534.
  • [19] Martin W. Liebeck, Nikolay Nikolov, and Aner Shalev, Groups of Lie type as products of $ {\rm SL}_2$ subgroups, J. Algebra 326 (2011), 201-207. MR 2746060 (2011m:20037), https://doi.org/10.1016/j.jalgebra.2008.12.030
  • [20] Alexander Lubotzky, Finite simple groups of Lie type as expanders, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 5, 1331-1341. MR 2825166, https://doi.org/10.4171/JEMS/282
  • [21] Joseph Maher, Asymptotics for pseudo-Anosov elements in Teichmüller lattices, Geom. Funct. Anal. 20 (2010), no. 2, 527-544. MR 2671285 (2011h:37061), https://doi.org/10.1007/s00039-010-0064-9
  • [22] Joseph Maher, Random walks on the mapping class group, Duke Math. J. 156 (2011), no. 3, 429-468. MR 2772067 (2012j:37069), https://doi.org/10.1215/00127094-2010-216
  • [23] Morris Newman, Counting modular matrices with specified Euclidean norm, J. Combin. Theory Ser. A 47 (1988), no. 1, 145-149. MR 924457 (89b:15025), https://doi.org/10.1016/0097-3165(88)90048-9
  • [24] P. Nguyen,
    Lattice reduction algorithms: Theory and practice,
    Advances in Cryptology-EUROCRYPT 2011, pages 2-6, 2011.
  • [25] Phong Q. Nguyen and Damien Stehlé, Low-dimensional lattice basis reduction revisited, ACM Trans. Algorithms 5 (2009), no. 4, Art. 46, 48. MR 2571909 (2011c:68236), https://doi.org/10.1145/1597036.1597050
  • [26] 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.
  • [27] A. Page,
    Computing arithmetic kleinian groups,
    arXiv preprint arXiv:1206.0087, 2012.
  • [28] 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 (2009m:20077), https://doi.org/10.1215/00127094-2008-009
  • [29] Igor Rivin, Walks on graphs and lattices--effective bounds and applications, Forum Math. 21 (2009), no. 4, 673-685. MR 2541479 (2010j:20103), https://doi.org/10.1515/FORUM.2009.034
  • [30] I. Rivin,
    Generic phenomena in groups-some answers and many questions,
    arXiv preprint arXiv:1211.6509, 2012.
  • [31] Carl Ludwig Siegel, Symplectic geometry, Amer. J. Math. 65 (1943), 1-86. MR 0008094 (4,242b)
  • [32] 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. MR 581487 (83e:65018), https://doi.org/10.1137/0717034
  • [33] 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.
  • [34] Brigitte Vallée, Gauss' algorithm revisited, J. Algorithms 12 (1991), no. 4, 556-572. MR 1130316 (93b:11166), https://doi.org/10.1016/0196-6774(91)90033-U

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 20H05, 20P05, 20G99

Retrieve articles in all journals with MSC (2010): 20H05, 20P05, 20G99


Additional Information

Igor Rivin
Affiliation: School of Mathematics, University of St Andrews, St Andrews, UK
Address at time of publication: Department of Mathematics, Temple University, Philadelphia, Pennsylvania
Email: rivin@temple.edu

DOI: https://doi.org/10.1090/mcom/2986
Keywords: Groups, lattices, matrices, randomness, probability
Received by editor(s): February 15, 2014
Received by editor(s) in revised form: July 6, 2014, and August 19, 2014
Published electronically: June 17, 2015
Additional Notes: The author would like to thank Nick Katz , Chris Hall, Peter Sarnak, and Hee Oh for helpful conversations. He would also like to thank ICERM and Brown University for their hospitality and generous support. The author would like to thank the anonymous referees for their patience and helpful suggestions.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society