uniolympiads Ελληνικά

IMC 2016, Day 2, Problem 10

Let AA be a n×nn \times n complex matrix whose eigenvalues have absolute value at most 11. Prove that

∥An∥≤nln⁡2∥A∥n−1.\|A^n\| \le \frac{n}{\ln 2} \|A\|^{n-1}.

(Here ∥B∥=sup⁡∥x∥≤1∥Bx∥\|B\| = \sup_{\|x\| \le 1} \|Bx\| for every n×nn \times n matrix BB and ∥x∥=∑i=1n∣xi∣2\|x\| = \sqrt{\sum_{i=1}^{n} |x_i|^2} for every complex vector x∈Cnx \in \mathbb{C}^n.)

Original from the official PDFLet A be a n × n complex matrix whose eigenvalues have absolute value at Problem 10. most 1 . Prove that kA n k ≤ (Here kBk = n kAk n−1 . ln 2 sup kBxk for every n × n matrix B and kxk = kxk≤1 r n P |x i | 2 for every complex i=1 vector x ∈ C n .)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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

Solution 1. Let r=∥A∥r = \|A\|. We have to prove ∥An∥≤nln⁡2rn−1\|A^n\| \le \frac{n}{\ln 2}r^{n-1}.

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

Let χ(t)=(t−λ1)(t−λ2)…(t−λn)=tn+c1tn−1+⋯+cn\chi(t) = (t-\lambda_1)(t-\lambda_2)\ldots(t-\lambda_n) = t^n + c_1t^{n-1} + \cdots + c_n be the characteristic polynomial of AA. From Vieta's formulas we get

∣ck∣=∣∑1≤i1<…<ik≤nλi1⋯λik∣≤∑1≤i1<…<ik≤n∣λi1⋯λik∣≤(nk)(k=1,2,…,n)|c_k| = \left| \sum_{1\le i_1<\ldots<i_k\le n} \lambda_{i_1}\cdots\lambda_{i_k} \right| \le \sum_{1\le i_1<\ldots<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 χ(A)=0\chi(A) = 0, so
∥An∥=∥c1An−1+⋯+cn∥≤∑k=1n(nk)∥Ak∥≤∑k=1n(nk)rk=(1+r)n−rn.\|A^n\| = \|c_1A^{n-1} + \cdots + 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 ∥An∥≤rn\|A^n\| \le r^n, we have
∥An∥≤min⁡(rn,(1+r)n−rn).\|A^n\| \le \min\big( r^n, (1+r)^n - r^n \big).
Let r0=12n−1r_0 = \frac{1}{\sqrt[n]{2} - 1}; it is easy to check that the two bounds are equal if r=r0r = r_0, moreover
r0=1eln⁡2/n−1<nln⁡2.r_0 = \frac{1}{e^{\ln 2/n} - 1} < \frac{n}{\ln 2}.
For r≤r0r\le r_0 apply the trivial bound:
∥An∥≤rn≤r0⋅rn−1<nln⁡2rn−1.\|A^n\| \le r^n \le r_0\cdot r^{n-1} < \frac{n}{\ln 2}r^{n-1}.
For r>r0r > r_0 we have
∥An∥≤(1+r)n−rn=rn−1⋅(1+r)n−rnrn−1.\|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)=(1+r)n−rnrn−1f(r) = \frac{(1+r)^n - r^n}{r^{n-1}} is decreasing because the numerator has degree n−1n-1 and all coefficients are positive, so
(1+r)n−rnrn−1<(1+r0)n−r0nr0n−1=r0((1+1/r0)n−1)=r0<nln⁡2,\frac{(1+r)^n - r^n}{r^{n-1}} < \frac{(1+r_0)^n - r_0^n}{r_0^{n-1}} = r_0\big((1+1/r_0)^n - 1\big) = r_0 < \frac{n}{\ln 2},
so ∥An∥<nln⁡2rn−1\|A^n\| < \frac{n}{\ln 2}r^{n-1}.

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

  • For any square matrix AA there exists a unitary matrix UU such that UAU−1UAU^{-1} is upper-triangular.
  • For any matrices AA, BB we have ∥A∥≤∥(A∣B)∥\|A\| \le \|(A|B)\| and ∥B∥≤∥(A∣B)∥\|B\| \le \|(A|B)\| where (A∣B)(A|B) is the matrix whose columns are the columns of AA and the columns of BB.
  • For any matrices AA, BB we have ∥A∥≤∥(AB)∥\|A\| \le \|\left(\frac{A}{B}\right)\| and ∥B∥≤∥(AB)∥\|B\| \le \|\left(\frac{A}{B}\right)\| where (AB)\left(\frac{A}{B}\right) is the matrix whose rows are the rows of AA and the rows of BB.
  • Adding a zero row or a zero column to a matrix does not change its norm.

We will prove a stronger inequality

∥An∥≤n∥A∥n−1\|A^n\| \le n\|A\|^{n-1}
for any n×nn\times n matrix AA whose eigenvalues have absolute value at most 11. We proceed by induction on nn. The case n=1n = 1 is trivial. Without loss of generality we can assume that the matrix AA is upper-triangular. So we have
A=(a11a12⋯a1n0a22⋯a2n⋯⋯⋯00⋯ann).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 AA are precisely the diagonal entries. We split AA as the sum of 33 matrices, A=X+Y+ZA = X + Y + Z as follows:
X=(a110⋯000⋯0⋯⋯⋯00⋯0),Y=(0a12⋯a1n00⋯0⋯⋯⋯00⋯0),Z=(00⋯00a22⋯a2n⋯⋯⋯00⋯ann).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′A' the matrix obtained from AA by removing the first row and the first column:
A′=(a22⋯a2n⋯⋯0⋯ann).A' = \begin{pmatrix} a_{22} & \cdots & a_{2n} \\ \cdots & & \cdots \\ 0 & \cdots & a_{nn} \end{pmatrix}.
We have ∥X∥≤1\|X\| \le 1 because ∣a11∣≤1|a_{11}| \le 1. We also have
∥A′∥=∥Z∥≤∥Y+Z∥≤∥A∥.\|A'\| = \|Z\| \le \|Y + Z\| \le \|A\|.
Now we decompose AnA^n as follows:
An=XAn−1+(Y+Z)An−1.A^n = XA^{n-1} + (Y+Z)A^{n-1}.
We substitute A=X+Y+ZA = X + Y + Z in the second term and expand the parentheses. Because of the following identities:
Y2=0,YX=0,ZY=0,ZX=0Y^2 = 0, \quad YX = 0, \quad ZY = 0, \quad ZX = 0
only the terms YZn−1YZ^{n-1} and ZnZ^n survive. So we have
An=XAn−1+(Y+Z)Zn−1.A^n = XA^{n-1} + (Y+Z)Z^{n-1}.
By the induction hypothesis we have ∥A′n−1∥≤(n−1)∥A′∥n−2\|A'^{n-1}\| \le (n-1)\|A'\|^{n-2}, hence ∥Zn−1∥≤(n−1)∥Z∥n−2≤(n−1)∥A∥n−2\|Z^{n-1}\| \le (n-1)\|Z\|^{n-2} \le (n-1)\|A\|^{n-2}. Therefore
∥An∥≤∥XAn−1∥+∥(Y+Z)Zn−1∥≤∥A∥n−1+(n−1)∥Y+Z∥∥A∥n−2≤n∥A∥n−1.\|A^n\| \le \|XA^{n-1}\| + \|(Y+Z)Z^{n-1}\| \le \|A\|^{n-1} + (n-1)\|Y+Z\|\|A\|^{n-2} \le n\|A\|^{n-1}.

Transcribed from the official solutions, pages 3–5. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?