American Institute of Mathematical Sciences

Advanced
October  2017, 37(10): 5285-5297. doi: 10.3934/dcds.2017229

A general law of large permanent

JÓzsef Balogh 1, and  Hoi Nguyen 2,

1. 

Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA
2. 

Department of Mathematics, The Ohio State University, Columbus, Ohio 43210, USA

Received  February 2017 Revised  April 2017 Published  June 2017

Fund Project: J. Balogh is partially supported by NSF grant DMS-1500121, Arnold O. Beckman Research Award (UIUC Campus Research Board 15006) and Langan Professional Scholarship. H. Nguyen is partially supported by NSF grant DMS-1600782.

In this short note we establish a law of large permanent for matrices with entries from an $\mathbf{N}^2$-indexed stochastic process. This answers a question by Bochi, Iommi and Ponce in [4].

Keywords: Permanent, law of large number.
Mathematics Subject Classification: 15A15, 26E60, 60B20.
Citation: JÓzsef Balogh, Hoi Nguyen. A general law of large permanent. Discrete & Continuous Dynamical Systems, 2017, 37 (10) : 5285-5297. doi: 10.3934/dcds.2017229
References:
[1]

S. Aaronson and H. Nguyen, Near invariance of the hypercube, Israel Journal of Mathematics, 212 (2016), 385-417.  doi: 10.1007/s11856-016-1291-z.  Google Scholar

[2]

N. Alon and S. Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, Electron. J. Combin., 15 (2008), Note 13, 2 pp.  Google Scholar

[3]

A. Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures and Algorithms, 14 (1999), 29-61.  doi: 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X.  Google Scholar

[4]

J. Bochi, G. Iommi and M. Ponce, The scaling mean and a law of large permanents, Adv. Math., 292 (2016), 374-409.  doi: 10.1016/j.aim.2016.01.013.  Google Scholar

[5]

J. Bochi, G. Iommi and M. Ponce, Perfect matching in inhomogeneous random bipartite graphs in random environment, submitted, https://arxiv.org/pdf/1605.06137v2.pdf. Google Scholar

[6]

L. M. Bregman, Some properties of non-negative matrices and their permanents, Soviet Math. Dokl., 14 (1973), 945-949.   Google Scholar

[7]

R. Brualdi, S. Parter and H. Schneider, The diagonal equivalence of a non-negative matrix to a stochastic matrix, J. Math. Anal. Appl., 16 (1966), 31-50.  doi: 10.1016/0022-247X(66)90184-3.  Google Scholar

[8]

K. P. Costello and V. Vu, Concentration of random determinants and permanent estimators, SIAM J. Discrete Math., 23 (2009), 1356-1371.  doi: 10.1137/080733784.  Google Scholar

[9]

G. Egorychev, The solution of van der Waerden's problem for permanents, Adv. in Math., 42 (1981), 299-305.  doi: 10.1016/0001-8708(81)90044-X.  Google Scholar

[10]

D. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki, 29 (1981), 931-938, 957.   Google Scholar

[11]

S. Friedland, Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums, Linear Algebra Appl., 434 (2011), 1615-1619.  doi: 10.1016/j.laa.2010.02.007.  Google Scholar

[12]

S. Friedland and S. Karlin, Some inequalities for the spectral radius of non-negative matrices and applications, Duke Math. J., 42 (1975), 459-490.   Google Scholar

[13]

S. Friedland, B. Rider and O. Zeitouni, Concentration of permanent estimators for certain large matrices, Annals Appl. Prob, 14 (2004), 1559-1576.  doi: 10.1214/105051604000000396.  Google Scholar

[14]

S. Friedland, S. Low and C. Tan, Nonnegative matrix inequalities and their application to non-convex power control optimization, SIAM J. Matrix Anal. Appl., 32 (2011), 1030-1055.  doi: 10.1137/090757137.  Google Scholar

[15]

C. D. Godsil and I. Gutman, On the matching polynomial of a graph, in Algebraic Methods in Graph Theory I-II (L. Lovász and V. T. Sós, eds. ), North-Holland, Amsterdam, 25 (1981), 241-249.  Google Scholar

[16]

N. R. Goodman, Distribution of the determinant of a complex Wishart distributed matrix, Annals Stat., 34 (1963), 178-180.  doi: 10.1214/aoms/1177704251.  Google Scholar

