6
$\begingroup$

This is problem 16, Section 6.B from Linear Algebra Done Right, 3rd Edition.

Suppose the field is $\mathbb{C}$, $V$ is finite-dimensional, $T \in \mathcal{L}(V)$, all the eigenvalues of $T$ have absolute value less than 1, and $\epsilon > 0$. Show that there exists a positive integer $m$ such that $||T^m v|| < \epsilon ||v|| \; \forall \; v \in V$.

At this point in the book Jordan form has not been proved, so all I can use is Schur's Theorem that guarantees upper triangular matrix with eigenvalues on the diagonal.

Could anyone give me a hint on how to proceed ? I tried computing powers of $T$, but while I get $\lambda^m$ on diagonal and same upper triangular structure, I am unable to manage the off-diagonal entries and control their growth.

Note that in this case if matrix is split as diagonal and strictly upper diagonal matrix as $T = D + U$, $D$ and $U$ do not commute because entries on diagoals of $D$ are unequal.

$\endgroup$
  • $\begingroup$ You can always trigonalise to $T=D+N$ where $D$ is diagonal $N$ strictly upper triangular (so nilpotent), and $T$ and $D$ commute. This just requires finding generalised eigenspaces. Maybe you are not assumed to know that at this point either? $\endgroup$ – Marc van Leeuwen Mar 13 '16 at 5:50
  • $\begingroup$ @MarcvanLeeuwen: I reworded the question so that I quote verbatim from the book. It certainly does not say equal or distinct eigenvalues. No, at this point inner products, their induced norms, projections and adjoints are the only things assumed. As an aside, the decomposition you mention uses all the generalized eigenvectors as a basis ? $\endgroup$ – me10240 Mar 13 '16 at 5:53
  • $\begingroup$ If you know the formula for the spectral radius, the proof is easy. $\endgroup$ – Friedrich Philipp Mar 13 '16 at 5:55
  • $\begingroup$ @FriedrichPhilipp: Yes, I am aware that its quite simple from that point of view, but norms of linear transformations, submultiplicativity are not introduced either. My main interest in the problem was because I was curious how to prove it without using those facts. $\endgroup$ – me10240 Mar 13 '16 at 5:57
  • $\begingroup$ Another approach (certainly connected with the spectral radius formula) is to use the fact that $I - T = \sum_{n=0}^\infty T^n$. But it seems you are not allowed to use this either. $\endgroup$ – Friedrich Philipp Mar 13 '16 at 6:02
9
$\begingroup$

Here is what I had in mind when I added that exercise to the third edition of Linear Algebra Done Right:

By Schur's Theorem (which is in the same section as this exercise), there is an orthonormal basis of $V$ such that $T$ has an upper-triangular matrix $A$ with respect to that basis. Orthonormality is important so that we can compute norms. We will work with $A$ instead of $T$ and $z \in \mathbf{C}^n$ instead of $v$.

The entries on the diagonal of $A$ are the eigenvalues of $T$. Thus all the diagonal entries of $A$ have absolute value less than $1$.

If we replace each entry in $A$ with its absolute value and each coordinate of $z$ with its absolute value, then $\|A^mz\|$ gets larger or remains the same for each positive integer $m$, and $\|z\|$ remains the same. Thus we can assume without loss of generality that each entry of $A$ is nonnegative.

If we now replace each entry on the diagonal of $A$ with the largest element on the diagonal of $A$, then $\|A^mz\|$ gets larger or remains the same for each positive integer $m$. Thus we can assume without loss of generality that there exists a nonnegative number $\lambda < 1$ such that every entry of the diagonal $A$ equals $\lambda$.

We can write $$ A = \lambda I + N, $$ where $N$ is an upper-triangular matrix whose diagonal entries all equal $0$. Thus $N^n = 0$.

Let $m$ be a positive integer with $m > n$. Then

\begin{align} A^m &= (\lambda I + N)^m \\[6pt]&= \lambda^m I + m \lambda^{m-1} N + \tfrac{m(m-1)}{2} \lambda^{m-2} N^2 \\[6pt] &\quad + \tfrac{m(m-1)(m-2)}{2 \cdot 3} \lambda^{m-3} N^3 + \dots + \tfrac{m(m-1) \dotsm (m - n + 1)}{(n-1)!} \lambda^{m-n+1} N^{n-1}, \end{align}

