International Mathematics Competition
for University Students
2016

IMC2016: Day 2, Problem 10

10. Let $A$ be a $n\times n$ complex matrix whose eigenvalues have absolute value at most $1$. Prove that $$\|A^n\|\le \dfrac{n}{\ln 2} \|A\|^{n-1}.$$ (Here $\|B\|=\sup\limits_{\|x\|\leq 1} \|Bx\|$ for every $n\times n$ matrix $B$ and $\|x\|=\sqrt{\sum\limits_{i=1}^n |x_i|^2}$ for every complex vector $x\in\mathbb{C}^n$.)

Proposed by Ian Morris and Fedor Petrov, St. Petersburg State University

Solution 1. Let $r=\|A\|$. We have to prove $\|A^n\| \leq \frac{n}{\ln2} r^{n-1}$.

As is well-known, the matrix norm satisfies $\|XY\|\leq \|X\|\cdot \|Y\|$ for any matrices $X,Y$, and as a simple consequence, $\|A^k\|\leq \|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_1t^{n-1}+\dots+c_n$ be the characteristic polynomial of $A$. From Vieta's formulas we get $$|c_k| = \left| \sum_{1\le i_1\lt \ldots\lt i_k\le n} \lambda_{i_1}\cdots\lambda_{i_k} \right| \le \sum_{1\le i_1\lt \ldots\lt i_k\le n} \big|\lambda_{i_1}\cdots\lambda_{i_k} \big| \le \binom{n}{k} \quad (k=1,2,\ldots,n)$$ By the Cayley-Hamilton theorem we have $\chi(A)=0$, so $$\|A^n\| = \|c_1A^{n-1}+\dots+c_n\| \leq \sum_{k=1}^n \binom{n}k \|A^k\| \leq \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\| \leq \min\big( r^n, (1+r)^n-r^n) \big).$$ Let $r_0=\frac1{\sqrt[n]2-1}$; it is easy to check that the two bounds are equal if $r=r_0$, moreover $$r_0 = \frac1{e^{\ln2/n}-1} \lt \frac{n}{\ln2}.$$ For $r\leq r_0$ apply the trivial bound: $$\|A^n\| \leq r^n \leq r_0\cdot r^{n-1} \lt \frac{n}{\ln2} r^{n-1}.$$ For $r\gt r_0$ we have $$\|A^n\| \leq (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}} \lt \frac{(1+r_0)^n-r_0^n}{r_0^{n-1}} = r_0 \big((1+1/r_0)^n-1) = r_0 \lt \frac{n}{\ln2},$$ so $\|A^n\| \lt \frac{n}{\ln2} r^{n-1}$.

Solution 2. 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\|\leq\|(A|B)\|$ and $\|B\|\leq\|(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\|\leq\|\left(\frac{A}{B}\right)\|$ and $\|B\|\leq\|\left(\frac{A}{B}\right)\|$ where $\left(\frac{A}{B}\right)$ is the matrix whose rows are the rows of $A$ and the rows of $B$. \item Adding a zero row or a zero column to a matrix does not change its norm.

We will prove a stronger inequality $$\|A^n\| \leq 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\|\leq 1$ because $|a_{11}|\leq 1$. We also have $$\|A'\|=\|Z\|\leq \|Y+Z\| \leq \|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}\|\leq (n-1)\|A'\|^{n-2}$, hence $\|Z^{n-1}\|\leq (n-1)\|Z\|^{n-2}\leq (n-1)\|A\|^{n-2}$. Therefore $$\|A^n\| \leq \|X A^{n-1}\| + \|(Y+Z) Z^{n-1}\| \leq \|A\|^{n-1} + (n-1) \|Y+Z\| \|A\|^{n-2}\leq n \|A\|^{n-1}.$$