×

zbMATH — the first resource for mathematics

The energy of graphs and matrices. (English) Zbl 1113.15016
The author defines the energy \({\mathcal E}(A)\) of a complex rectangular matrix \(A\) as the sum of its singular values \(\sigma_1(A)\geq ...\geq \sigma_{m\wedge n}(A),\) extending hereby the concept of the energy of a graph \(G\) (defined via the adjacency matrix \(A(G)\)); see the review cited below). He shows for any nonconstant matrix \(A\) that \(\sigma_1(A)+\left(| | A| | _2^2-\sigma_1^2(A)\big/ \sigma_2(A)\right)\leq {\mathcal E}(A), \) while for a nonnegative \(m\times n\) matrix with maximum entry \(\alpha\) and \(| | A| | _1\geq n\alpha,\) there holds
\[ {\mathcal E}(A)\leq \frac{| | A| | _1}{\sqrt{mn}}+ \sqrt{(m-1)\left( | | A| | _2^2-\frac{| | A| | _1^2}{mn} \right)} \leq \alpha \frac{\sqrt{n}(m+\sqrt{n})}{2}. \]
For matrices \(A=A(G)\) this was found earlier by J. H. Koolen and V. Moulton [Adv. Appl. Math. 26, 47–52 (2001; Zbl 0976.05040)]. Using Wigner’s semicircle law he also gets for almost all graphs \(G\) that \({\mathcal E}(A(G))=\left(\frac{4\pi}{3}+o(1)\right)n^{3/2}.\)
There are no hints to that the author has consulted any of the numerous articles on estimates for subsums of eigenvalues, see e.g. J. K. Merikoski and A. Virtanen [Linear Algebra Appl. 264, 101–108 (1997; Zbl 0885.15011)], where very similar formulae can be found.

MSC:
15A42 Inequalities involving eigenvalues and eigenvectors
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Arnold, L., On the asymptotic distribution of the eigenvalues of random matrices, J. math. anal. appl., 20, 262-268, (1967) · Zbl 0246.60029
[2] Balakrishnan, R., The energy of a graph, Linear algebra appl., 387, 287-295, (2004) · Zbl 1041.05046
[3] Bollobás, B., Modern graph theory, Grad. texts in math., vol. 184, (1998), Springer-Verlag New York, xiv+394 pp · Zbl 0902.05016
[4] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs, (1980), VEB Deutscher Verlag der Wissenschaften Berlin, 368 pp · Zbl 0458.05042
[5] J. Friedman, A proof of Alon’s Second Eigenvalue Conjecture, Mem. Amer. Math. Soc., in press · Zbl 1192.05087
[6] Füredi, Z.; Komlós, J., The eigenvalues of random symmetric matrices, Combinatorica, 1, 233-241, (1981) · Zbl 0494.15010
[7] Gutman, I., The energy of a graph, Ber. math.-stat. sekt. forschungszent. Graz, 103, 1-22, (1978)
[8] Gutman, I., The energy of a graph: old and new results, (), 196-211 · Zbl 0974.05054
[9] Horn, R.; Johnson, C., Matrix analysis, (1985), Cambridge University Press Cambridge, xiii+561 pp · Zbl 0576.15001
[10] Koolen, J.H.; Moulton, V., Maximal energy graphs, Adv. appl. math., 26, 47-52, (2001) · Zbl 0976.05040
[11] Koolen, J.H.; Moulton, V., Maximal energy bipartite graphs, Graphs combin., 19, 131-135, (2003) · Zbl 1015.05043
[12] Rada, J.; Tineo, A., Upper and lower bounds for the energy of bipartite graphs, J. math. anal. appl., 289, 446-455, (2004) · Zbl 1034.05034
[13] Shparlinski, I., On the energy of some circulant graphs, Linear algebra appl., 414, 378-382, (2006) · Zbl 1083.05029
[14] Stevanović, D.; Stanković, I., Remarks on hyperenergetic circulant graphs, Linear algebra appl., 400, 345-348, (2005) · Zbl 1065.05064
[15] Wigner, E., On the distribution of the roots of certain symmetric matrices, Ann. of math., 67, 325-328, (1958) · Zbl 0085.13203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.