Asymptotic Properties of Jordan Block 2-norm

93 Views Asked by At

Let $A = SJS^{-1}$ denote the Jordan decomposition of the matrix $A\in\mathbb{R}^{n\times n}$, where $J = \textrm{blkdiag}(J_1,\ldots,J_m)$, where each Jordan block is given by

\begin{equation*} J_i = \lambda_i I_{n_i} + N_{n_i} \in \mathbb{R}^{n_i\times n_i}, \end{equation*} with $N_{n_i}$ denoting the nilpotent matrix (i.e., $N_{n_i}^{n_i} = 0$) with ones on the superdiagonal and zeros elsewhere. I am interested in determining the asymptotic behavior of the two-norm of the Jordan matrix, that is, $\lim_{k\rightarrow\infty} \| J^k \|_{2}$.

To this end, note the binomial expansion for $J_i^k$ as

\begin{align*} J_i^k = (\lambda_i I_{n_i} + N_{n_i})^k &= \sum_{\ell = 0}^{k} \binom{k}{\ell} (\lambda_i I_{n_i})^{k-\ell} N_{n_i}^{\ell} \\ &= \sum_{\ell=0}^{k} \binom{k}{\ell} \lambda_i^{k - \ell} N_{n_i}^{\ell} \\ &= \sum_{\ell = 0}^{\min(k,n_i)} \binom{k}{\ell} \lambda_i^{k-\ell}N_{n_i}^{\ell} \\ &= \binom{k}{0}\lambda_i^k I_{n_i} + \binom{k}{1}\lambda_i^{k-1} N_{n_i} + \ldots + \binom{k}{n_{i-1}}\lambda_i^{k-n_i + 1}N_{n_i}^{n_i-1} \\ &= \begin{bmatrix} \lambda_i^k & \binom{k}{1}\lambda_i^{k-1} & \binom{k}{2}\lambda_i^{k-2} & \cdots & \cdots & \binom{k}{n_i-1}\lambda_i^{k-n_i+1} \\ & \lambda_i^k & \binom{k}{1}\lambda_i^{k-1} & \cdots & \cdots & \binom{k}{n_i-2}\lambda_i^{k-n_i+2} \\ & & \ddots & \ddots & \vdots & \vdots\\ & & & \ddots & \ddots & \vdots\\ & & & & \lambda_i^k & \binom{k}{1}\lambda_i^{k-1}\\ & & & & & \lambda_i^k \end{bmatrix} \end{align*} So, this is the structure of each Jordan block $J_i^k$. Now, the question is how to evaluate or do asymptotic analysis on $\|J^k\|_{2} := \sigma_{\textrm{max}}(J^k) = \sqrt{\rho((J^k)^\intercal J^k)}$. In the textbook Iterative Methods by Greenbaum, they write the expression \begin{equation*} \|J^k\| \sim \binom{k}{n_i-1}[\rho(J)]^{k-n_i+1}, \quad k\rightarrow\infty, \end{equation*} which (vaguely) corresponds to the upper-right element in the above expression for $J_i^k$. I am just not sure how to make the connection from $J_i^k$ to $\lim_{k\rightarrow\infty} \|J^k\|$.

1

There are 1 best solutions below

1
On BEST ANSWER

First of all, note that $J^k = \operatorname{blkdiag}(J_1^k ,\dots, J_m^k)$, so that $\|J^k\| = \max_i\|J_i^k\|$. Also, for sufficiently large $k$, $\|J_i\|$ will necessarily be greatest for an $i$ such that $|\lambda_i| = \rho(J)$ (as a consequence of the fact that $\|J_i^k\|^{1/k} \to |\lambda_i|$). Thus, it suffices to consider the case where $J = J_i$ for such an $i$. With that in mind, I will drop the $i$ subscripts from this point on; note that we will have $\rho(J) = |\lambda|$.

For convenience, write $f(k) = \binom{k}{n-1}[\rho(J)]^{k-n+1}$. In order to justify the asymptotic equivalence, we need the following two facts:

  1. $J^k$ has an entry with absolute value equal to $f(k)$ (namely the upper-right element),
  2. All other entries of $J^k$ are $o\left(f(k)\right)$ (see the end of my answer for a proof, and for explanation of what $o(\cdot)$ means if that is unfamiliar notation).

With that, let $e_n$ denote the final standard basis vector, i.e. the last column of the identity matrix. We have the following lower-bound on $\|J^k\|$: $$ \|J^k\|^2 \geq \|J^k e_n\|^2 = \sum_{j=0}^{n-1} \left|\binom{k}{j}\lambda^{k-j} \right|^2 \geq \left|\binom{k}{n-1}\lambda^{k-n+1} \right|^2 = [f(k)]^2. $$ For the upper bound, select any $0 < \epsilon < 1$. Let $\|\cdot\|_F$ denote the Frobenius norm. Let $k_0$ be such that $|[J^k]_{p,q}| \leq \frac{\epsilon}{n} f(k)$ for all $1 \leq p,q \leq n$ whenever $k > k_0$. For such $k$, we have \begin{align} \|J^k\|^2 & \leq \|J^k\|_F^2 = |[J^k]_{1,n}|^2 + \sum_{p,q; (p,q) \neq (1,n)} |[J^k]_{p,q}|^2 \\ & = f(k)^2 + \sum_{p,q; (p,q) \neq (1,n)} |[J^k]_{p,q}|^2 \\ & \leq f(k)^2 + \frac{n^2-1}{n^2} \epsilon^2 f(k)^2 \\ & \leq f(k)^2 + \epsilon^2f(k)^2 \leq f(k)^2 + \epsilon f(k)^2 = (1 + \epsilon)f(k)^2. \end{align} Thus, for any $0 < \epsilon < 1$ and sufficiently large $k$, $$ f(k)^2 \leq \|J^k\|^2 \leq (1 + \epsilon)f(k)^2. $$ Thus, for all such $\epsilon$, we have $$ 1 \leq \lim_{k \to \infty} \frac{\|J^k\|^2}{f(k)^2} \leq 1 + \epsilon, $$ and since $0 < \epsilon < 1$ was arbitrary this implies that $\lim_{k \to \infty} \frac{\|J^k\|^2}{f(k)^2} = 1$. That is, $\|J^k\|^2 \sim [f(k)]^2$, which means that $\|J^k\| \sim f(k)$.


Proof of fact 2: Every entry besides the top-right entry can be written as $\binom kj \lambda^{k-j}$ for some $j < n-1$. We note that (for $k \geq n-1$) \begin{align} \frac{\left|\binom kj \lambda^{k-j}\right|}{f(k)} &= \frac{\binom{k}{j}|\lambda|^{k-j}}{\binom{k}{n-1}|\lambda^{k-n+1}|} = |\lambda|^{n-1-j} \cdot \frac{\binom{k}{j}}{\binom{k}{n-1}} \\ & = |\lambda|^{n-1-j} \cdot \frac{k!}{j!(n-j)!} \cdot \frac{(n-1)!(k-n+1)!}{k!} \\ & = |\lambda|^{n-1-j} \cdot \frac{(n-1)!(k-n+1)!}{j!(k-j)!} \\ & = |\lambda|^{n-1-j} \frac{(j+1)(j+2)\cdots (n-1)}{(k-n+2) \cdots (k-j+1)(k-j)} \\ & = \frac{|\lambda|^{n-1-j}[(j+1)(j+2)\cdots (n-1)]}{(k-n+2) \cdots (k-j+1)(k-j)}. \end{align} We note that the final expression has a constant numerator (relative to $k$) and denominator that tends to $\infty$ as $k \to \infty$. Conclude that $\left|\binom kj \lambda^{k-j}\right|\Big/f(k) \to 0$ as $k \to \infty$, which is to say that $\left|\binom kj \lambda^{k-j}\right| = o(f(k))$.

Alternatively, fact 2 can be proved a bit more quickly if we use the fact that $\binom kj = \Theta(k^j)$, which is to say that $\binom kj \sim ck^j$ for some $c > 0$.