uniolympiads English

IMC 2002, Ημέρα 1, Θέμα 6

For an n×nn \times n matrix MM with real entries let ∥M∥=sup⁡x∈Rn∖{0}∥Mx∥2∥x∥2\|M\| = \sup_{x \in \mathbb{R}^n \setminus \{0\}} \frac{\|Mx\|_2}{\|x\|_2}, where ∥⋅∥2\|\cdot\|_2 denotes the Euclidean norm on Rn\mathbb{R}^n. Assume that an n×nn \times n matrix AA with real entries satisfies ∥Ak−Ak−1∥≤12002k\|A^k - A^{k-1}\| \le \frac{1}{2002k} for all positive integers kk. Prove that ∥Ak∥≤2002\|A^k\| \le 2002 for all positive integers kk.

Πρωτότυπο από το επίσημο PDFkM xk 2 , x∈R n \{0} kxk 2 where k · k 2 denotes the Euclidean norm on R n . Assume that an n × n matrix 1 for all positive integers k. A with real entries satisfies kA k − A k−1 k ≤ 2002k k Prove that kA k ≤ 2002 for all positive integers k. Problem 6. For an n×n matrix M with real entries let kM k = sup

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution.

Lemma 1. Let (an)n≥0(a_n)_{n\ge0} be a sequence of non-negative numbers such that a2k−a2k+1≤ak2a_{2k}-a_{2k+1}\le a_k^2,  a2k+1−a2k+2≤akak+1\ a_{2k+1}-a_{2k+2}\le a_ka_{k+1} for any k≥0k\ge0 and lim sup⁡nan<1/4\limsup na_n<1/4. Then lim sup⁡ann<1\limsup\sqrt[n]{a_n}<1.

Proof. Let cl=sup⁡n≥2l(n+1)anc_l=\sup_{n\ge2^l}(n+1)a_n for l≥0l\ge0. We will show that cl+1≤4cl2c_{l+1}\le4c_l^2. Indeed, for any integer n≥2l+1n\ge2^{l+1} there exists an integer k≥2lk\ge2^l such that n=2kn=2k or n=2k+1n=2k+1. In the first case there is a2k−a2k+1≤ak2≤cl2(k+1)2≤4cl22k+1−4cl22k+2a_{2k}-a_{2k+1}\le a_k^2\le\frac{c_l^2}{(k+1)^2}\le\frac{4c_l^2}{2k+1}-\frac{4c_l^2}{2k+2}, whereas in the second case there is a2k+1−a2k+2≤akak+1≤cl2(k+1)(k+2)≤4cl22k+2−4cl22k+3a_{2k+1}-a_{2k+2}\le a_ka_{k+1}\le\frac{c_l^2}{(k+1)(k+2)}\le\frac{4c_l^2}{2k+2}-\frac{4c_l^2}{2k+3}.

Hence a sequence (an−4cl2n+1)n≥2l+1(a_n-\frac{4c_l^2}{n+1})_{n\ge2^{l+1}} is non-decreasing and its terms are non-positive since it converges to zero. Therefore an≤4cl2n+1a_n\le\frac{4c_l^2}{n+1} for n≥2l+1n\ge2^{l+1}, meaning that cl+12≤4cl2c_{l+1}^2\le4c_l^2. This implies that a sequence ((4cl)2−l)l≥0((4c_l)^{2^{-l}})_{l\ge0} is non-increasing and therefore bounded from above by some number q∈(0,1)q\in(0,1) since all its terms except finitely many are less than 1. Hence cl≤q2lc_l\le q^{2^l} for ll large enough. For any nn between 2l2^l and 2l+12^{l+1} there is an≤cln+1≤q2l≤(q)na_n\le\frac{c_l}{n+1}\le q^{2^l}\le(\sqrt{q})^n yielding lim sup⁡ann≤q<1\limsup\sqrt[n]{a_n}\le\sqrt{q}<1, yielding lim sup⁡ann≤q<1\limsup\sqrt[n]{a_n}\le\sqrt{q}<1, which ends the proof.

Lemma 2. Let TT be a linear map from Rn\mathbb{R}^n into itself. Assume that lim sup⁡n∥Tn+1−Tn∥<1/4\limsup n\|T^{n+1}-T^n\|<1/4. Then lim sup⁡∥Tn+1−Tn∥1/n<1\limsup\|T^{n+1}-T^n\|^{1/n}<1. In particular TnT^n converges in the operator norm and TT is power bounded.

Proof. Put an=∥Tn+1−Tn∥a_n=\|T^{n+1}-T^n\|. Observe that

Tk+m+1−Tk+m=(Tk+m+2−Tk+m+1)−(Tk+1−Tk)(Tm+1−Tm)T^{k+m+1}-T^{k+m}=(T^{k+m+2}-T^{k+m+1})-(T^{k+1}-T^k)(T^{m+1}-T^m)
implying that ak+m≤ak+m+1+akama_{k+m}\le a_{k+m+1}+a_ka_m. Therefore the sequence (am)m≥0(a_m)_{m\ge0} satisfies assumptions of Lemma 1 and the assertion of Proposition 1 follows.

Remarks. 1. The theorem proved above holds in the case of an operator TT which maps a normed space XX into itself, XX does not have to be finite dimensional.

  1. The constant 1/41/4 in Lemma 1 cannot be replaced by any greater number since a sequence an=14na_n=\frac{1}{4n} satisfies the inequality ak+m−ak+m+1≤akama_{k+m}-a_{k+m+1}\le a_ka_m for any positive integers kk and mm whereas it does not have exponential decay.

  2. The constant 1/41/4 in Lemma 2 cannot be replaced by any number greater that 1/e1/e. Consider an operator (Tf)(x)=xf(x)(Tf)(x)=xf(x) on L2([0,1])L^2([0,1]). One can easily check that lim sup⁡∥Tn+1−Tn∥=1/e\limsup\|T^{n+1}-T^n\|=1/e, whereas TnT^n does not converge in the operator norm. The question whether in general lim sup⁡n∥Tn+1−Tn∥<∞\limsup n\|T^{n+1}-T^n\|<\infty implies that TT is power bounded remains open.

Remark The problem was incorrectly stated during the competition: instead of the inequality ∥Ak−Ak−1∥≤12002k\|A^k-A^{k-1}\|\le\frac{1}{2002k}, the inequality ∥Ak−Ak−1∥≤12002n\|A^k-A^{k-1}\|\le\frac{1}{2002n} was assumed. If A=(1ε01)A=\begin{pmatrix}1&\varepsilon\\0&1\end{pmatrix} then Ak=(1k ε01)A^k=\begin{pmatrix}1&k\,\varepsilon\\0&1\end{pmatrix}. Therefore Ak−Ak−1=(0ε00)A^k-A^{k-1}=\begin{pmatrix}0&\varepsilon\\0&0\end{pmatrix}, so for sufficiently small ε\varepsilon the condition is satisfied although the sequence (∥Ak∥)\left(\|A^k\|\right) is clearly unbounded.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;