Mathematics 372 – Numerical Linear Algebra Selected Solutions for Problem Set 4 February 22, 2007

2.1.30. We want to show that

(1)  ∥A∥_{∞} = max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}|,

the “maximum row sum.” First we note that for any vector u with ∥u∥_{∞} = 1,

∥Au∥_{∞} = max_{1≤i≤n} |∑_{j=1}^{n} a_{ij}u_{j}|

≤ max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}||u_{j}|

≤ max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}|

(first ≤ by triangle inequality, second by ∥u∥_{∞} = 1, so |u_{j}| ≤ 1 for all j). Since this is true for all such u, we have

∥A∥_{∞} = max_{∥u∥_{∞}=1} ∥Au∥_{∞} ≤ max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}|.

To show the other inequality, consider the row number i where the maximum row sum occurs and the vector u formed as follows:

u_{j} = \{ \begin{matrix}+1 & if a_{ij} > 0 \\ −1 & if a_{ij} ≤ 0 \end{matrix}

Then

∥Au∥_{∞} = max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}|.

Hence

∥A∥_{∞} = max_{∥u∥_{∞}=1} ∥Au∥_{∞} ≥ max_{1≤i≤n} ∑_{j=1}^{n} |a_{ij}|.

Since both inequalities hold, the formula (1) is proved.

2.1.31. We have

∥x∥_{∞} = max_{1≤i≤n} |x_{i}| = max_{1≤i≤n} \sqrt{x_{i}^{2}} ≤ \sqrt{∑_{i=1}^{n} x_{i}^{2}} = ∥x∥_{2},

so the first inequality in the string holds. Next, square the 1- and 2-norms:

∥x∥_{2}^{2} = ∑_{i=1}^{n} x_{i}^{2} ≤ (∑_{i=1}^{n} |x_{i}|)^{2} = ∥x∥_{1}^{2}.

Taking square roots shows ∥x∥_{2} ≤ ∥x∥_{1}. Next, by the Cauchy-Schwarz inequality, with y_{i} = ±1 chosen similarly to what we did in 2.1.30 above, ∥y∥_{2} = \sqrt{n}, so

∥x∥_{1} = ⟨x, y⟩ ≤ ∥x∥_{2}∥y∥_{2} = \sqrt{n} · ∥x∥_{2}.

Finally,

∥x∥_{2} = \sqrt{∑_{i=1}^{n} x_{i}^{2}} ≤ \sqrt{n · max_{1≤i≤n} x_{i}^{2}} = \sqrt{n} max_{1≤i≤n} |x_{i}| = \sqrt{n}∥x∥_{∞}.

Multiplying both sides by \sqrt{n} shows

\sqrt{n}∥x∥_{2} ≤ n∥x∥_{∞}

as desired.

2.1.32. Say ∥A∥_{1} = max_{∥u∥_{1}=1} ∥Au∥_{1} is achieved for the vector u. Then by 2.3.31

∥A∥_{1} = ∥Au∥_{1} ≤ \sqrt{n}∥Au∥_{2} ≤ \sqrt{n}∥A∥_{2}∥u∥_{2} ≤ \sqrt{n}∥A∥_{2}

since by 2.3.31 again, ∥u∥_{2} ≤ ∥u∥_{1} = 1.

For the second inequality in the first part, let u be a vector with ∥u∥_{2} = 1 such that ∥A∥_{2} = ∥Au∥_{2}. Then by 2.3.31

∥A∥_{2} = ∥Au∥_{2} ≤ ∥Au∥_{1} ≤ ∥A∥_{1}∥u∥_{1} ≤ \sqrt{n}∥A∥_{1}

since ∥u∥_{1} ≤ \sqrt{n}∥u∥_{2} = \sqrt{n}. Multiply both sides by \sqrt{n} to get the desired inequality \sqrt{n}∥A∥_{2} ≤ n∥A∥_{1}.

The second part is similar. Say ∥A∥_{∞} = max_{∥u∥_{∞}=1} ∥Au∥_{∞} is achieved for the vector u. Then by 2.3.31

∥A∥_{∞} = ∥Au∥_{∞} ≤ ∥Au∥_{2} ≤ ∥A∥_{2}∥u∥_{2} ≤ \sqrt{n}∥A∥_{2}

since by 2.3.31 again, ∥u∥_{2} ≤ \sqrt{n}∥u∥_{∞} = \sqrt{n} · 1 = \sqrt{n}.

For the second inequality in the second part, let u be a vector with ∥u∥_{2} = 1 such that ∥A∥_{2} = ∥Au∥_{2}. Then by 2.3.31

∥A∥_{2} = ∥Au∥_{2} ≤ \sqrt{n}∥Au∥_{∞} ≤ \sqrt{n}∥A∥_{∞}∥u∥_{∞} ≤ \sqrt{n}∥A∥_{∞}

since ∥u∥_{∞} ≤ ∥u∥_{2} = 1. Multiply both sides by \sqrt{n} to get the desired inequality \sqrt{n}∥A∥_{2} ≤ n∥A∥_{∞}.

2.2.23 – Comment: The second part here – find a “big” perturbation of b that produces a “small” perturbation in x is not too hard if you think of the geometric picture of the intersection points of two nearly parallel lines (as in example from class, or Figure 2.1 on page 130 in the text). If you shift both lines up or down, the position of the intersection point can be close to where you started.