We compute the expected normalized trace norm (matrix/graph energy) of random symmetric band circulant matrices and graphs in the limit of large sizes, and obtain explicit bounds on the rate of convergence to the limit, and on the probabilities of large deviations. We also show that random symmetric band Toeplitz matrices have the same limit norm assuming that their band widths remain small relative to their sizes. We compare the limit norms across a range of related random matrix and graph ensembles.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmps_1181,
author = {Sergiy Koshkin},
title = {The asymptotic trace norm of random circulants and the graph energy},
journal = {Discussiones Mathematicae Probability and Statistics},
volume = {36},
year = {2016},
pages = {67-92},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmps_1181}
}
Sergiy Koshkin. The asymptotic trace norm of random circulants and the graph energy. Discussiones Mathematicae Probability and Statistics, Tome 36 (2016) pp. 67-92. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmps_1181/
[000] [1] B. Anderson, J. Ash, R. Jones, D. Rider and B. Saffari, Exponential sums with coefficients 0 or 1 and concentrated Lp norms, Annales de l’Institut Fourier (Grenoble) 57 (5) (2007), 1377-1404. | Zbl 1133.42004
[001] [2] B. von Bahr, On the convergence of moments in the central limit theorem, Ann. Math. Statist. 36 (1965), 808-818. | Zbl 0139.35301
[002] [3] Z. Bai, Methodologies in spectral analysis of large dimensional random matrices: a review, Statistica Sinica 9 (1999), 611-677. | Zbl 0949.60077
[003] [4] S. Blackburn and I. Shparlinski, On the average energy of circulant graphs, Linear Algebra and its Applications 428 (8-9) (2008), 1956-1963. | Zbl 1135.05036
[004] [5] A. Bose and J. Mitra, Limiting spectral distribution of a special circulant, Statistics & Probability Letters 60 (2002), 111-120. | Zbl 1014.60038
[005] [6] W. Bryc and A. Dembo, Spectral measure of large random Hankel, Markov and Toeplitz matrices, Ann. Probab. 34 (1) (2006), 1-38. | Zbl 1094.15009
[006] [7] X. Chen, X. Li and H. Lian, The skew energy of random oriented graphs, Linear Algebra and its Applications 438 (11) (2013), 4547-4556. | Zbl 1282.05049
[007] [8] R. van Dal, G. Tijssen, Z. Tuza, J. van der Veen, C. Zamfirescu and T. Zamfirescu, Hamiltonian properties of Toeplitz graphs, Discrete Math. 159 (1-3) (1996), 9-81. | Zbl 0864.05060
[008] [9] K. Das and I. Gutman, On incidence energy of graphs, Linear Algebra and its Applications 446 (2014), 329-344.
[009] [10] A. Daugavet, Convergence rates of some numerical characteristics of distributions in the central limit theorem, Vestnik Leningrad University Mathematics 13 (1981), 175-182. | Zbl 0479.60032
[010] [11] Ph. Davis and Ph. Rabinowitz, Methods of Numerical Integration (Academic Press, Orlando, FL, 1984).
[011] [12] W. Du, X. Li and Y. Li, The energy of random graphs, Linear Algebra and its Applications 435 (10) (2011), 2334-2346. | Zbl 1222.05153
[012] [13] A. Ilić and M. Bašic, New results on the energy of integral circulant graphs, Appl. Math. Comput. 218 (7) (2011), 3470-3482. | Zbl 1242.05163
[013] [14] S. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications 94 (Cambridge University Press, Cambridge, 2003).
[014] [15] I. Gohberg and M. Krein, Introduction to the Theory of Linear Nonselfadjoint Operators, Translations of Mathematical Monographs 18 (American Mathematical Society, Providence, 1969). | Zbl 0181.13504
[015] [16] R. Goldberg, Methods of Real Analysis (Wiley & Sons, New York-London-Sydney, 1976).
[016] [17] R. Gray, Toeplitz and circulant matrices: a review, Foundations and Trends in Communications and Information Theory 2 (3) (2006), 155-239.
[017] [18] U. Grenander and G. Szegö, Toeplitz Forms and Their Applications (University of California Press, Los Angeles, 1958). | Zbl 0080.09501
[018] [19] A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Electronic Communications in Probability 5 (2000), 119-136. | Zbl 0969.15010
[019] [20] I. Gutman, Hyperenergetic and hypoenergetic graphs, Zbornik Radova 14 (22) (2011), Selected topics on applications of graph spectra, 113-135. | Zbl 1289.05286
[020] [21] C. Hammond and S. Miller, Distribution of eigenvalues for the ensemble of real symmetric Toeplitz matrices, J. Theor. Probab. 18 (3) (2005), 537-566. | Zbl 1086.15024
[021] [22] V. Kargin, Concentration of the spectral measure for large matrices, Electronic Communications in Probability 14 (2009), 412-421.
[022] [23] P. Lancaster, Theory of Matrices (Academic Press, New York, 1969). | Zbl 0186.05301
[023] [24] T. Le and J. Sander, Extremal energies of integral circulant graphs via multiplicativity, Linear Algebra and its Applications 437 (6) (2012), 1408-1421. | Zbl 1243.05150
[024] [25] X. Li, Y. Shi and I. Gutman, Graph Energy (Springer, New York, 2012).
[025] [26] M. Meckes, Some results on random circulant matrices, in High dimensional probability V: the Luminy volume, Institute of Mathematical Statistics Collections, 5 (Beachwood, OH, 2009), 213-223.
[026] [27] B. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra and its Applications 40 (1981), 203-216. | Zbl 0468.05039
[027] [28] M. Miranda and P. Tilli, Asymptotic spectra of Hermitian block Toeplitz matrices and preconditioning results, SIAM Journal on Matrix Analysis and Applications 21 (3) (2000), 867-881. | Zbl 0957.15011
[028] [29] S. Molchanov, L. Pastur and A. Khorunzhii, Distribution of the eigenvalues of random band matrices in the limit of their infinite order, Theor. Math. Phys. 90 (2)(1992), 108-118.
[029] [30] V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2) (2007), 1472-1475. | Zbl 1113.15016
[030] [31] V. Nikiforov, Beyond graph energy: Norms of graphs and matrices, Linear Algebra and its Applications 506 (2016), 82-138. | Zbl 1344.05089
[031] [32] V. Nikiforov, Remarks on the energy of regular graphs, Linear Algebra and its Applications 508 (2016), 133-145. | Zbl 1346.05174
[032] [33] L. Paditz, On the analytical structure of the constant in the nonuniform version of the Esseen inequality, Statistics 20 (3) (1989), 453-464. | Zbl 0683.60018
[033] [34] I. Pinelis, On the nonuniform Berry-Esseen bound, (2013), available at http://arxiv.org/abs/1301.2828.
[034] [35] H. Ren and F. Zhang, Fully-angular polyhex chains with minimal total p-electron energy, J. Math. Anal. Appl. 326 (2) (2007), 1244-1253. | Zbl 1104.92072
[035] [36] H. Ren and F. Zhang, Double hexagonal chains with maximal Hosoya index and minimal Merrifield-Simmons index, J. Math. Chem. 42 (4) (2007), 679-690. | Zbl 1217.05214
[036] [37] J. Sander and T. Sander, The maximal energy of classes of integral circulant graphs, Discrete Appl. Math. 160 (13-14) (2012), 2015-2029. | Zbl 1246.05099
[037] [38] A. Shiryaev, Probability, Graduate Texts in Mathematics 95 (Springer-Verlag, New York, 1996).
[038] [39] M. Talagrand, A new look at independence, Ann. Probab. 24 (1) (1996), 1-34. | Zbl 0858.60019
[039] [40] G. Tee, Eigenvectors of block circulant and alternating circulant matrices, New Zealand J. Math. 36 (2007), 195-211. | Zbl 1186.15008
[040] [41] L. Tran, V. Vu and K. Wang, Sparse random graphs: eigenvalues and eigenvectors, Random Structures Algorithms 42 (1) (2013), 110-134. | Zbl 1257.05089