[17]

A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Elec. Comm. Probab., 5 (2000), 119-136.  doi: 10.1214/ECP.v5-1026.  Google Scholar

[18]

G. Halász and G. Székely, On the elementary symmetric polynomials of independent random variables, Acta Math. Acad. Sci. Hungar., 28 (1976), 397-400.  doi: 10.1007/BF01896806.  Google Scholar

[19]

G. Keller, Equilibrium States in Ergodic Theory London Math. Soc. Stud. Texts, vol. 42, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781107359987.  Google Scholar

[20]

N. Linial, A. Samorodnitsky and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica, 20 (2000), 545-568.  doi: 10.1007/s004930070007.  Google Scholar

[21]

A. Marshall and I. Olkin, Scaling of matrices to achieve specified row and column sums, Numer. Math., 12 (1968), 83-90.  doi: 10.1007/BF02170999.  Google Scholar

[22]

M. Menon, Matrix links, an extremization problem, and the reduction of a non-negative matrix to one with prescribed row and column sums, Canad. J. Math., 20 (1968), 225-232.  doi: 10.4153/CJM-1968-021-9.  Google Scholar

[23]

H. Minc, Upper bounds for permanents of $(0, 1)$-matrices, Bull. Amer. Math. Soc., 69 (1963), 789-791.  doi: 10.1090/S0002-9904-1963-11031-9.  Google Scholar

[24] G. Rempala and J. Wesołowski, Symmetric Functionals on Random Matrices and Random Matchings Problems, Springer, New York, NY, 2008.   Google Scholar
[25]

M. Rudelson and O. Zeitouni, Singular values of Gaussian matrices and permanent estimators, Random Structures and Algorithms, 48 (2016), 183-212.  doi: 10.1002/rsa.20564.  Google Scholar

[26]

R. Sinkhorn, Continuous dependence on $A$ in the $D_1AD_2$ theorems, Proc. Amer. Math. Soc., 32 (1972), 395-398.  doi: 10.2307/2037825.  Google Scholar

[27]

R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math., 21 (1967), 343-348.  doi: 10.2140/pjm.1967.21.343.  Google Scholar

[28]

G. Soules, New permanental upper bounds for nonnegative matrices, Linear Multilinear Algebra, 51 (2003), 319-337.  doi: 10.1080/0308108031000098450.  Google Scholar

[29]

B. van der Waerden, Aufgabe 45, Jber. Deutsch. Math. Verein., 35 (1926), p117.   Google Scholar

[30]

A. Widgerson, Matrix and Operator scaling and their many applications, http://www.math.ias.edu/avi/talks. Google Scholar

show all references

References:
[1]

S. Aaronson and H. Nguyen, Near invariance of the hypercube, Israel Journal of Mathematics, 212 (2016), 385-417.  doi: 10.1007/s11856-016-1291-z.  Google Scholar

[2]

N. Alon and S. Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, Electron. J. Combin., 15 (2008), Note 13, 2 pp.  Google Scholar

[3]

A. Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures and Algorithms, 14 (1999), 29-61.  doi: 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X.  Google Scholar

[4]

J. Bochi, G. Iommi and M. Ponce, The scaling mean and a law of large permanents, Adv. Math., 292 (2016), 374-409.  doi: 10.1016/j.aim.2016.01.013.  Google Scholar

[5]

J. Bochi, G. Iommi and M. Ponce, Perfect matching in inhomogeneous random bipartite graphs in random environment, submitted, https://arxiv.org/pdf/1605.06137v2.pdf. Google Scholar

[6]

L. M. Bregman, Some properties of non-negative matrices and their permanents, Soviet Math. Dokl., 14 (1973), 945-949.   Google Scholar

[7]

R. Brualdi, S. Parter and H. Schneider, The diagonal equivalence of a non-negative matrix to a stochastic matrix, J. Math. Anal. Appl., 16 (1966), 31-50.  doi: 10.1016/0022-247X(66)90184-3.  Google Scholar

[8]

K. P. Costello and V. Vu, Concentration of random determinants and permanent estimators, SIAM J. Discrete Math., 23 (2009), 1356-1371.  doi: 10.1137/080733784.  Google Scholar

[9]

G. Egorychev, The solution of van der Waerden's problem for permanents, Adv. in Math., 42 (1981), 299-305.  doi: 10.1016/0001-8708(81)90044-X.  Google Scholar

