Page 131 - Textos de Matemática Vol. 44

AN UPPER BOUND FOR THE LARGEST EIGENVALUE OF A NONNEGATIVE SYMMETRIC MATRIX WITH ZERO DIAGONAL
JORMA K. MERIKOSKI AND ALEXANDER KOVACˇEC
Dedicated to Nat´alia Bebiano on occasion of her 60th birthday
Abstract. LetA̸=Obeanonnegativesymmetricmatrixwithzerodiagonal. We prove that its largest eigenvalue λ satisfies
λ≤ 1(−m+ m2 +4∥A∥2). 2
Here m is the smallest positive entry of A and ∥.∥ denotes the Euclidean norm. We compare the right-hand side with certain other upper bounds for λ. We also discuss briefly the case when A does not have zero diagonal.
1. Introduction
Throughout, unless otherwise stated, we let A = (aij) ̸= O be a nonneg- ative symmetric n × n matrix (n ≥ 2) with zero diagonal. (Nonnegativity is understood entrywise.) Denote by λ(A) = λ its largest eigenvalue (equal to its spectral radius, e.g., [4, Theorem 8.3.1]). Generalizing a result by Brualdi and Hoffman [3, Theorem 2.2], Stanley [8] proved that if A is a (0, 1)-matrix, then its largest eigenvalue λ(A) = λ satisfies
(1.1) λ≤ 1 −1+√1+8e , 2
where 2e is the number of ones. He also showed that equality holds if and only if e = k and
2
T Jk O A=P O O P
for some permutation matrix P. Here 2 ≤ k ≤ n and Jk is the k×k matrix with zero diagonal and ones elsewhere.
2010 Mathematics Subject Classification. 15A42, 15B48, 05C50
Key words and phrases. eigenvalues, spectral radius, nonnegative symmetric matrices
121
(1.2)