Graphs and matrices with maximal energy

Given a complex m×n matrix A, we index its singular values as σ1(A) σ2(A) ··· and call the value E(A) = σ1(A)+σ2(A)+··· the energy of A, thereby extending the concept of graph energy, introduced by Gutman. Koolen and Moulton proved that E(G) (n/2)(1+√n) for any graph G of order n and exhibited an infinite family of graphs with E(G) = (v(G)/2)(1 +√v(G) ). We prove that for all sufficiently large n, there exists a graph G = G(n) with E(G) n3/2/2 − n11/10. This implies a conjecture of Koolen and Moulton. We also characterize all square nonnegative matrices and all graphs with energy close to the maximal one. In particular, such graphs are quasi-random. © 2006 Elsevier Inc. All rights reserved