[10]

D. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki, 29 (1981), 931-938, 957.   Google Scholar

[11]

S. Friedland, Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums, Linear Algebra Appl., 434 (2011), 1615-1619.  doi: 10.1016/j.laa.2010.02.007.  Google Scholar

[12]

S. Friedland and S. Karlin, Some inequalities for the spectral radius of non-negative matrices and applications, Duke Math. J., 42 (1975), 459-490.   Google Scholar

[13]

S. Friedland, B. Rider and O. Zeitouni, Concentration of permanent estimators for certain large matrices, Annals Appl. Prob, 14 (2004), 1559-1576.  doi: 10.1214/105051604000000396.  Google Scholar

[14]

S. Friedland, S. Low and C. Tan, Nonnegative matrix inequalities and their application to non-convex power control optimization, SIAM J. Matrix Anal. Appl., 32 (2011), 1030-1055.  doi: 10.1137/090757137.  Google Scholar

[15]

C. D. Godsil and I. Gutman, On the matching polynomial of a graph, in Algebraic Methods in Graph Theory I-II (L. Lovász and V. T. Sós, eds. ), North-Holland, Amsterdam, 25 (1981), 241-249.  Google Scholar

[16]

N. R. Goodman, Distribution of the determinant of a complex Wishart distributed matrix, Annals Stat., 34 (1963), 178-180.  doi: 10.1214/aoms/1177704251.  Google Scholar

[17]

A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Elec. Comm. Probab., 5 (2000), 119-136.  doi: 10.1214/ECP.v5-1026.  Google Scholar

[18]

G. Halász and G. Székely, On the elementary symmetric polynomials of independent random variables, Acta Math. Acad. Sci. Hungar., 28 (1976), 397-400.  doi: 10.1007/BF01896806.  Google Scholar

[19]

G. Keller, Equilibrium States in Ergodic Theory London Math. Soc. Stud. Texts, vol. 42, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781107359987.  Google Scholar

[20]

N. Linial, A. Samorodnitsky and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica, 20 (2000), 545-568.  doi: 10.1007/s004930070007.  Google Scholar

[21]

A. Marshall and I. Olkin, Scaling of matrices to achieve specified row and column sums, Numer. Math., 12 (1968), 83-90.  doi: 10.1007/BF02170999.  Google Scholar

[22]

M. Menon, Matrix links, an extremization problem, and the reduction of a non-negative matrix to one with prescribed row and column sums, Canad. J. Math., 20 (1968), 225-232.  doi: 10.4153/CJM-1968-021-9.  Google Scholar

[23]

H. Minc, Upper bounds for permanents of $(0, 1)$-matrices, Bull. Amer. Math. Soc., 69 (1963), 789-791.  doi: 10.1090/S0002-9904-1963-11031-9.  Google Scholar

[24] G. Rempala and J. Wesołowski, Symmetric Functionals on Random Matrices and Random Matchings Problems, Springer, New York, NY, 2008.   Google Scholar
[25]

M. Rudelson and O. Zeitouni, Singular values of Gaussian matrices and permanent estimators, Random Structures and Algorithms, 48 (2016), 183-212.  doi: 10.1002/rsa.20564.  Google Scholar

[26]

R. Sinkhorn, Continuous dependence on $A$ in the $D_1AD_2$ theorems, Proc. Amer. Math. Soc., 32 (1972), 395-398.  doi: 10.2307/2037825.  Google Scholar

[27]

R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math., 21 (1967), 343-348.  doi: 10.2140/pjm.1967.21.343.  Google Scholar

[28]

G. Soules, New permanental upper bounds for nonnegative matrices, Linear Multilinear Algebra, 51 (2003), 319-337.  doi: 10.1080/0308108031000098450.  Google Scholar

[29]

B. van der Waerden, Aufgabe 45, Jber. Deutsch. Math. Verein., 35 (1926), p117.   Google Scholar

[30]

A. Widgerson, Matrix and Operator scaling and their many applications, http://www.math.ias.edu/avi/talks. Google Scholar

[1]

Wilfrid Gangbo, Andrzej Świech. Optimal transport and large number of particles. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1397-1441. doi: 10.3934/dcds.2014.34.1397
[2]

