Notes on Vector and Matrix Norms

1 Notes on Vector and Matrix NormsRobert A. van de GeijnDepartment of Computer ScienceThe University of Texas at AustinAustin, TX 15, 20141 Absolute ValueRecall that if C, then| |equals its absolute value. In other words, if = r+i c, then| |= 2r+ 2c= .This absolute value function has the following properties: 6= 0 | |>0 (| |is positive definite), | |=| || |(| |is homogeneous), and | + | | |+| |(| |obeys the triangle inequality).2 Vector NormsA ( Vector ) norm extends the notion of an absolute value (length or size) to vectors:Definition :Cn R. Then is a ( Vector ) norm if for allx,y Cn x6= 0 (x)>0( is positive definite), ( x) =| | (x)( is homogeneous), and (x+y) (x) + (y)( obeys the triangle inequality).

2 Exercise that if :Cn Ris a norm , then (0) = 0(where the first0denotes the zero Vector inCn).Answer:Letx Cnand~0 the zero Vector of sizenand 0 the scalar zero. Then (~0) = (0 x)0 x=~0=|0| (x) ( ) is homogeneous= 0algebraEnd of AnswerNote: often we will use to denote a Vector Vector 2- norm (length)Definition Vector 2- norm 2:Cn Ris defined by x 2= xHx= 0 0+ + n 1 n 1= | 0|2+ +| n 1| show that the Vector 2- norm is a norm , we will need the following theorem:Theorem 4.(Cauchy-Schartz inequality) Letx,y Cn. Then|xHy| x 2 y :Assume thatx6= 0 andy6= 0, since otherwise the inequality is trivially true.

3 We can then choose x=x/ x 2and y=y/ y 2. This leaves us to prove that| xH y| 1, with x 2= y 2= Cwith| |= 1 s that xH yis real and nonnegative. Note that since it is real, xH y= xH y= yH ,0 x y 22= (x y)H( x y)( z 22=zHz)= xH x yH x xH y+ yH y(multiplying out)= 1 2 xH y+| |2( x 2= y 2= 1 and xH y= xH y= yH x)= 2 2 xH y(| |= 1).Thus 1 xH yand, taking the absolute value of both sides,1 | xH y|=| || xH y|=| xH y|,which is the desired Vector 2- norm is a :To prove this, we merely check whether the three conditions are met:Letx,y Cnand Cbe arbitrarily chosen. Then x6= 0 x 2>0 ( 2is positive definite):Notice thatx6= 0 means that at least one of its components is nonzero.

4 Let s assume that j6= 0. Then x 2= | 0|2+ +| n 1|2 | j|2=| j|>0. x 2=| | x 2( 2is homogeneous): x 2= | 0|2+ +| n 1|2= | |2| 0|2+ +| |2| n 1|2= | |2(| 0|2+ +| n 1|2) =| | | 0|2+ +| n 1|2=| | x 2. x+y 2 x 2+ y 2( 2obeys the triangle inequality). x+y 22= (x+y)H(x+y)=xHx+yHx+xHy+yHy x 22+ 2 x 2 y 2+ y 22= ( x 2+ y 2) the square root of both sides yields the desired Vector 1-normDefinition Vector 1- norm 1:Cn Ris defined by x 1=| 0|+| 1|+ +| n 1|.Exercise Vector 1- norm is a :We show that the three conditions are met:Letx,y Cnand Cbe arbitrarily chosen. Then x6= 0 x 1>0 ( 1is positive definite):Notice thatx6= 0 means that at least one of its components is nonzero.

5 Let s assume that j6= 0. Then x 1=| 0|+ +| n 1| | j|>0. x 1=| | x 1( 1is homogeneous): x 1=| 0|+ +| n 1|=| || 0|+ +| || n 1|=| |(| 0|+ +| n 1|) =| |(| 0|+ +| n 1|) =| | x 1. x+y 1 x 1+ y 1( 1obeys the triangle inequality). x+y 1=| 0+ 0|+| 1+ 1|+ +| n 1+ n 1| | 0|+| 0|+| 1|+| 1|+ +| n 1|+| n 1|=| 0|+| 1|+ +| n 1|+| 0|+| 1|+ +| n 1|= x 1+ y of AnswerThe Vector 1- norm is sometimes referred to as the taxi-cab norm . It is the distance that a taxi travelsalong the streets of a city that has square Vector - norm (infinity norm )Definition Vector - norm :Cn Ris defined by x = maxi| i|.Exercise Vector - norm is a :We show that the three conditions are met:Letx,y Cnand Cbe arbitrarily chosen.

