IMC 2016 · Day 2 · P10

Let $r = \|A\|$. We have to prove $\|A^n\| \le \frac{n}{\ln 2} r^{n-1}$.

As is well-known, the matrix norm satisfies $\|XY\| \le \|X\| \cdot \|Y\|$ for any matrices $X, Y$, and as a simple consequence, $\|A^k\| \le \|A\|^k = r^k$ for every positive integer $k$.

Let $\chi(t) = (t - \lambda_1)(t - \lambda_2) \dots (t - \lambda_n) = t^n + c_1 t^{n-1} + \dots + c_n$ be the characteristic polynomial of $A$. From Vieta's formulas we get $$|c_k| = \Bigl| \sum_{1 \le i_1 < \dots < i_k \le n} \lambda_{i_1} \cdots \lambda_{i_k} \Bigr| \le \sum_{1 \le i_1 < \dots < i_k \le n} \bigl| \lambda_{i_1} \cdots \lambda_{i_k} \bigr| \le \binom{n}{k} \qquad (k = 1, 2, \dots, n)$$ By the Cayley–Hamilton theorem we have $\chi(A) = 0$, so $$\|A^n\| = \|c_1 A^{n-1} + \dots + c_n\| \le \sum_{k=1}^{n} \binom{n}{k} \|A^k\| \le \sum_{k=1}^{n} \binom{n}{k} r^k = (1+r)^n - r^n.$$ Combining this with the trivial estimate $\|A^n\| \le r^n$, we have $$\|A^n\| \le \min\bigl( r^n, (1+r)^n - r^n) \bigr).$$ Let $r_0 = \frac{1}{\sqrt[n]{2} - 1}$; it is easy to check that the two bounds are equal if $r = r_0$, moreover $$r_0 = \frac{1}{e^{\ln 2 / n} - 1} < \frac{n}{\ln 2}.$$ For $r \le r_0$ apply the trivial bound: $$\|A^n\| \le r^n \le r_0 \cdot r^{n-1} < \frac{n}{\ln 2} r^{n-1}.$$ For $r > r_0$ we have $$\|A^n\| \le (1+r)^n - r^n = r^{n-1} \cdot \frac{(1+r)^n - r^n}{r^{n-1}}.$$ Notice that the function $f(r) = \frac{(1+r)^n - r^n}{r^{n-1}}$ is decreasing because the numerator has degree $n - 1$ and all coefficients are positive, so $$\frac{(1+r)^n - r^n}{r^{n-1}} < \frac{(1+r_0)^n - r_0^n}{r_0^{n-1}} = r_0 \bigl( (1 + 1/r_0)^n - 1) = r_0 < \frac{n}{\ln 2},$$ so $\|A^n\| < \frac{n}{\ln 2} r^{n-1}$.

We will use the following facts which are easy to prove:

• For any square matrix $A$ there exists a unitary matrix $U$ such that $U A U^{-1}$ is upper-triangular.
• For any matrices $A$, $B$ we have $\|A\| \le \|(A|B)\|$ and $\|B\| \le \|(A|B)\|$ where $(A|B)$ is the matrix whose columns are the columns of $A$ and the columns of $B$.
• For any matrices $A$, $B$ we have $\|A\| \le \bigl\| \bigl( \begin{smallmatrix} A \\ B \end{smallmatrix} \bigr) \bigr\|$ and $\|B\| \le \bigl\| \bigl( \begin{smallmatrix} A \\ B \end{smallmatrix} \bigr) \bigr\|$ where $\bigl( \begin{smallmatrix} A \\ B \end{smallmatrix} \bigr)$ is the matrix whose rows are the rows of $A$ and the rows of $B$.
• Adding a zero row or a zero column to a matrix does not change its norm.

We will prove a stronger inequality $$\|A^n\| \le n \|A\|^{n-1}$$ for any $n \times n$ matrix $A$ whose eigenvalues have absolute value at most 1. We proceed by induction on $n$. The case $n = 1$ is trivial. Without loss of generality we can assume that the matrix $A$ is upper-triangular. So we have $$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ 0 & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & a_{nn} \end{pmatrix}.$$ Note that the eigenvalues of $A$ are precisely the diagonal entries. We split $A$ as the sum of 3 matrices, $A = X + Y + Z$ as follows: $$X = \begin{pmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & 0 \end{pmatrix}, \quad Y = \begin{pmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & 0 \\ \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} 0 & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & a_{nn} \end{pmatrix}.$$ Denote by $A'$ the matrix obtained from $A$ by removing the first row and the first column: $$A' = \begin{pmatrix} a_{22} & \cdots & a_{2n} \\ \cdots & \cdots \\ 0 & \cdots & a_{nn} \end{pmatrix}.$$ We have $\|X\| \le 1$ because $|a_{11}| \le 1$. We also have $$\|A'\| = \|Z\| \le \|Y + Z\| \le \|A\|.$$ Now we decompose $A^n$ as follows: $$A^n = X A^{n-1} + (Y + Z) A^{n-1}.$$ We substitute $A = X + Y + Z$ in the second term and expand the parentheses. Because of the following identities: $$Y^2 = 0, \quad YX = 0, \quad ZY = 0, \quad ZX = 0$$ only the terms $Y Z^{n-1}$ and $Z^n$ survive. So we have $$A^n = X A^{n-1} + (Y + Z) Z^{n-1}.$$ By the induction hypothesis we have $\|A'^{n-1}\| \le (n-1) \|A'\|^{n-2}$, hence $\|Z^{n-1}\| \le (n-1) \|Z\|^{n-2} \le (n-1) \|A\|^{n-2}$. Therefore $$\|A^n\| \le \|X A^{n-1}\| + \|(Y + Z) Z^{n-1}\| \le \|A\|^{n-1} + (n-1) \|Y + Z\| \|A\|^{n-2} \le n \|A\|^{n-1}.$$