Zengjing Chen, Weihuan Huang, Panyu Wu. Extension of the strong law of large numbers for capacities. Mathematical Control & Related Fields, 2019, 9 (1) : 175-190. doi: 10.3934/mcrf.2019010
[3]

Alexander Bobylev, Åsa Windfäll. Kinetic modeling of economic games with large number of participants. Kinetic & Related Models, 2011, 4 (1) : 169-185. doi: 10.3934/krm.2011.4.169
[4]

Shige Peng. Law of large numbers and central limit theorem under nonlinear expectations. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 4-. doi: 10.1186/s41546-019-0038-2
[5]

Mingshang Hu, Xiaojuan Li, Xinpeng Li. Convergence rate of Peng’s law of large numbers under sublinear expectations. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 261-266. doi: 10.3934/puqr.2021013
[6]

Yongsheng Song. Stein’s method for the law of large numbers under sublinear expectations. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 199-212. doi: 10.3934/puqr.2021010
[7]

Harald Friedrich. Semiclassical and large quantum number limits of the Schrödinger equation. Conference Publications, 2003, 2003 (Special) : 288-294. doi: 10.3934/proc.2003.2003.288
[8]

Jean-François Biasse. Subexponential time relations in the class group of large degree number fields. Advances in Mathematics of Communications, 2014, 8 (4) : 407-425. doi: 10.3934/amc.2014.8.407
[9]

Freddy Dumortier. Sharp upperbounds for the number of large amplitude limit cycles in polynomial Lienard systems. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1465-1479. doi: 10.3934/dcds.2012.32.1465
[10]

Gianluca Mola. Recovering a large number of diffusion constants in a parabolic equation from energy measurements. Inverse Problems & Imaging, 2018, 12 (3) : 527-543. doi: 10.3934/ipi.2018023
[11]

Aleksa Srdanov, Radiša Stefanović, Aleksandra Janković, Dragan Milovanović. "Reducing the number of dimensions of the possible solution space" as a method for finding the exact solution of a system with a large number of unknowns. Mathematical Foundations of Computing, 2019, 2 (2) : 83-93. doi: 10.3934/mfc.2019007
[12]

Zengjing Chen, Yuting Lan, Gaofeng Zong. Strong law of large numbers for upper set-valued and fuzzy-set valued probability. Mathematical Control & Related Fields, 2015, 5 (3) : 435-452. doi: 10.3934/mcrf.2015.5.435
[13]

Rana D. Parshad. Asymptotic behaviour of the Darcy-Boussinesq system at large Darcy-Prandtl number. Discrete & Continuous Dynamical Systems, 2010, 26 (4) : 1441-1469. doi: 10.3934/dcds.2010.26.1441
[14]

Futoshi Takahashi. On the number of maximum points of least energy solution to a two-dimensional Hénon equation with large exponent. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1237-1241. doi: 10.3934/cpaa.2013.12.1237
[15]

Michela Eleuteri, Luca Lussardi, Ulisse Stefanelli. A rate-independent model for permanent inelastic effects in shape memory materials. Networks & Heterogeneous Media, 2011, 6 (1) : 145-165. doi: 10.3934/nhm.2011.6.145
[16]

Afaf Bouharguane. On the instability of a nonlocal conservation law. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 419-426. doi: 10.3934/dcdss.2012.5.419
[17]

Chihurn Kim, Dong Han Kim. On the law of logarithm of the recurrence time. Discrete & Continuous Dynamical Systems, 2004, 10 (3) : 581-587. doi: 10.3934/dcds.2004.10.581
[18]

Michela Eleuteri, Luca Lussardi. Thermal control of a rate-independent model for permanent inelastic effects in shape memory materials. Evolution Equations & Control Theory, 2014, 3 (3) : 411-427. doi: 10.3934/eect.2014.3.411
[19]

J. Alberto Conejero, Enrique Hernández-Orallo, Pietro Manzoni, Marina Murillo-Arcila. A SIR-based model for contact-based messaging applications supported by permanent infrastructure. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 735-746. doi: 10.3934/dcdss.2019048
[20]

Baojun Bian, Nan Wu, Harry Zheng. Optimal liquidation in a finite time regime switching model with permanent and temporary pricing impact. Discrete & Continuous Dynamical Systems - B, 2016, 21 (5) : 1401-1420. doi: 10.3934/dcdsb.2016002

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (165)
  • HTML views (67)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy