Lecture 6: Matrix Norms and Spectral Radii

1 Lecture 6: Matrix Norms and Spectral Radii After a reminder on Norms and inner products, this Lecture introduces the notions of Matrix norm and induced Matrix norm . Then the relation between Matrix Norms and Spectral Radii is studied, culminating with Gelfand's formula for the Spectral radius. 1 Inner products and vector Norms Definition 1. Let V be a vector space over a field K (K = R or C). A function h , i : V V K. is called an inner product if (IP1 ) hx, xi 0 for all x V , with equality iff x = 0, [positivity]. (IP2 ) h x + y, zi = hx, zi + hy, zi for all , K and x, y, z V , [linearity].

2 (IP3 ) hx, yi = hy, xi for all x, y V . [Hermitian symmetry]. Observation: If K = R, then (IP3 ) simply says that hx, yi = hy, xi. This is not the case in the complex setting, where one has to be careful about complex conjugation. For instance, (IP2 ). and (IP3 ) combine to give, for all , C and x, y, z V , hx, y + zi = hx, yi + hx, zi. Observation: On V = Cn , there is the classical inner product defined by n X. (1) hx, yi := y x = xj yj , x, y Cn . j=1. On V = Mn , there is the Frobenius inner product defined by n X. X n . hA, BiF := tr (B A) = ak,` bk,` , A, B Mn.

3 K=1 `=1. Cauchy Schwarz inequality is a fundamental inequality valid in any inner product space. At this point, we state it in the following form in order to prove that any inner product generates a normed space. Theorem 2. If h , i is an inner product on a vector space V , then, for all x, y V , |hx, yi|2 hx, xihy, yi. Proof. For x, y V , choose ( , ] such that Rehei x, yi = |hx, yi|. Consider the function defined for t R by q(t) := hei x + ty, ei x + tyi = hei x, ei xi + 2tRehei x, yi + t2 hy, yi = hx, xi + 2t|hx, yi| + t2 hy, yi. 1. This is a quadratic polynomial with q(t) 0 for all t R, so its discriminant satisfies = (2|hx, yi|)2 4hx, xihy, yi 0, which directly translates into |hx, yi|2 hx, xihy, yi, as desired.)

4 The general definition of a norm is given below. A normed space is simply a vector space endowed with a norm . Definition 3. Let V be a vector space over a field K (K = R or C). A function k k : V R is called a (vector) norm if (N1 ) kxk 0 for all x V , with equality iff x = 0, [positivity]. (N2 ) k xk = | |kxk for all K and x V , [homogeneity]. (N3 ) kx + yk kxk + kyk for all x, y V . [triangle inequality]. As examples, we observe that the expression kxk := max |xj |. j [1:n]. defines a norm on Kn . The corresponding vector space is denoted as `n . The expression kxk1 := |x1 | + |x2 | + + |xn |.

5 Defines a norm on Kn . The corresponding vector space is denoted as `n1 . More generally, for p 1, the expression 1/p kxkp := |x1 |p + |x2 |p + + |xn |p . defines a norm on Kn . The corresponding vector space is denoted as `np . In the case p = 2, note that `n2 is the vector space Kn endowed with the inner product (1). Proposition 4. If V is a vector space endowed with an inner product h , i, then the expression p kxk := hx, xi defines a norm on V . Proof. The properties (N1 ) and (N2 ) are readily checked. As for (N3 ), consider x, y V , and use Theorem 2 to obtain hx + y, x + yi = hx, xi + 2 Rehx, yi + hy, yi hx, xi + 2|hx, yi| + hy, yi p p p p 2.

6 Hx, xi + 2 hx, xi hy, yi + hy, yi = hx, xi + hy, yi , p p p so that hx + y, x + yi hx, xi + hy, yi, , kx + yk kxk + kyk, as expected. 2. p Now that we know that kxk = hx, xi defines a norm on an inner product space, we can state Cauchy Schwarz inequality in the more familiar form |hx, yi| kxkkyk, x, y V. If V is a finite-dimensional space, then all Norms on V are equivalent in the following sense (in fact, this characterizes finite dimension). Theorem 5. If k k and k k0 are two Norms on a finite-dimensional vector space V , then there exist constants c, C > 0 such that ckxk kxk0 Ckxk for all x V.

7 Proof. Fixing a basis (v1 , .. , vn ) of V , we are going to show that any arbitrary norm k k0 is equivalent to the norm k k defined by n X. kxk = max |xj |, where x = xj vj . j [1:n]. j=1. On the one hand, for any x V , we have n n n n X 0 X X X. 0 0 0. kxk = xj vj kxj vj k = |xj |kvj k max |xj | kvj k0 = Ckxk, j [1:n]. j=1 j=1 j=1 j=1. where we have set C := nj=1 kvj k0 . On the other hand, let us assume that there is no c > 0. P. such that kxk (1/c)kxk0 for all x V , so that, for each integer k 1, we can find x(k) V. with kx(k) k > kkx(k) k0 . Since we can assume without loss of generality that kx(k) k = 1, we (k).

8 Have kx(k) k0 < 1/k. The sequence x1 k 1 of complex numbers is bounded, so we can extract ( (k)) ( (k)) . a subsequence x1 1 k 1. converging to some x1 C; next, the sequence x2 1 k 1. of com- ( 1 ( 2 (k))) . plex numbers is bounded, so we can extract a subsequence x2 k 1. converging to some ( (k)) ( (k)) . x2 C; etc. Setting = 1 n , we end up with subsequences x1 k 1. , .. , x n k 1. ( (k)) ( (k)). Pn ( (k)). such that xj xj for each j [1 : n]. Note that the vectors x := j=1 xj vj and k . ( (k)). x = nj=1 xj vj satisfy kx x( (k)) k = maxj [1:n] |xj xj P. | 0, therefore k.

9 Kxk0 kx x( (k)) k0 + kx( (k)) k0 Ckx x( (k)) k + 1/ (k). Taking the limit as k yields kxk0 = 0, hence x = 0, which contradicts ( (k)) ( (k)). kxk = max |xj | = max lim |xj | = lim max |xj | = lim kx( (k)) k = lim 1 = 1. j [1:n] j [1:n] k k j [1:n] k k . This proves the existence of the desired constant c > 0. 3. For instance, we can use Cauchy Schwarz inequality to derive, for any x Cn , n n n n X X hX i1/2 h X i1/2 . kxk1 = |xj | = 1 |xj | 12 |xj |2 = nkxk2 , j=1 j=1 j=1 j=1. and this inequality is best possible because it turns into an equality for x = [1, 1.]

10 , 1]> . On the other hand, for any x Cn , we have kxk2 kxk1 , since n X n hX i2. kxk22 = |xj |2 |xj | = kxk21 , j=1 j=1. and this inequality is best possible because it turns into an equality for x = [1, 0, .. , 0]> . We can more generally compare any `p - norm with any `q - norm . The proof is left as an exercise. Proposition 6. Given 1 p < q , for all x Kn , kxkq kxkp n1/p 1/q kxkq , and these inequalities are best possible. 2 Matrix Norms Since Mn is a vector space, it can be endowed with a vector norm . There is one more ingredient making this norm a Matrix norm .