Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4603234 | Linear Algebra and its Applications | 2007 | 5 Pages |
Abstract
Write μ(A)=μ1(A)⩾⋯⩾μmin(A)μ(A)=μ1(A)⩾⋯⩾μmin(A) for the eigenvalues of a Hermitian matrix A. Our main result is:Let A be a Hermitian matrix partitioned into r×rr×r blocks so that all diagonal blocks are zero. Then for every real diagonal matrix B of the same size as Aμ(B-A)⩾μB+1r-1A.Let G be a nonempty graph, χ(G)χ(G) be its chromatic number, A be its adjacency matrix, and L be its Laplacian. The above inequality implies the well-known result of Hoffmanχ(G)⩾1+μ(A)-μmin(A),and also,χ(G)⩾1+μ(A)μ(L)-μ(A).Equality holds in the latter inequality if and only if every two color classes of G induce a ∣μmin(A)∣∣μmin(A)∣-regular subgraph.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Vladimir Nikiforov,