Cut-norms and spectra of matrices

Details Cut-norms and spectra of matrices Cut-norms and spectra of matrices

2009-12-02

arxiv.org/abs/0912.0336v1

Mathematics

Functional Analysis

17 pages

Scientific paper

One of the aims of this paper is to solve an open problem of Lovasz about relations between graph spectra and cut-distance. The paper starts with several inequalities between two versions of the cut-norm and the two largest singular values of arbitrary complex matrices, exteding, in particular, the well-known graph-theoretical Expander Mixing Lemma and giving a hitherto unknown converse of it. Next, cut-distance is defined for Hermitian matrices, and, separately, for arbitrary complex matrices; using these extensions, we give upper bounds on the difference of corresponding eigenvalues and singular values of two matrices, thus solving the problem of Lovasz. Finally, we deduce a spectral sampling theorem, which informally states that almost all principal submatrices of a real symmetric matrix are spectrally similar to it.

Affiliated with

Also associated with

No associations

Rating

Cut-norms and spectra of matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cut-norms and spectra of matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cut-norms and spectra of matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-508294