5
$\begingroup$

This is the problem: Let $A$ be a real symmetric $n \times n$ matrix with non negative entries. Prove that $A$ has an eigenvector with non-negative entries

I looked at the answer key and don't quite understand it. In the expression containing max, why should it correspond to the eigenvalue $\lambda_0$? I thought that this may be because if Ax is parallel to x, then the dot product between $Ax$ and $x$ is maximised, but is it not possible that it still attains a large value if $A$ transforms $x$ in a way that scales x by so much that Ax is large enough to make $\langle Ax,x\rangle$ large even though they may not be parallel?

Solution(as in answer key):

Let $\lambda_0$ be the largest eigenvalue of $A$. We have

$$\lambda_0 = \max{\{\langle Ax, x\rangle\mid x\in\mathbb{R}^n,\|x\| = 1\}}$$

and the maximum it attains precisely when $x$ is an eigenvector of $A$ with eigenvalue $\lambda_0$. Suppose $v$ is a unit vector for which the maximum is attained, and let $u$ be the vector whose coordinates are the absolute values of the coordinates of $v$. Since the entries of $A$ are nonnegative, we have

$$\langle Au,u \rangle \ge \langle Ax,x\rangle =\lambda_0$$ implying that $\langle Au,u\rangle = \lambda_0$, so that $u$ is an eigenvector of $A$ for the eigenvalue $\lambda_0$.

$\endgroup$
2
$\begingroup$

$A$ is real symmetric, so it has $n$ independent eigenvectors with real eigen-values $\lambda_1\geq \cdots \geq\lambda_n$.

Let $v_1,v_2,\cdots, v_n$ be the corresponding independent eigenvectors, and we can assume that their length is $1$ (i.e. they form orthonormal basis).

In max expression, you considered $x$ with $\|x\|=1$. Let $$x=a_1v_1+a_2v_2+\cdots + a_nv_n.$$ Then $$Ax=\lambda_1a_1v_1+\cdots + \lambda_na_nv_n.$$ Therefore, w.r.t. above orthonormal basis, noting that $\lambda_i\leq \lambda_1$, we get $$\langle Ax,x\rangle=\lambda_1|a_1|^2+\cdots + \lambda_n|a_n|^2 \leq \lambda_1 (|a_1|^2+\cdots + |a_n|^2)=\lambda_1 \langle x,x\rangle=\lambda_1\|x\|^2=\lambda_1.$$ This implies the maximum value of $\langle Ax,x\rangle$ for unit vector $x$ is $\lambda_1$. Now this is in fact attained, if you take $$x=v_1= \mbox{ unit eigenvector for the largest eigenvalue } \lambda_1. $$ You can chech this with almost same calculations as above.

$\endgroup$
1
$\begingroup$

As $A$ is real symmetric, there exists an orthonormal basis $u_0, \dots, u_{n-1}$ of $\mathbb{R}^n$ consisting of eigenvectors of $A$, say $A u_i = \lambda_i u_i$ for $1 \leq i \leq n$ and $\lambda_0 \geq \lambda_1 \geq \dots \geq \lambda_{n-1}$. Now if $x = \sum_{i = 0}^{n-1} a_i u_i$ with $\|x\| = 1$, i.e. $\sum_{i=0}^{n-1} a_i^2 = 1$, then we have $$ \langle Ax , x\rangle = \sum_{i = 0}^{n-1} \sum_{j = 0}^{n-1} \lambda_i a_i a_j \langle u_i, u_j \rangle = \sum_{i = 0}^{n-1} \lambda_i a_i^2 \leq \lambda_0 \sum_{i = 0}^{n-1} a_i^2 = \lambda_0.$$

$\endgroup$
0
$\begingroup$

By the spectral theorem, a real symmetric matrix can be diagonalized by an orthogonal matrix. So by (rigid) change of basis, $A$ is diagonal. (By rigid, we mean that the initial orthonormal basis may be rotated to the basis that makes $A$ diagonal.) Consequently, embiggening you describe (which is a valid concern in general) cannot occur.

$\endgroup$
0
$\begingroup$

If $\lambda_0=\max_{\|x\|=1}\langle Ax,x\rangle$, then, for all $x$, $$ 0 \le \langle(\lambda_0I-A)x,x\rangle. $$ Because $A$ is symmetric $\langle x,y\rangle_{\epsilon}=\langle(\lambda_0I+\epsilon I-A)x,y\rangle$ defines an inner product on your space with associated norm $\|x\|_{\epsilon}=\langle(\lambda_0I+\epsilon I-A)x,x\rangle^{1/2}$. By the Cauchy-Schwarz inequality applied to this inner product, you get $|\langle x,y\rangle_{\epsilon}|\le \|x\|_\epsilon\|y\|_\epsilon$. Letting $\epsilon\downarrow 0$ gives $$ |\langle(\lambda_0 I-A)x,y\rangle|\le |\langle(\lambda_0-I)x,x\rangle|^{1/2}|\langle(\lambda_0-I)y,y\rangle|^{1/2}. $$ Now you can see: if $\langle(\lambda_0-I)x,x\rangle=0$, then $\langle(\lambda_0I-A)x,y\rangle=0$ for all $y$, which gives $(\lambda_0I-A)x=0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.