(Proposed by Ian Morris and Fedor Petrov, St. Petersburg State University)
Solution 1. Let r = ∥ A ∥ r = \|A\| r = ∥ A ∥ . We have to prove ∥ A n ∥ ≤ n ln 2 r n − 1 \|A^n\| \le \frac{n}{\ln 2}r^{n-1} ∥ A n ∥ ≤ l n 2 n r n − 1 .
As is well-known, the matrix norm satisfies ∥ X Y ∥ ≤ ∥ X ∥ ⋅ ∥ Y ∥ \|XY\| \le \|X\|\cdot\|Y\| ∥ X Y ∥ ≤ ∥ X ∥ ⋅ ∥ Y ∥ for any matrices X , Y X,Y X , Y , and as a simple consequence, ∥ A k ∥ ≤ ∥ A ∥ k = r k \|A^k\| \le \|A\|^k = r^k ∥ A k ∥ ≤ ∥ A ∥ k = r k for every positive integer k k k .
Let χ ( t ) = ( t − λ 1 ) ( t − λ 2 ) … ( t − λ n ) = t n + c 1 t n − 1 + ⋯ + c n \chi(t) = (t-\lambda_1)(t-\lambda_2)\ldots(t-\lambda_n) = t^n + c_1t^{n-1} + \cdots + c_n χ ( t ) = ( t − λ 1 ) ( t − λ 2 ) … ( t − λ n ) = t n + c 1 t n − 1 + ⋯ + c n be the characteristic polynomial of A A A . From Vieta's formulas we get
∣ c k ∣ = ∣ ∑ 1 ≤ i 1 < … < i k ≤ n λ i 1 ⋯ λ i k ∣ ≤ ∑ 1 ≤ i 1 < … < i k ≤ n ∣ λ i 1 ⋯ λ i k ∣ ≤ ( n k ) ( 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) ∣ c k ∣ = 1 ≤ i 1 < … < i k ≤ n ∑ λ i 1 ⋯ λ i k ≤ 1 ≤ i 1 < … < i k ≤ n ∑ λ i 1 ⋯ λ i k ≤ ( k n ) ( k = 1 , 2 , … , n )
By the Cayley–Hamilton theorem we have
χ ( A ) = 0 \chi(A) = 0 χ ( A ) = 0 , so
∥ A n ∥ = ∥ c 1 A n − 1 + ⋯ + c n ∥ ≤ ∑ k = 1 n ( n k ) ∥ A k ∥ ≤ ∑ k = 1 n ( n k ) r k = ( 1 + r ) n − r n . \|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. ∥ A n ∥ = ∥ c 1 A n − 1 + ⋯ + c n ∥ ≤ k = 1 ∑ n ( k n ) ∥ A k ∥ ≤ k = 1 ∑ n ( k n ) r k = ( 1 + r ) n − r n .
Combining this with the trivial estimate
∥ A n ∥ ≤ r n \|A^n\| \le r^n ∥ A n ∥ ≤ r n , we have
∥ A n ∥ ≤ min ( r n , ( 1 + r ) n − r n ) . \|A^n\| \le \min\big( r^n, (1+r)^n - r^n \big). ∥ A n ∥ ≤ min ( r n , ( 1 + r ) n − r n ) .
Let
r 0 = 1 2 n − 1 r_0 = \frac{1}{\sqrt[n]{2} - 1} r 0 = n 2 − 1 1 ; it is easy to check that the two bounds are equal if
r = r 0 r = r_0 r = r 0 , moreover
r 0 = 1 e ln 2 / n − 1 < n ln 2 . r_0 = \frac{1}{e^{\ln 2/n} - 1} < \frac{n}{\ln 2}. r 0 = e l n 2/ n − 1 1 < ln 2 n .
For
r ≤ r 0 r\le r_0 r ≤ r 0 apply the trivial bound:
∥ A n ∥ ≤ r n ≤ r 0 ⋅ r n − 1 < n ln 2 r n − 1 . \|A^n\| \le r^n \le r_0\cdot r^{n-1} < \frac{n}{\ln 2}r^{n-1}. ∥ A n ∥ ≤ r n ≤ r 0 ⋅ r n − 1 < ln 2 n r n − 1 .
For
r > r 0 r > r_0 r > r 0 we have
∥ A n ∥ ≤ ( 1 + r ) n − r n = r n − 1 ⋅ ( 1 + r ) n − r n r n − 1 . \|A^n\| \le (1+r)^n - r^n = r^{n-1}\cdot\frac{(1+r)^n - r^n}{r^{n-1}}. ∥ A n ∥ ≤ ( 1 + r ) n − r n = r n − 1 ⋅ r n − 1 ( 1 + r ) n − r n .
Notice that the function
f ( r ) = ( 1 + r ) n − r n r n − 1 f(r) = \frac{(1+r)^n - r^n}{r^{n-1}} f ( r ) = r n − 1 ( 1 + r ) n − r n is decreasing because the numerator has degree
n − 1 n-1 n − 1 and all coefficients are positive, so
( 1 + r ) n − r n r n − 1 < ( 1 + r 0 ) n − r 0 n r 0 n − 1 = r 0 ( ( 1 + 1 / r 0 ) n − 1 ) = r 0 < n ln 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}, r n − 1 ( 1 + r ) n − r n < r 0 n − 1 ( 1 + r 0 ) n − r 0 n = r 0 ( ( 1 + 1/ r 0 ) n − 1 ) = r 0 < ln 2 n ,
so
∥ A n ∥ < n ln 2 r n − 1 \|A^n\| < \frac{n}{\ln 2}r^{n-1} ∥ A n ∥ < l n 2 n r n − 1 .
Solution 2. We will use the following facts which are easy to prove:
For any square matrix A A A there exists a unitary matrix U U U such that U A U − 1 UAU^{-1} U A U − 1 is upper-triangular.
For any matrices A A A , B B B we have ∥ A ∥ ≤ ∥ ( A ∣ B ) ∥ \|A\| \le \|(A|B)\| ∥ A ∥ ≤ ∥ ( A ∣ B ) ∥ and ∥ B ∥ ≤ ∥ ( A ∣ B ) ∥ \|B\| \le \|(A|B)\| ∥ B ∥ ≤ ∥ ( A ∣ B ) ∥ where ( A ∣ B ) (A|B) ( A ∣ B ) is the matrix whose columns are the columns of A A A and the columns of B B B .
For any matrices A A A , B B B we have ∥ A ∥ ≤ ∥ ( A B ) ∥ \|A\| \le \|\left(\frac{A}{B}\right)\| ∥ A ∥ ≤ ∥ ( B A ) ∥ and ∥ B ∥ ≤ ∥ ( A B ) ∥ \|B\| \le \|\left(\frac{A}{B}\right)\| ∥ B ∥ ≤ ∥ ( B A ) ∥ where ( A B ) \left(\frac{A}{B}\right) ( B A ) is the matrix whose rows are the rows of A A A and the rows of B B 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 ∥ ≤ n ∥ A ∥ n − 1 \|A^n\| \le n\|A\|^{n-1} ∥ A n ∥ ≤ n ∥ A ∥ n − 1
for any
n × n n\times n n × n matrix
A A A whose eigenvalues have absolute value at most
1 1 1 . We proceed by induction on
n n n . The case
n = 1 n = 1 n = 1 is trivial. Without loss of generality we can assume that the matrix
A A A is upper-triangular. So we have
A = ( a 11 a 12 ⋯ a 1 n 0 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ 0 0 ⋯ a n n ) . 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}. A = a 11 0 ⋯ 0 a 12 a 22 ⋯ 0 ⋯ ⋯ ⋯ a 1 n a 2 n ⋯ a nn .
Note that the eigenvalues of
A A A are precisely the diagonal entries. We split
A A A as the sum of
3 3 3 matrices,
A = X + Y + Z A = X + Y + Z A = X + Y + Z as follows:
X = ( a 11 0 ⋯ 0 0 0 ⋯ 0 ⋯ ⋯ ⋯ 0 0 ⋯ 0 ) , Y = ( 0 a 12 ⋯ a 1 n 0 0 ⋯ 0 ⋯ ⋯ ⋯ 0 0 ⋯ 0 ) , Z = ( 0 0 ⋯ 0 0 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ 0 0 ⋯ a n n ) . 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}. X = a 11 0 ⋯ 0 0 0 ⋯ 0 ⋯ ⋯ ⋯ 0 0 ⋯ 0 , Y = 0 0 ⋯ 0 a 12 0 ⋯ 0 ⋯ ⋯ ⋯ a 1 n 0 ⋯ 0 , Z = 0 0 ⋯ 0 0 a 22 ⋯ 0 ⋯ ⋯ ⋯ 0 a 2 n ⋯ a nn .
Denote by
A ′ A' A ′ the matrix obtained from
A A A by removing the first row and the first column:
A ′ = ( a 22 ⋯ a 2 n ⋯ ⋯ 0 ⋯ a n n ) . A' = \begin{pmatrix} a_{22} & \cdots & a_{2n} \\ \cdots & & \cdots \\ 0 & \cdots & a_{nn} \end{pmatrix}. A ′ = a 22 ⋯ 0 ⋯ ⋯ a 2 n ⋯ a nn .
We have
∥ X ∥ ≤ 1 \|X\| \le 1 ∥ X ∥ ≤ 1 because
∣ a 11 ∣ ≤ 1 |a_{11}| \le 1 ∣ a 11 ∣ ≤ 1 . We also have
∥ A ′ ∥ = ∥ Z ∥ ≤ ∥ Y + Z ∥ ≤ ∥ A ∥ . \|A'\| = \|Z\| \le \|Y + Z\| \le \|A\|. ∥ A ′ ∥ = ∥ Z ∥ ≤ ∥ Y + Z ∥ ≤ ∥ A ∥.
Now we decompose
A n A^n A n as follows:
A n = X A n − 1 + ( Y + Z ) A n − 1 . A^n = XA^{n-1} + (Y+Z)A^{n-1}. A n = X A n − 1 + ( Y + Z ) A n − 1 .
We substitute
A = X + Y + Z A = X + Y + Z A = X + Y + Z in the second term and expand the parentheses. Because of the following identities:
Y 2 = 0 , Y X = 0 , Z Y = 0 , Z X = 0 Y^2 = 0, \quad YX = 0, \quad ZY = 0, \quad ZX = 0 Y 2 = 0 , Y X = 0 , Z Y = 0 , ZX = 0
only the terms
Y Z n − 1 YZ^{n-1} Y Z n − 1 and
Z n Z^n Z n survive. So we have
A n = X A n − 1 + ( Y + Z ) Z n − 1 . A^n = XA^{n-1} + (Y+Z)Z^{n-1}. A n = X A 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} ∥ A ′ n − 1 ∥ ≤ ( n − 1 ) ∥ A ′ ∥ n − 2 , hence
∥ Z n − 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} ∥ Z n − 1 ∥ ≤ ( n − 1 ) ∥ Z ∥ n − 2 ≤ ( n − 1 ) ∥ A ∥ n − 2 . Therefore
∥ A n ∥ ≤ ∥ X A n − 1 ∥ + ∥ ( Y + Z ) Z n − 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}. ∥ A n ∥ ≤ ∥ X A n − 1 ∥ + ∥ ( Y + Z ) Z n − 1 ∥ ≤ ∥ A ∥ n − 1 + ( n − 1 ) ∥ Y + Z ∥∥ A ∥ n − 2 ≤ n ∥ A ∥ n − 1 .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.