The control of eigenvalue

$A = ({a_{ij}})$ and $B = ({b_{ij}})$ are $n \times n$ symmetric real matrixes whose eigenvalue are ${\lambda _1} \le {\lambda _2} \le \cdots \le {\lambda _n}$ and ${\mu _1} \le {\mu _2} \le \cdots \le {\mu _n}$ respectively. If $\left| {{a_{ij}} - {b_{ij}}} \right| \le \varepsilon$, please show that $\left| {{\lambda _i} - {\mu _i}} \right| \le n\varepsilon$.

-

The max-norm of the "perturbation" matrix $P := A-B$ is given to be at most $\varepsilon$. For a square matrix, the max-norm is related to the operator norm as $$\| P \|_{\max} \leqslant \| P \|_{\mathrm{op}} \leqslant n\| P \|_{\max}.$$ Therefore, the operator norm of $P$ is at most $n \varepsilon$; i.e., all its eigenvalues of $P$ are in the interval $[-n \varepsilon, +n \varepsilon]$.
With a bound on the operator norm of $P = A-B$ at hand, Weyl's inequality in matrix theory says that the eigenvalues of $A$ and $B$ cannot be too far apart. More precisely, the inequality states that for all $i$, the difference $\lambda_i - \mu_i$ is in between the smallest and largest eigenvalue of $P$; i.e., $$- n \varepsilon \leqslant \lambda_i - \mu_i \leqslant n\varepsilon,$$ which is what we wanted to show.
A lemma may be help for the proof of Weyl's inequality: ${\lambda _{n - j}} = \mathop {\min }\limits_{{v_1}, \cdots {v_{j - 1}} \in {\mathbb R^n}} \mathop {\max }\limits_{(x,{v_1}) = \cdots = (x,{v_{j - 1}}) = 0,{\kern 1pt} {\kern 1pt} (x,x) = 1} x'Ax$ –  Hezudao Dec 2 '11 at 8:26