Use the result from Exercise 23 to show that if is an eigenvalue of a stochastic matrix

Determine _ _F , _ _, and _ _1 for each of the following matrices: (a) 1 0 0 1 (b) 1 4 2 2 (c) 1 2 1 2 1 2 1 2 (d) 0 5 1 2 3 1 1 2 2 (e) 5 0 5 4 1 0 3 2 1

Let A = 2 0 0 2 and x = x1 x2 and set f (x1, x2) = _Ax_2/_x_2 Determine the value of _A_2 by finding the maximum value of f for all (x1, x2) _= (0, 0).

Let A = 1 0 0 0 Use the method of Exercise 2 to determine the value of _A_2.

Let D = 3 0 0 0 0 5 0 0 0 0 2 0 0 0 0 4 (a) Compute the singular value decomposition of D. (b) Find the value of _D_2.

Show that if D is an n n diagonal matrix, then _D_2 = max 1in (|dii |)

If D is an n n diagonal matrix, how do the values of _D_1, _D_2, and _D_ compare? Explain your answers.

Let I denote the n n identity matrix. Determine the values of _I _1, _I _, and _I _F .

Let _ _M denote a matrix norm on Rnn, _ _V denote a vector norm on Rn, and I be the n n identity matrix. Show that (a) If _ _M and _ _V are compatible, then _I _M 1. (b) If __M is subordinate to __V , then _I _M = 1.

A vector x in Rn can also be viewed as an n 1 matrix X: x = X = x1 x2 ... xn (a) How do the matrix norm _X_ and the vector norm _x_ compare? Explain. (b) How do the matrix norm _X_1 and the vector norm _x_1 compare? Explain. 1

A vector y in Rn can also be viewed as an n 1 matrix Y = (y). Show that (a) _Y _2 = _y_2 (b) _Y T _2 = _y_2 1

Let A = wyT , where w Rm and y Rn. Show that (a) _Ax_2 _x_2 _y_2_w_2 for all x _= 0 in Rn. (b) _A_2 = _y_2_w_2 1

Let A = 3 1 2 1 2 7 4 1 4 (a) Determine _A_. (b) Find a vector x whose coordinates are each 1 such that _Ax_ = _A_. (Note that _x_ = 1, so _A_ = _Ax_/_x_.) 1

Theorem 7.4.2 states that _A_ = max 1im _n j=1 |ai j | Prove this in two steps. (a) Show first that _A_ max 1im _n j=1 |ai j | (b) Construct a vector x whose coordinates are each 1 such that _Ax_ _x_ = _Ax_ = max 1im _n j=1 |ai j | 1

Show that _A_F = _AT _F . 1

Let A be a symmetric n n matrix. Show that _A_ = _A_1. 1

Let A be a 5 4 matrix with singular values 1 = 5, 2 = 3, and 3 = 4 = 1. Determine the values of _A_2 and _A_F . 1

Let A be an m n matrix. (a) Show that _A_2 _A_F . (b) Under what circumstances will _A_2 = _A_F ? 1

Let _ _ denote the family of vector norms and let _ _M be a subordinate matrix norm. Show that _A_M = max _x_=1 _Ax_ 1

Let A be an m n matrix and let _ _v and _ _w be vector norms on Rn and Rm, respectively. Show that _A_v,w = max x_=0 _Ax_w _x_v defines a matrix norm on Rmn. 2

Let A be an m n matrix. The 1,2-norm of A is given by _A_1,2 = max x_=0 _Ax_2 _x_1 (See Exercise 19.) Show that _A_1,2 = max (_a1_2, _a2_2, . . . , _an_2) 2

Let A be an m n matrix. Show that _A_1,2 _A_2 2

Let A be an m n matrix and let B Rnr . Show that (a) _Ax_ _A_1,2_x_1 for all x in Rn. (b) _AB_1,2 _A_2_B_1,2 2

Let A be an n n matrix and let _ _M be a matrix norm that is compatible with some vector norm on Rn. Show that if is an eigenvalue of A, then || _A_M. 2

Use the result from Exercise 23 to show that if is an eigenvalue of a stochastic matrix, then || 1. 2

Sudoku is a popular puzzle involving matrices. In this puzzle, one is given some of the entries of a 9 9 matrix A and asked to fill in the missing entries. The matrix A has block structure A = A11 A12 A13 A21 A22 A23 A31 A32 A33 where each submatrix Ai j is 3 3. The rules of the puzzle are that each row, each column, and each of the submatrices of A must be made up of all of the integers 1 through 9. We will refer to such a matrix as a sudoku matrix. Show that if A is a sudoku matrix, then = 45 is its dominant eigenvalue. 2

Let Ai j be a submatrix of a sudoku matrix A (see Exercise 25). Show that if is an eigenvalue of Ai j , then || 22. 2

