Numerical radius and zero pattern of matrices

Let A be an n × n complex matrix and r be the maximum size of its principal submatrices with no off-diagonal zero entries. Suppose A has zero main diagonal and x is a unit n-vector. Then, letting A be the Frobenius norm of A, we show that Ax, x 2 (1−1/2r −1/2n) A 2. This inequality is tight within an additive term O(rn−2). If the matrix A is Hermitian, then Ax, x 2 (1−1/r) A 2. This inequality is sharp; moreover, it implies the Turán theorem for graphs. © 2007 Elsevier Inc. All rights reserved.