-
Previous Article
Nodal Bubble-Tower Solutions for a semilinear elliptic problem with competing powers
- DCDS Home
- This Issue
-
Next Article
A locally integrable multi-dimensional billiard system
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 |
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 [
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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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 and 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 and 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 and 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 and 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 and 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 and Related Fields, 2015, 5 (3) : 435-452. doi: 10.3934/mcrf.2015.5.435 |
[13] |
Xue Meng, Miaomiao Gao, Feng Hu. New proofs of Khinchin's law of large numbers and Lindeberg's central limit theorem –PDE's approach. Mathematical Foundations of Computing, 2022 doi: 10.3934/mfc.2022017 |
[14] |
Rana D. Parshad. Asymptotic behaviour of the Darcy-Boussinesq system at large Darcy-Prandtl number. Discrete and Continuous Dynamical Systems, 2010, 26 (4) : 1441-1469. doi: 10.3934/dcds.2010.26.1441 |
[15] |
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 and Applied Analysis, 2013, 12 (3) : 1237-1241. doi: 10.3934/cpaa.2013.12.1237 |
[16] |
Michela Eleuteri, Luca Lussardi, Ulisse Stefanelli. A rate-independent model for permanent inelastic effects in shape memory materials. Networks and Heterogeneous Media, 2011, 6 (1) : 145-165. doi: 10.3934/nhm.2011.6.145 |
[17] |
Afaf Bouharguane. On the instability of a nonlocal conservation law. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 419-426. doi: 10.3934/dcdss.2012.5.419 |
[18] |
Chihurn Kim, Dong Han Kim. On the law of logarithm of the recurrence time. Discrete and Continuous Dynamical Systems, 2004, 10 (3) : 581-587. doi: 10.3934/dcds.2004.10.581 |
[19] |
Ambroise Vest. On the structural properties of an efficient feedback law. Evolution Equations and Control Theory, 2013, 2 (3) : 543-556. doi: 10.3934/eect.2013.2.543 |
[20] |
Michela Eleuteri, Luca Lussardi. Thermal control of a rate-independent model for permanent inelastic effects in shape memory materials. Evolution Equations and Control Theory, 2014, 3 (3) : 411-427. doi: 10.3934/eect.2014.3.411 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]