Skip to main content
SpringerLink
Log in

On the permanent of a random symmetric matrix

  • Published:
Selecta Mathematica Aims and scope Submit manuscript

Abstract

Let \(M_{n}\) denote a random symmetric \(n\times n\) matrix, whose entries on and above the diagonal are i.i.d. Rademacher random variables (taking values \(\pm 1\) with probability 1/2 each). Resolving a conjecture of Vu, we prove that the permanent of \(M_{n}\) has magnitude \(n^{n/2+o(n)}\) with probability \(1-o(1)\). Our result can also be extended to more general models of random matrices. In our proof, we build on and extend some techniques introduced by Tao and Vu, studying the evolution of permanents of submatrices in a random matrix process.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Actually, this result is part of an extensive body of research concerning permanents of (non-random) matrices with \(\pm 1\) entries; see for example [6,7,8, 20, 21, 29, 30, 41, 42].

  2. This type of exposure is standard in the study of symmetric random matrices (see for example [10]).

  3. The matching number of a graph G is the largest number \(\nu \) such that one can find \(\nu \) disjoint edges in G.

References

  1. Aaronson, S.: Anti-concentration bound for permanents of Gaussian matrices?, MathOverflow post, https://mathoverflow.net/q/45822 (2010)

  2. Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. Theory Comput. 9, 143–252 (2013)

    Article  MathSciNet  Google Scholar 

  3. Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization, 4th edn. Wiley, Hoboken (2016)

    Google Scholar 

  4. Bourgade, P., Mody, K.: Gaussian fluctuations of the determinant of Wigner matrices. Electron. J. Probab. 24, Paper No. 96 (2019)

  5. Bourgain, J., Vu, V.H., Wood, P.M.: On the singularity probability of discrete random matrices. J. Funct. Anal. 258(2), 559–603 (2010)

    Article  MathSciNet  Google Scholar 

  6. Budrevich, M.V., Guterman, A.E.: Kräuter conjecture on permanents is true. J. Combin. Theory Ser. A 162, 306–343 (2019)

    Article  MathSciNet  Google Scholar 

  7. Budrevich, M.V., Guterman, A.E., Taranin, K.A.: On the divisibility of the permanent of \((\pm 1)\)-matrices, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 439 (2015), no. Chislennye Metody i Voprosy Organizatsii Vychisleniĭ. XXVIII, 26–37

  8. Budrevich, M.V., Guterman, A.E., Taranin, K.A.: On the Kräuter–Seifter theorem on the divisibility of permanents, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 463 (2017), no. Chislennye Metody i Voprosy Organizatsii Vychisleniĭ. XXX, 25–35

  9. Campos, M., Mattos, L., Morris, R., Morrison, N.: On the singularity of random symmetric matrices. Duke Math. J. 170(5), 881–907 (2021)

    Article  MathSciNet  Google Scholar 

  10. Costello, K.P., Tao, T., Vu, V.: Random symmetric matrices are almost surely nonsingular. Duke Math. J. 135(2), 395–413 (2006)

    Article  MathSciNet  Google Scholar 

  11. Eldar, L., Mehraban, S.: Approximating the permanent of a random matrix with vanishing mean. In: 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS,: IEEE Computer Soc. Los Alamitos, CA 2018, 23–34 (2018)

  12. Ferber, A.: Singularity of random symmetric matrices—simple proof. C. R. Math. Acad. Sci. Paris 359(6), 743–747 (2021)

    MathSciNet  MATH  Google Scholar 

  13. Ferber, A., Jain, V.: Singularity of random symmetric matrices—a combinatorial approach to improved bounds. Forum Math. Sigma 7, e22 (2019)

    Article  MathSciNet  Google Scholar 

  14. Fox, J., Kwan, M., Sauermann, L.: Combinatorial anti-concentration inequalities, with applications. Math. Proc. Camb. Philos. Soc. 171(2), 227–248 (2021)

    Article  MathSciNet  Google Scholar 

  15. Girko, V.L.: A central limit theorem for random determinants. Teor. Veroyatnost. i Primenen. 24(4), 728–740 (1979)

    MathSciNet  MATH  Google Scholar 

  16. Girko, V.L.: A refinement of the central limit theorem for random determinants. Teor. Veroyatnost. i Primenen. 42(1), 63–73 (1997)

    Article  MathSciNet  Google Scholar 

  17. Janson, S.: The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph. Combin. Probab. Comput. 3(1), 97–126 (1994)

    Article  MathSciNet  Google Scholar 

  18. Kahn, J., Komlós, J., Szemerédi, E.: On the probability that a random \(\pm 1\)-matrix is singular. J. Am. Math. Soc. 8(1), 223–240 (1995)

    MathSciNet  MATH  Google Scholar 

  19. Komlós, J.: On the determinant of \((0,\,1)\) matrices. Stud. Sci. Math. Hung. 2, 7–21 (1967)

    MATH  Google Scholar 

  20. Kräuter, A.R., Seifter, N.: On some questions concerning permanents of \((1,\,-1)\)-matrices. Isr. J. Math. 45(1), 53–62 (1983)

    Article  MathSciNet  Google Scholar 

  21. Kräuter, A.R., Seifter, N.: Some properties of the permanent of \((1,\,-1)\)-matrices. Linear Multilinear Algebra 15(3–4), 207–223 (1984)

    Article  MathSciNet  Google Scholar 

  22. Lundow, P., Markström, K.: Efficient computation of permanents, with applications to boson sampling and random matrices, arXiv preprint arXiv:1904.06229 (2019)

  23. Meka, R., Nguyen, O., Vu, V.: Anti-concentration for polynomials of independent random variables. Theory Comput. 12, Paper No. 11 (2016)

  24. Nguyen, H.H.: Inverse Littlewood-Offord problems and the singularity of random symmetric matrices. Duke Math. J. 161(4), 545–586 (2012)

    Article  MathSciNet  Google Scholar 

  25. Nguyen, H.H.: On the least singular value of random symmetric matrices. Electron. J. Probab. 17, Paper No. 53 (2012)

  26. Nguyen, H.H., Vu, V.: Random matrices: law of the determinant. Ann. Probab. 42(1), 146–167 (2014)

    Article  MathSciNet  Google Scholar 

  27. Rogozin, B.A.: On the increase of dispersion of sums of independent random variables. Teor. Verojatnost. i Primenen 6, 106–108 (1961)

    MathSciNet  Google Scholar 

  28. Rudelson, M., Vershynin, R.: The Littlewood-Offord problem and invertibility of random matrices. Adv. Math. 218(2), 600–633 (2008)

    Article  MathSciNet  Google Scholar 

  29. Seifter, N.: Upper bounds for permanents of \((1,-1)\)-matrices. Isr. J. Math. 48(1), 69–78 (1984)

    Article  MathSciNet  Google Scholar 

  30. Simion, R., Schmidt, F.W.: On \((+1,-1)\)-matrices with vanishing permanent. Discrete Math. 46(1), 107–108 (1983)

    Article  MathSciNet  Google Scholar 

  31. Tao, T., Vu, V.: On random \(\pm 1\) matrices: singularity and determinant. Random Struct. Algorithms 28(1), 1–23 (2006)

    Article  MathSciNet  Google Scholar 

  32. Tao, T., Vu, V.: On the singularity probability of random Bernoulli matrices. J. Am. Math. Soc. 20(3), 603–628 (2007)

    Article  MathSciNet  Google Scholar 

  33. Tao, T., Vu, V.: On the permanent of random Bernoulli matrices. Adv. Math. 220(3), 657–669 (2009)

    Article  MathSciNet  Google Scholar 

  34. Tao, T., Vu, V.: A central limit theorem for the determinant of a Wigner matrix. Adv. Math. 231(1), 74–101 (2012)

    Article  MathSciNet  Google Scholar 

  35. Tao, T., Vu, V.H.: Additive Combinatorics. Cambridge Studies in Advanced Mathematics, vol. 105. Cambridge University Press, Cambridge, Paperback edition (2010)

  36. Tikhomirov, K.: Singularity of random Bernoulli matrices. Ann. Math. (2) 191(2), 593–634 (2020)

    Article  MathSciNet  Google Scholar 

  37. Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189–201 (1979)

    Article  MathSciNet  Google Scholar 

  38. Vershynin, R.: Invertibility of symmetric random matrices. Random Struct. Algorithms 44(2), 135–182 (2014)

    Article  MathSciNet  Google Scholar 

  39. Vu, V.: Random matrices: a survey, slides for a presentation at an IPAM workshop, http://campuspress.yale.edu/vanvu/files/2013/01/ipam09.pdf, 2009

  40. Vu, V.H.: Recent progress in combinatorial random matrix theory. Probab. Surv. 18, 179–200 (2021)

    Article  MathSciNet  Google Scholar 

  41. Wang, E.T.-H.: On permanents of \((1,\,-1)\)-matrices. Isr. J. Math. 18, 353–361 (1974)

    Article  Google Scholar 

  42. Wanless, I.M.: Permanents of matrices of signed ones. Linear Multilinear Algebra 53(6), 427–433 (2005)

    Article  MathSciNet  Google Scholar 

  43. Wigner, E.P.: Characteristic vectors of bordered matrices with infinite dimensions. Ann. Math. (2) 62, 548–564 (1955)

    Article  MathSciNet  Google Scholar 

  44. Wigner, E.P.: On the distribution of the roots of certain symmetric matrices. Ann. Math. (2) 67, 325–327 (1958)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank Asaf Ferber for insightful discussions. We are also grateful to the referee for their careful reading of the paper, and their useful comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics, Stanford University, Stanford, CA, USA

    Matthew Kwan

  2. School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA

    Lisa Sauermann

Authors
  1. Matthew Kwan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lisa Sauermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lisa Sauermann.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

M. Kwan: Research supported by NSF Award DMS-1953990.

L. Sauermann: Research supported by NSF Grant CCF-1900460 and NSF Award DMS-1953772. Part of this work was completed while this author was a Szegő Assistant Professor at Stanford University.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kwan, M., Sauermann, L. On the permanent of a random symmetric matrix. Sel. Math. New Ser. 28, 15 (2022). https://doi.org/10.1007/s00029-021-00730-6

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00029-021-00730-6

Keywords

Mathematics Subject Classification

Search

Navigation