where the other terms in the binomial expansion do not appear because $N^k = 0$ for $k \ge n$. In the expression above, the coefficients of the $n$ matrices $I$, $N$, $N^2$, $N^3$, $\dots$, $N^{n-1}$ are all bounded by $$ \frac{m^n \lambda^m}{\lambda^{n-1}}. $$ Think of $n$ and $\lambda$ as fixed. Then the limit of the expression above as $m \to \infty$ equals $0$ (because $0 \le \lambda < 1$).

Because the sum above has only a fixed number $n$ of terms, we thus see that by taking $m$ sufficiently large, we can make all the entries of the matrix $A^m$ have absolute value as small as we wish. In particular, there exists a positive integer $m$ such every entry of $A^m$ has absolute value less than $\epsilon/n$.

The definition of matrix multiplication and the Cauchy-Schwarz Inequality imply that for each $j$, the entry in row $j$, column $1$ of $Az$ has absolute value at most $\epsilon \|z\|/\sqrt{n}$. Thus $\|Az\| \le \epsilon \|z\|$, as desired.

This exercise is, in my opinion, one of the harder exercises in the third edition of Linear Algebra Done Right if one uses only the tools available at that stage of the book. The proof becomes much clearer and cleaner if one uses the tools associated with the spectral radius in a Banach algebra, which shows the power of those tools.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

I am going to suppose you are allowed to use the direct sum decomposition of the vector space into generalised eigenspaces for$~T$, which I believe is something Axler treats fairly early.

The norm of a vector cannot exceed the sum of the norms of its components along this direct sum decomposition, so it will suffice to show that each of these components becomes small for sufficiently high exponent$~m$ (giving a precise value for the exponent required is a gory detail that I won't go into).

Therefore, by restricting to one generalised eigenspace at a time, it suffices to prove the result in the case there is just a single eigenvalue$~\lambda\in\Bbb C$, which has $|\lambda|<1$. Then by definition of the generalised eigenspace for$~\lambda$, which due to our restriction is the whole space, the operator $N=T-\lambda I$ is nilpotent, say $N^n=0$. Now for a vector $v$ and any $m\geq n-1$ we have by the binomial formula ($\lambda I$ commutes): $$ T^m(v)=(\lambda I+N)^m(v)=\sum_{k=0}^m\binom mk\lambda^{m-k}N^k(v) =\lambda^{m-n+1}\sum_{k=0}^{n-1}\binom mk\lambda^{n-1-k}N^k(v) $$ since $N^k=0$ for $k\geq n$. Note the the summand has a fixed number $n$ of terms, in each of which the vector $\lambda^{n-1-k}N^k(v)$, which his independent of$~m$, is multiplied by the scalar $\binom mk$, which depends on$~m$ as a polynomial of function of degree$~k$. The exponential factor $\lambda^{m-n+1}$ before the sum has absolute value decreasing with$~m$ sufficiently rapidly to overcome this polynomial growth, and the norm of the result therefore tends to$~0$ as $m\to\infty$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Here is an answer for $\dim V = 2$. For higher dimensions the whole thing becomes more messy. Let $r < 1$ be the spectral radius of $T$ and $\lambda_1,\lambda_2$ the zeros of the characteristic polynomial of $T$, i.e., $p(t) = (t - \lambda_1)(t - \lambda_2)$. Put $p_k(t) := (t^k - \lambda_1^k)(t^k - \lambda_2^k)$. As $p$ divides $p_k$, we have $p_k(T) = 0$, that is, $$ T^{2k} = (\lambda_1^k + \lambda_2^k)T^k - (\lambda_1\lambda_2)^kI. $$ Hence, for any $v\in V$, $\|v\|=1$, $$ \|T^{2k}v\|\le 2r^k\|T^kv\| + r^{2k}. $$ From here, it is not difficult to see that $$ \|T^{2^j}v\|\le 2^jr^{2^j-1}\|Tv\| + (2^j-1)r^{2^j}. $$ Since $T$ and the norm are continuous (I hope, at least this can be used), $v\mapsto \|Tv\|$ attains its maximum on the compact set $B_V := \{v\in V : \|v\|=1\}$. Hence, $\|T^{2^j}v\|\to 0$ uniformly in $v\in B_V$.

| cite | improve this answer | |
$\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.