6 Then x6= 0 x >0 ( is positive definite):Notice thatx6= 0 means that at least one of its components is nonzero. Let s assume that j6= 0. Then x = maxi| i| | j|> x =| | x ( is homogeneous): x = maxi| i|= maxi| || i|=| |maxi| i|=| | x . x+y x + y ( obeys the triangle inequality). x+y = maxi| i+ i| maxi(| i|+| i|) maxi(| i|+ maxj| j|)= maxi| i|+ maxj| j|= x + y .End of Vectorp-normDefinition vectorp- norm p:Cn Ris defined by x p=p | 0|p+| 1|p+ +| n 1| that thep- norm is a norm is a little tricky and not particularly relevant to this course. To provethe triangle inequality requires the following classical result:Theorem 11.

7 (H older inequality) Letx,y Cnand1p+1q= 1with1 p,q . Then|xHy| x p y , the 1- norm and 2 Norms are special cases of thep- norm . Also, x = limp x Matrix NormsIt is not hard to see that Vector Norms are all measures of how big the vectors are. Similarly, we wantto have measures for how big matrices are. We will start with one that are somewhat artificial and thenmove on to the important class of induced Matrix Frobenius normDefinition Frobenius norm F:Cm n Ris defined by A F= m 1 i=0n 1 j=0| i,j| that one can think of the Frobenius norm as taking the columns of the Matrix , stacking them ontop of each other to create a Vector of sizem n, and then taking the Vector 2- norm of the that the Frobenius norm is a.

8 The answer is to realize that ifA=(a0a1 an 1)then A F= m 1 i=0n 1 j=0| i,j|2= n 1 j=0m 1 i=0| i,j|2= n 1 j=0 aj 22= 1 other words, it equals the Vector 2- norm of the Vector that is created by stacking the columns ofAon topof each other. The fact that the Frobenius norm is a norm then comes from realizing this connection andexploiting , just grind through the three conditions!End of AnswerSimilarly, other Matrix Norms can be created from Vector Norms by viewing the Matrix as a Vector . Itturns out that other than the Frobenius norm , these aren t particularly interesting in Induced Matrix normsDefinition :Cm Rand :Cn Rbe Vector Norms .

9 Define , :Cm n Rby A , = supx Cnx6= 0 Ax x .Let us start by interpreting this. How big Ais, as measured by A , , is defined as the most thatAmagnifies the length of nonzero vectors, where the length of the vectors (x) is measured with norm and the length of the transformed Vector (Ax) is measured with norm .Two comments are in order. First,supx Cnx6= 0 Ax x = sup x =1 Ax .This follows immediately from the fact this sequence of equivalences:supx Cnx6= 0 Ax x = supx Cnx6= 0 Ax x = supx Cnx6= 0 Ax x =supx Cnx6= 0y=x x Ay = sup y =1 Ay = sup x =1 Ax .Also the sup (which stands for supremum) is used because we can t claim yet that there is a vectorxwith x = 1 for which A , = Ax.

10 The fact is that there is always such a vectorx. The proof depends on a result from real analysis (sometimescalled advanced calculus ) that states that supx Sf(x) is attained for some vectorx Sas long asfiscontinuous andSis a compact set. Since real analysis is not a prerequisite for this course, the reader mayhave to take this on faith!We conclude that the following two definitions are equivalent definitions to the one we already gave:5 Definition :Cm Rand :Cn Rbe Vector Norms . Define , :Cm n Rby A , = maxx Cnx6= 0 Ax x .andDefinition :Cm Rand :Cn Rbe Vector Norms . Define , :Cm n Rby A , = max x =1 Ax.