  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.
