# Determining eigenvalues and eigenvectors from a symmetric matrix

Let $A \in \mathbb{R}^{N \times N}$ be symmetric.

a) The respective Eigenvalue $\lambda$ to an approximately defined Eigenvector $0 \neq x \mathbb \in {R}^n$ from $A$ has to be calculated, so that $||Ax-\lambda x||^2_2$ is minimal. Specify a formula to calculate $\lambda$.

This is an introductory class to numerical methods. Can I use here the same formula that I have always used? Considering $Ax=\lambda x$, solving the linear system $(A-\lambda I)x=0$ should give us the (approximated) Eigenvalue $\lambda$, right? Why wouldn't $||Ax-\lambda x||^2_2$ be $0$?

$A$ has furthermore the Eigenvalues $\lambda_1 \leq \lambda_2 \leq ...\leq \lambda_n$. Show that:

b) $\lambda_1 x^T x \leq x^T Ax \leq \lambda_n x^T x$

I think I'm missing something. Can I simply use $Ax=\lambda x$? Thus $x^T Ax$ is the same as $\lambda x^T x$, as $\lambda$ can be any arbitrary Eigenvalue between the smallest ($\lambda_1$) and the largest ($\lambda_n$), it follows that $\lambda_1 x^T x \leq \lambda x^T x \leq \lambda_n x^T x$ is valid.

c) $\lambda_1 = \min_{x \neq 0} \frac{x^T Ax}{x^T x}= \min_{x^T x = 1} x^T Ax$

I'm a little lost here. I would attempt to use the same trick again, thus $\lambda_1 = \min_{x^T x = 1} x^T \lambda x = \min_{x^T x = 1} \lambda x^T x = \min_{x^T x = 1} \lambda$. However I don't think is proving what they want?

d) $\lambda_n = \max_{x \neq 0} \frac{x^T Ax}{x^T x}= \max_{x^T x = 1} x^T Ax$

Analogue to c)

Edit: Thanks to Martin I know understand better what they want.

For b) and following the tip that I can diagonalize the Matrix, I now have

Let $D=Q^T AQ$. The eigenvalues of A are in the diagonal from $D$. With $y=Q^T x$ it follows that:

$x^T Ax=x^T Q D Q^T x = y^T D y = \sum \lambda_i y_i^2$

and therefore

$\lambda_1 x^T x=\lambda_1 y^T y \leq \sum \lambda_i y_i^2 \leq \lambda_n y^T y = \lambda_n x^T x$

I think I'm very near to being able to answer c) and d) but I'm still missing something. Any help? Thanks!

-
Since $A$ is symmetric, try diagonalizing it first: there is an orthogonal matrix $Q$ which will diagonalize $A$... –  math-visitor Jun 15 '12 at 17:32
thanks for the fast reply @math-visitor. But what would I do the with the diagonal matrix from A? –  Clash Jun 15 '12 at 17:34
The diagonal matrix would contain exactly the eigenvalues. But the methods you are considered are used in numerical analysis precisely because finding $Q$ is far from easy. –  Martin Argerami Jun 15 '12 at 18:03

The point is that solving the system $A-\lambda I=0$ is usually computationally intensive. It might be easy when $A$ is $3\times3$, but there are real life applications where your matrix can be huge. That's why there are lots of numerical methods to approximate eigenvalues, and that's what they are teaching you in your class.

In a), $A$ and $x$ are given, and they want you to find the $\lambda$ that minimizes the formula; with that $\lambda$, you can test whether it really looks like an eigenvalue or not (there are different methods for this, too).

So in a) you want to minimize $$||Ax-\lambda x||^2_2=\langle Ax-\lambda x,Ax-\lambda x\rangle=\langle Ax,Ax\rangle - 2\lambda\langle Ax,x\rangle + \lambda^2\langle x,x\rangle.$$ This is a quadratic with positive degree-two coefficient, so its mininum occurs at "$-b/2a$", i.e. at $$\lambda=\frac{2\langle Ax,x\rangle}{2\langle x,x\rangle}=\frac{\langle Ax,x\rangle}{\langle x,x\rangle}.$$

Edit: for c) and d), you have already proven that $$\lambda_1 x^Tx\leq x^TAx\leq \lambda_n x^Tx,$$ so

$$\lambda_1 \leq \frac{x^TAx}{x^Tx}\leq \lambda_n.$$ You achieve the minimum by using an eigenvector for $\lambda_1$, and similarly for $\lambda_n$ and the maximum. This shows the first equality in both c) and d).

For the second equality, if $z^Tz=1$ then $$z^TAz=\frac{z^TAz}{z^Tz},$$ so $$\lambda_1\leq z^TAz\leq\lambda_n.$$ To achieve the equality, let $z$ be an eigenvector for $\lambda_1$; then put $x=z/(z^Tz)^{1/2}$. Then $$x^TAx=\frac{z^TAz}{z^Tz}=\lambda_1\,\frac{z^Tz}{z^Tz}=\lambda_1.$$ And we proceed similarly for $\lambda_n$.

-
thanks for the reply martin! I've edited my question with my answer to b), could you help me with c) and d)? thanks again! –  Clash Jun 16 '12 at 9:23
Your answer to b) is ok, and you can use the same argument to answer c) and d). –  Martin Argerami Jun 16 '12 at 14:26
Martin, I still don't see it. Could you give me a hand? I have $\lambda_1 \leq x^T Ax \leq \lambda_n$ because $x^T x=1$. We also have $x^T Ax = \sum \lambda_i y_i^2$. What am I missing? –  Clash Jun 16 '12 at 14:42
If $z$ is an arbitrary nonzero vector, then $z/(z^Tz)^{1/2}$ satisfies $z^Tz=1$. –  Martin Argerami Jun 16 '12 at 15:17
You are welcome! –  Martin Argerami Jun 16 '12 at 17:52