Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to understand a proof I have seen of the following theorem:


I understand that to do this, the idea is to show that 1) $\rho(A)\leq\|A\|$ for any norm, and then to show that, a norm exists for which, 2) $\|A\|_{\epsilon}\lt\rho(A)+\epsilon,\,\,\, \forall\, \epsilon\gt 0$, which would then indicate that, indeed, the statement in the theorem is true.

I can do the first part:
Let $V$ be a vector space. Let $x$ be an eigenvector of $A\in\mathbb{R}^{n\times n}$, with corresponding eigenvalue $\lambda$, such that $|\lambda|=\rho(A)$, where $\rho$ denotes the spectral radius. Then, by the definition of a subordinate norm, $$\|A\|=\sup_{v\in V}\frac{\|Av\|}{\|v\|}\ge\frac{\|Ax\|}{\|x\|}=\frac{|\lambda|\|x\|}{\|x\|}=|\lambda|,$$ or $$\rho(A)\le\|A\|.$$

In the next part of the proof, I can make it most of the way:
Define $$D=\begin{pmatrix} \delta&0&0&0&\cdots&0 \\ 0&\delta^2&0&0&\cdots&0 \\ 0 & 0 & \delta^3 & 0 & \cdots & 0 \\ 0 & 0 & 0 & \delta^4 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & \delta^n\end{pmatrix},$$ where $\delta>0$ is small. $D^{-1}$ exists, and it is a diagonal matrix with entries consisting of the reciprocals of the entries on the diagonal of $D$. By the Schur Decomposition theorem, we know that $A$ can be decomposed as $Q^T AQ=\Lambda+U$, where $Q$ is an orthogonal matrix, $\Lambda$ is a diagonal matrix with the eigenvalues of $A$ on the diagonal, and $U$ is a strict upper-triangular matrix. Now, investigate $$D^{-1}Q^T A Q D=D^{-1}( \Lambda +U) D=D^{-1}\Lambda D + D^{-1} U D.$$ On the right hand side, $D^{-1}\Lambda D = \Lambda,$ since these three matrices are diagonal, so $$D^{-1}Q^T A Q D = \Lambda + D^{-1}UD. $$ Now, consider $$\|D^{-1}Q^TAQD\|_\infty = \|\Lambda + D^{-1}UD\|_\infty\le\|\Lambda\|_\infty+\|D^{-1}UD\|_\infty$$ by the triangle inequality. Since $\Lambda$ has the eigenvalues of $A$ on its diagonal, I know $\|\Lambda\|_\infty=\rho(A)$. If we look at the entries of $D^{-1}UD$, we find values of $(D^{-1}UD)_{ij}=\delta^{j-i}u_{ij}$ for $j>i$, where $u_{ij}$ is the $(i,j)$-entry of $U$. The entries for $j\le i$ are $0$, since $U$ is upper triangular. Thus, we know that $\|D^{-1}UD\|_\infty\le \delta\|U\|_\infty$. The "less than" part will almost always hold, but it seems that if $u_{n-1,n}$ is huge, maybe $\|U\|_\infty=u_{n-1,n}$ (recall the $\|\cdot\|_\infty$ is the max row sum). In that case, $\|D^{-1}UD\|_\infty=\delta\|U\|_\infty$. Ignoring this for now, we have

$$\|D^{-1}Q^TAQD\|_\infty \le\|\Lambda\|_\infty+\|D^{-1}UD\|_\infty \le \rho(A) + \delta\|U\|_\infty.$$ Now, define $\delta\equiv\frac{\epsilon}{\|U\|_\infty},$ and $\|A\|_\epsilon=\|D^{-1}Q^TAQD\|_\infty$. (It can be shown that $\|A\|_\epsilon$ is a subordinate norm, but as this post is already quite long, I will skip that proof.) Then, finally, we have $$\|A\|_\epsilon\le \rho(A)+\epsilon.$$

However, this is not quite what I wanted to show, because of the $\le$ sign in the last inequality. Does anyone know how I can change this to a strict inequality? Thanks a lot.

share|cite|improve this question
up vote 4 down vote accepted

You need, for each $\epsilon > 0$ a norm $\|\cdot\|_{\epsilon}$ for which $\|A\|_{\epsilon} < \rho(A) + \epsilon$.

But what you have shown is sufficient. Indeed let $\delta > 0$.

Choose, by the above, a norm $\|\cdot\|_{\frac{\delta}{2}}$ such that $\|A\|_{\frac{\delta}{2}}\leq \rho(A) + \frac{\delta}{2}$.

But then $\|A\|_{\frac{\delta}{2}}\leq \rho(A) + \frac{\delta}{2} < \rho(A) + \delta$. So take $\|\cdot\|_{\delta}$ to be $\|\cdot\|_{\frac{\delta}{2}}$ and the claim is satisfied.

$\bf{\text{Similar Example:}}$ A sequence $(x_{n})_{n=1}^{\infty}$ in a metric space $(X,d)$ converges to $x\in X$ if for all $\epsilon > 0$ there is $N\geq 1$ such that $d(x_{n}, x)<\epsilon$ whenever $n\geq N$.

This definition does not change if we replace $< \epsilon$ with $\leq \epsilon$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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