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

A general law of large permanent

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].

Citation: JÓzsef Balogh, Hoi Nguyen. A general law of large permanent. Discrete & Continuous Dynamical Systems - A, 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.

[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.

[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.

[4]

J. BochiG. 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.

[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.

[6]

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

[7]

R. BrualdiS. 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.

[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

S. FriedlandS. 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.

[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.

[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.

[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.

[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.

[19]

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

[20]

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

[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.

[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.

[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.

[24] G. Rempala and J. Wesołowski, Symmetric Functionals on Random Matrices and Random Matchings Problems, Springer, New York, NY, 2008.
[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.

[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.

[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.

[28]

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

[29]

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

[30]

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

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.

[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.

[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.

[4]

J. BochiG. 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.

[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.

[6]

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

[7]

R. BrualdiS. 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.

[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

S. FriedlandS. 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.

[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.

[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.

[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.

[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.

[19]

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

[20]

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

[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.

[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.

[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.

[24] G. Rempala and J. Wesołowski, Symmetric Functionals on Random Matrices and Random Matchings Problems, Springer, New York, NY, 2008.
[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.

[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.

[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.

[28]

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

[29]

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

[30]

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

[1]

Wilfrid Gangbo, Andrzej Świech. Optimal transport and large number of particles. Discrete & Continuous Dynamical Systems - A, 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]

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

[5]

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

[6]

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

[7]

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

[8]

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, 0 (0) : 0-0. doi: 10.3934/mfc.2019007

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Ambroise Vest. On the structural properties of an efficient feedback law. Evolution Equations & Control Theory, 2013, 2 (3) : 543-556. doi: 10.3934/eect.2013.2.543

[16]

Timothy C. Reluga, Jan Medlock, Alison Galvani. The discounted reproductive number for epidemiology. Mathematical Biosciences & Engineering, 2009, 6 (2) : 377-393. doi: 10.3934/mbe.2009.6.377

[17]

Michel Laurent, Arnaldo Nogueira. Rotation number of contracted rotations. Journal of Modern Dynamics, 2018, 12: 175-191. doi: 10.3934/jmd.2018007

[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]

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

[20]

Mustapha Mokhtar-Kharroubi. On permanent regimes for non-autonomous linear evolution equations in Banach spaces with applications to transport theory. Kinetic & Related Models, 2010, 3 (3) : 473-499. doi: 10.3934/krm.2010.3.473

2017 Impact Factor: 1.179

Metrics

  • PDF downloads (11)
  • HTML views (22)
  • Cited by (0)

Other articles
by authors

[Back to Top]