31
$\begingroup$

How do I prove that the norm of a matrix equals the absolutely largest eigenvalue of the matrix? This is the precise question:

Let $A$ be a symmetric $n \times n$ matrix. Consider $A$ as an operator in $\mathbb{R}^n$ given by $x \mapsto Ax$. Prove that $\|A\| = \max_j |\lambda_j|$, where $\lambda_j$ are the eigenvalues of $A$.

I've read the relevant sections in my literature over and over but can't find any clue on how to begin. A solution is suggested here but the notion of diagonal operator is not in my literature so it doesn't tell me very much. So, any other hints on how to solve the question? Thanks.

$\endgroup$
1
  • $\begingroup$ It is missing here completely in the discussion (but also in the task) that it is about the 2-norm. For other induced matrix norms (lub-norms) the situation is different. $\endgroup$ – Matthias Mar 20 '20 at 17:41
30
$\begingroup$

The norm of a matrix is defined as \begin{equation} \|A\| = \sup_{\|u\| = 1} \|Au\| \end{equation} Taking the singular value decomposition of the matrix $A$, we have \begin{equation} A = VD W^T \end{equation} where $V$ and $W$ are orthonormal and $D$ is a diagonal matrix. Since $V$ and $W$ are orthonormal, we have $\|V\| = 1$ and $\|W\| = 1$. Then $\|Av\| = \|D v\|$ for any vector $v$. Then we can maximize the norm of $Av$ by maximizing the norm of $Dv$.

By the definition of singular value decomposition, $D$ will have the singular values of $A$ on its main diagonal and will have zeros everywhere else. Let $\lambda_1, \ldots, \lambda_n$ denote these diagonal entries so that

\begin{equation} D = \left(\begin{array}{cccc} \lambda_1 & 0 & \ldots & 0 \\ 0 & \lambda_2 & \ldots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \ldots & \lambda_n \end{array}\right) \end{equation}

Taking some $v = (v_1, v_2, \ldots, v_n)^T$, the product $Dv$ takes the form \begin{equation} Dv = \left(\begin{array}{c} \lambda_1v_1 \\ \vdots \\ \lambda_nv_n \end{array}\right) \end{equation} Maximizing the norm of this is the same as maximizing the norm squared. Then we are trying to maximize the sum \begin{equation} S = \sum_{i=1}^{n} \lambda_i^2v_i^2 \end{equation} under the constraint that $v$ is a unit vector (i.e., $\sum_i v_i^2 = 1$). The maximum is attained by finding the largest $\lambda_i^2$ and setting its corresponding $v_i$ to $1$ and then setting each other $v_j$ to $0$. Then the maximum of $S$ (which is the norm squared) is the square of the absolutely largest eigenvalue of $A$. Taking the square root, we get the absolutely largest eigenvalue of $A$.

