Small eigenvalues can hide a large transient

STATEMENT

Disprove the claim that recurrent eigenvalues below one prevent every finite-time amplification.

GIVEN

Consider the linear state update $\vec h_t=\mat W\vec h_{t-1}$ with

Both eigenvalues are $1/2$. Use Euclidean vector norms and let $\vec e_2=(0,1)^{\mathsf T}$.

FIND

A formula for $\mat W^n$, its effect on $\vec e_2$, and why this does not contradict eventual decay or the norm bound (I.9.6).

STRATEGY

Write $\mat W=(1/2)\mat I+\mat N$. Since $\mat N^2=0$, only two terms survive in the binomial expansion.

SOLUTION

For integer $n\geq1$,

It follows that

Their norms are approximately $4.031129$ and $4.007805$, although the initial vector has norm one. At ten steps the first coordinate is $0.078125$ and the second is $0.0009765625$.

The matrix is non-normal: it does not commute with its transpose. Its eigenvalue magnitudes describe the eventual exponential rate, not a uniform bound on every finite power. The off-diagonal term introduces a factor of $n$ before the exponential decay wins. Both $2^{-n}$ and $n2^{-(n-1)}$ tend to zero, so $\mat W^n$ eventually tends to the zero matrix.

Backward propagation uses $(\mat W^n)^{\mathsf T}$. Its spectral norm equals that of $\mat W^n$, so a backward direction can be amplified too. For example, $\mat W^{\mathsf T}(1,0)^{\mathsf T}=(1/2,4)^{\mathsf T}$.

There is no conflict with (I.9.6). Indeed $\|\mat W\|_2\geq\|\mat W\vec e_2\|_2>4$. The eigenvalue $1/2$ is not a valid replacement for the factor norm in that inequality.

Check — sanity

At $n=1$ the power formula returns the supplied matrix. At $n=2$ its off-diagonal entry is four, matching direct multiplication.