The asymptotic trace norm of random circulants and the graph energy

Sergiy Koshkin

Discussiones Mathematicae Probability and Statistics (2016)

  • Volume: 36, Issue: 1-2, page 67-92
  • ISSN: 1509-9423

Abstract

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

How to cite

top

Sergiy Koshkin. "The asymptotic trace norm of random circulants and the graph energy." Discussiones Mathematicae Probability and Statistics 36.1-2 (2016): 67-92. <http://eudml.org/doc/286928>.

@article{SergiyKoshkin2016,
abstract = {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.},
author = {Sergiy Koshkin},
journal = {Discussiones Mathematicae Probability and Statistics},
keywords = {random matrix; graph energy; matrix energy; circulant; Toeplitz matrix; band matrix; Dirichlet kernel; non-uniform Berry-Esseen estimate; Talagrand concentration inequality},
language = {eng},
number = {1-2},
pages = {67-92},
title = {The asymptotic trace norm of random circulants and the graph energy},
url = {http://eudml.org/doc/286928},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Sergiy Koshkin
TI - The asymptotic trace norm of random circulants and the graph energy
JO - Discussiones Mathematicae Probability and Statistics
PY - 2016
VL - 36
IS - 1-2
SP - 67
EP - 92
AB - 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.
LA - eng
KW - random matrix; graph energy; matrix energy; circulant; Toeplitz matrix; band matrix; Dirichlet kernel; non-uniform Berry-Esseen estimate; Talagrand concentration inequality
UR - http://eudml.org/doc/286928
ER -

References

top
  1. [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. Zbl1133.42004
  2. [2] B. von Bahr, On the convergence of moments in the central limit theorem, Ann. Math. Statist. 36 (1965), 808-818. Zbl0139.35301
  3. [3] Z. Bai, Methodologies in spectral analysis of large dimensional random matrices: a review, Statistica Sinica 9 (1999), 611-677. Zbl0949.60077
  4. [4] S. Blackburn and I. Shparlinski, On the average energy of circulant graphs, Linear Algebra and its Applications 428 (8-9) (2008), 1956-1963. Zbl1135.05036
  5. [5] A. Bose and J. Mitra, Limiting spectral distribution of a special circulant, Statistics &amp; Probability Letters 60 (2002), 111-120. Zbl1014.60038
  6. [6] W. Bryc and A. Dembo, Spectral measure of large random Hankel, Markov and Toeplitz matrices, Ann. Probab. 34 (1) (2006), 1-38. Zbl1094.15009
  7. [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. Zbl1282.05049
  8. [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. Zbl0864.05060
  9. [9] K. Das and I. Gutman, On incidence energy of graphs, Linear Algebra and its Applications 446 (2014), 329-344. 
  10. [10] A. Daugavet, Convergence rates of some numerical characteristics of distributions in the central limit theorem, Vestnik Leningrad University Mathematics 13 (1981), 175-182. Zbl0479.60032
  11. [11] Ph. Davis and Ph. Rabinowitz, Methods of Numerical Integration (Academic Press, Orlando, FL, 1984). 
  12. [12] W. Du, X. Li and Y. Li, The energy of random graphs, Linear Algebra and its Applications 435 (10) (2011), 2334-2346. Zbl1222.05153
  13. [13] A. Ilić and M. Bašic, New results on the energy of integral circulant graphs, Appl. Math. Comput. 218 (7) (2011), 3470-3482. Zbl1242.05163
  14. [14] S. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications 94 (Cambridge University Press, Cambridge, 2003). 
  15. [15] I. Gohberg and M. Krein, Introduction to the Theory of Linear Nonselfadjoint Operators, Translations of Mathematical Monographs 18 (American Mathematical Society, Providence, 1969). Zbl0181.13504
  16. [16] R. Goldberg, Methods of Real Analysis (Wiley &amp; Sons, New York-London-Sydney, 1976). 
  17. [17] R. Gray, Toeplitz and circulant matrices: a review, Foundations and Trends in Communications and Information Theory 2 (3) (2006), 155-239. 
  18. [18] U. Grenander and G. Szegö, Toeplitz Forms and Their Applications (University of California Press, Los Angeles, 1958). Zbl0080.09501
  19. [19] A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Electronic Communications in Probability 5 (2000), 119-136. Zbl0969.15010
  20. [20] I. Gutman, Hyperenergetic and hypoenergetic graphs, Zbornik Radova 14 (22) (2011), Selected topics on applications of graph spectra, 113-135. Zbl1289.05286
  21. [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. Zbl1086.15024
  22. [22] V. Kargin, Concentration of the spectral measure for large matrices, Electronic Communications in Probability 14 (2009), 412-421. 
  23. [23] P. Lancaster, Theory of Matrices (Academic Press, New York, 1969). Zbl0186.05301
  24. [24] T. Le and J. Sander, Extremal energies of integral circulant graphs via multiplicativity, Linear Algebra and its Applications 437 (6) (2012), 1408-1421. Zbl1243.05150
  25. [25] X. Li, Y. Shi and I. Gutman, Graph Energy (Springer, New York, 2012). 
  26. [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. 
  27. [27] B. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra and its Applications 40 (1981), 203-216. Zbl0468.05039
  28. [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. Zbl0957.15011
  29. [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. 
  30. [30] V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2) (2007), 1472-1475. Zbl1113.15016
  31. [31] V. Nikiforov, Beyond graph energy: Norms of graphs and matrices, Linear Algebra and its Applications 506 (2016), 82-138. Zbl1344.05089
  32. [32] V. Nikiforov, Remarks on the energy of regular graphs, Linear Algebra and its Applications 508 (2016), 133-145. Zbl1346.05174
  33. [33] L. Paditz, On the analytical structure of the constant in the nonuniform version of the Esseen inequality, Statistics 20 (3) (1989), 453-464. Zbl0683.60018
  34. [34] I. Pinelis, On the nonuniform Berry-Esseen bound, (2013), available at http://arxiv.org/abs/1301.2828. 
  35. [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. Zbl1104.92072
  36. [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. Zbl1217.05214
  37. [37] J. Sander and T. Sander, The maximal energy of classes of integral circulant graphs, Discrete Appl. Math. 160 (13-14) (2012), 2015-2029. Zbl1246.05099
  38. [38] A. Shiryaev, Probability, Graduate Texts in Mathematics 95 (Springer-Verlag, New York, 1996). 
  39. [39] M. Talagrand, A new look at independence, Ann. Probab. 24 (1) (1996), 1-34. Zbl0858.60019
  40. [40] G. Tee, Eigenvectors of block circulant and alternating circulant matrices, New Zealand J. Math. 36 (2007), 195-211. Zbl1186.15008
  41. [41] L. Tran, V. Vu and K. Wang, Sparse random graphs: eigenvalues and eigenvectors, Random Structures Algorithms 42 (1) (2013), 110-134. Zbl1257.05089

NotesEmbed ?

top

You must be logged in to post comments.