$\endgroup$
5
  • 2
    $\begingroup$ @TedShifrin is it not up to me who asked the question to determine what is overkill? I asked for more details, the answer is not overkill, it's precisely what I needed. $\endgroup$ – Erik Vesterlund Dec 12 '13 at 13:50
  • $\begingroup$ @yoknapatawpha I understand your argument completely, thank you. However, I'm not able to convince myself that your choice of $x \in R^n$ yields the greatest $||Dx|||$? $\endgroup$ – Erik Vesterlund Dec 12 '13 at 16:06
  • $\begingroup$ @ErikVesterlund: My apologies for stepping on your toes. $\endgroup$ – Ted Shifrin Dec 12 '13 at 16:35
  • 2
    $\begingroup$ @ErikVesterlund If you consider $S$ just as a weighted sum (putting aside for now that these are eigenvalues of $A$ we're dealing with), then intuitively it makes sense that to maximize the weighted sum, we'd assign all of the weight to the largest element in the sum. Considering the case of a $2 \times 2$ matrix, we'd just have $\lambda_1$ and $\lambda_2$ so that $S = \lambda_1^2v_1^2 + \lambda_2^2v_2^2$. Here, if $\lambda_1 > \lambda_2$, we'd maximize $S$ by setting $v_1 = 1$ and $v_2 = 0$ (and vice-versa if $\lambda_2 > \lambda_1$). The case of higher dimensions is similar. Does this help? $\endgroup$ – yoknapatawpha Dec 12 '13 at 20:33
  • 1
    $\begingroup$ The fact that $\|W\| = 1$ and does not imply that $\|Wv\| = \|v\|$ for any vector $v$. It follows from $W$ being unitary. $\endgroup$ – user159517 Apr 18 '18 at 11:17
19
$\begingroup$

But the key point is exactly that your matrix is diagonalizable more specially that you can find an orthonormal basis of eigenvector $e_i$ for which you have $A e_i=\lambda_i e_i$.

Then your write for $x=\sum x_ie_i$ and you have $Ax=\sum x_i\lambda_i e_i$ so that $\|Ax\|^2=\sum\lambda_i^2x_i^2$ now by definition of the norm of matrix it gives you $$\frac{\|Ax\|}{\|x\|}\leq|\lambda_{i_0}|$$ therefore $\|A\|\leq|\lambda_{i_0}|$ where $\lambda_{i_0}$ is the greatest eigenvalue . Finally the identity $\|Ae_{i_0}\|=\|\lambda_{i_0}e_i\|$ gives you the inequality $\|A\|\geq|\lambda_{i_0}|$.

$\endgroup$
4
  • $\begingroup$ How do you get that $||Ax||^2 = \sum \lambda_i^2 x_i^2$? At least in my book the matrix norm is not defined, not previous to the exercise anyway so, what is it? $\endgroup$ – Erik Vesterlund Dec 11 '13 at 22:36
  • 1
    $\begingroup$ just because $(e_i)$ is an orthonormal basis, the whole question relies on the euclidean structure : the norm in $\mathbb{R}^n$ is the one defined by $\|x\|^2:=<x,x>=\sum x_i^2$. The fact that $e_i$ is orthonormal reads $<e_i,e_j>=\delta_{ij}$ which means $1$ if $i=j$ and $0$ otherwise. Now compute $\|x\|^2=<x,x>=\sum x_ix_j<e_i,e_j>=\sum x_i^2$ $\endgroup$ – user42070 Dec 11 '13 at 22:44
  • $\begingroup$ Is it correct to draw the conclusion, that when we can find an eigenbasis, then the largest singular value always equals the largest eigenvalue? $\endgroup$ – Thomas Ahle Feb 14 '17 at 6:24
  • 1
    $\begingroup$ So $x_i$ is not the elements of $x$ but its decomposition in the orthonormal basis $(e_i)$? $\endgroup$ – Ella Sharakanski Jan 27 '19 at 8:55
1
$\begingroup$

I don't have enough reputation to comment. But I'd like to fix a mistake in @yoknapatawpha's answer. The overall idea is correct.

Take the singular value decomposition of $A$ as $$A=VDW^T$$ and then we are looking for $$\max_{||u||=1}||Au||=\max_{||u||=1}||VDW^Tu||.$$

Here V and W are both orthogonal matrices. Because V is orthogonal, we have $$||VDW^Tu||=||DW^Tu||.$$ Now denote $$x=W^Tu,$$ because W is orthogonal, we have $$||x||=||W^Tu||=||u||=1$$ and also there is an one-to-one mapping between $x$ and $u$. Thus the problem is equivalent to $$\max_{||x||=1} ||Dx||$$ and the rest of the answer follows @yoknapatawpha's.

However, generally it's not right to say $\|Av\| = \|D v\|$ is true for any $v$. For example when $$V=\left[\begin{matrix}1& 0\\0 & 1\end{matrix}\right], D=\left[\begin{matrix}2& 0\\0 & 1\end{matrix}\right], W=\left[\begin{matrix}0& 1\\1 & 0\end{matrix}\right], v=\left[\begin{matrix}1\\0\end{matrix}\right]$$ in this case you can check that $||Av||=1$ but $||Dv||=2$.

$\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.