Let A be an n n matrix and x Rn. Prove: (a) _Ax_ n1/2_A_2_x_ (b) _Ax_2 n1/2_A__x_2 (c) n1/2_A_2 _A_ n1/2_A_2 2

Let A be a symmetric n n matrix with eigenvalues 1, . . . , n and orthonormal eigenvectors u1, . . . , un. Let x Rn and let ci = uT i x for i = 1, 2, . . . , n. Show that (a) _Ax_22 = _n i=1 (i ci )2 (b) If x _= 0, then min 1in |i| _Ax_2 _x_2 max 1in |i (c) _A_2 = max 1in |i | 2

Let A = 1 0.99 1 1 Find A1 and cond(A). 3

Solve the given two systems and compare the solutions. Are the coefficient matrices well conditioned? Ill conditioned? Explain. 1.0x1 + 2.0x2 = 1.12 2.0x1 + 3.9x2 = 2.16 1.000x1 + 2.011x2 = 1.120 2.000x1 + 3.982x2 = 2.160 3

Let A = 1 0 1 2 2 3 1 1 2 Calculate cond(A) = _A__A1_. 3

Let A be a nonsingular n n matrix, and let _ _M denote a matrix norm that is compatible with some vector norm on Rn. Show that condM(A) 1 3

Let An = 1 1 1 1 1 n for each positive integer n. Calculate (a) A1 n (b) cond(An) (c) lim n cond(An) 3

If A is a 53 matrix with _A_2 = 8, cond2(A) = 2, and _A_F = 12, determine the singular values of A. 3

Let A = 3 2 1 1 and b = 5 2 The solution computed using two-digit decimal floating-point arithmetic is x = (1.1, 0.88)T . (a) Determine the residual vector r and the value of the relative residual _r_/_b_. (b) Find the value of cond(A). (c) Without computing the exact solution, use the results from parts (a) and (b) to obtain bounds for the relative error in the computed solution. (d) Compute the exact solution x and determine the actual relative error. Compare your results with the bounds derived in part (c). 3

Let A = 0.50 0.75 0.25 0.50 0.25 0.25 1.00 0.50 0.50 Calculate cond1(A) = _A_1_A1_1. 3

Let A be the matrix in Exercise 36 and let A_ = 0.5 0.8 0.3 0.5 0.3 0.3 1.0 0.5 0.5 Let x and x_ be the solutions of Ax = b and A_x = b, respectively, for some b R3. Find a bound for the relative error (_x x__1)/_x__1. 3

Let A = 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 , b = 5.00 1.02 1.04 1.10 An approximate solution of Ax = b is calculated by rounding the entries of b to the nearest integer and then solving the rounded system with integer arithmetic. The calculated solution is x_ = (12, 4, 2, 1)T . Let r denote the residual vector. (a) Determine the values of _r_ and cond(A). (b) Use your answer to part (a) to find an upper bound for the relative error in the solution. (c) Compute the exact solution x and determine the relative error _x x__ _x_ . 3

Let A and B be nonsingular n n matrices. Show that cond(AB) cond(A) cond(B) 4

Let D be a nonsingular n n diagonal matrix and let dmax = max 1in |dii | and dmin = min 1in |dii | (a) Show that cond1(D) = cond(D) = dmax dmin (b) Show that cond2(D) = dmax dmin 4

Let Q be an n n orthogonal matrix. Show that (a) _Q_2 = 1 (b) cond2(Q) = 1 (c) for any b Rn, the relative error in the solution of Qx = b is equal to the relative residual; that is, _e_2 _x_2 = _r_2 _b_2 4

Let A be an n n matrix and let Q and V be n n orthogonal matrices. Show that (a) _QA_2 = _A_2 (b) _AV_2 = _A_2 (c) _QAV_2 = _A_2 4

Let A be an m n matrix and let 1 be the largest singular value of A. Show that if x and y are nonzero vectors in Rn, then each of the following holds: (a) |xT Ay| _x_2 _y_2 1 [Hint: Make use of the CauchySchwarz inequality.] (b) max x_=0, y_=0 |xT Ay| _x_ _y_ = 1 4

Let A be an m n matrix with singular value decomposition U_V T . Show that min x_=0 _Ax_2 _x_2 = n 4

Let A be an m n matrix with singular value decomposition U_V T . Show that, for any vector x Rn, n_x_2 _Ax_2 1_x_2 4

Let A be a nonsingular n n matrix and let Q be an n n orthogonal matrix. Show that (a) cond2(QA) = cond2(AQ) = cond2(A) (b) if B = QTAQ, then cond2(B) = cond2(A). 4

Let A be a symmetric nonsingular nn matrix with eigenvalues 1, . . . , n. Show that cond2(A) = max 1in |i | min 1in |i