Spectral Norm and Approximation of Matrix Multiplication for a Given Matrix

(a) The spectral norm of a matrix A is equal to the square root of the largest eigenvalue of A'A. Since A is a square matrix, A'A is also a square matrix and its eigenvalues are the squares of the singular values of A. Therefore, the largest eigenvalue of A'A is (1/9)^2 = 1/81, and the spectral norm of A is the square root of 1/81, which is 1/9.

(b) We have ∥Ax − Akx∥ = ∥(A − Ak)x∥. By the triangle inequality, we know that ∥(A − Ak)x∥ ≤ ∥A − Ak∥∥x∥. Therefore, we need to find the value of k such that ∥A − Ak∥ is less than or equal to 0.2/∥x∥ = 0.2.

Note that A − Ak is a diagonal matrix with diagonal entries 0, 1 − 1/2k, 1 − 1/3k, · · · , 1 − 1/9k. Therefore, its norm is equal to the maximum absolute value of its diagonal entries, which is |1 − 1/k|. Therefore, we need to find the largest value of k such that |1 − 1/k| ≤ 0.2.

If k = 1, then |1 − 1/k| = 0, which is less than 0.2. If k > 1, then |1 − 1/k| > 0, and we can rearrange the inequality to get k > 1/(1 − 0.2) = 1.25. Therefore, the values of k that would guarantee ∥Ax − Akx∥ ≤ 0.2 are k = 2, 3, · · · , 9.