Maximizing Norms of Matrices: A Scientific Approach

[Pacopag]

Homework Statement

I am trying to show that
(1) $$||A||_1 = \max_j \sum_i |a_{ij}|$$
(2) $$||A||_2 = \sqrt{max\_eigval\_ of\_{ } A^* A}$$ where A* is the conjugate transpose
(3) $$||A||_\infty = \max_i \sum_i |a_{ij}|$$

Homework Equations

In general,
$$||A||_p = max_{x\neq 0} {{||Ax||_p}\over{||x||_p}}$$
where for a vector we have
$$||x||_p = \left( \sum_i |x_i|^p \right)^{1\over p}$$

The Attempt at a Solution

First of all, write
$$(Ax)_i = \sum_j a_{ij} x_j$$.
(1) Here we have
$$||Ax||_1 = max_{x} {{\sum_i \left|\sum_j a_{ij} x_j \right|}\over{\sum_j |x_j|}}$$.
I'm pretty sure we could switch the summation order in the numerator too. But I don't know how to proceed from here.
(2) Here we have
$$||Ax||_2^2 = max_x {{x^* A^* A x}\over{x^* x}}$$ using $$||x||_2^2 =x^* x$$
Now, I read somewhere that the x that maximizes this is an eigenvector of $$A^* A$$. So we get
$$||Ax||_2^2 = \lambda_{max}$$, the largest eigenvalue.
My only problem with this is: How do we know that an eigenvector will maximize it?
(3) Here we have
$$||Ax||_\infty = max_x {{max_i \left( \left| \sum_j a_{ij} x_j \right| \right)}\over{max_j (|x_j|)}}$$
using
$$||x||_\infty = max_j (x_j)$$.
Again, I don't know how to proceed from here. It seems that in order to arrive at the answer (which I like to pretend that I don't know),
I would need to choose x to be a vector where all the components are the same. Then the x_j's would cancel and i get the right answer.
But I don't see why such an x is guaranteed to maximize ||A||.

 

[morphism]

For (1), note that, for a fixed i,

$$\left| \sum_j a_{ij} x_j \right| \leq \sum_j |a_{ij}| |x_j| \leq \max_j |a_{ij}| \sum_j |x_j|.$$

Use this to conclude that $\|Ax\|_1 \leq \max_j \sum_i |a_{ij}|$. Can you find unit vectors to help guarantee that equality is achieved?

A similar technique can be applied to (3).

As for (2), note that A*A is Hermitian, so we can unitarily diagonalize it. Let B={v_1, ..., v_n} be an orthonormal basis for C^n consisting of eigenvectors of A*A. Writing $x=k_1 v_1+\cdots+k_n v_n$, we see that (with respect to the basis B)

$$x^*A^*Ax = (k_1^*, \ldots, k_n^*) \left(\begin{array}{cccc} \lambda_1 \\ & \lambda 2 \\ & & \ddots \\ & & & \lambda_n \end{array}\right) \left(\begin{array}{c}{k_1 \\ \vdots \\ k_n \end{array}\right) = \sum_j \lambda_j |k_j|^2.$$

Can you take it from here?

 

[Pacopag]

Yes! That is a tremendous help. Thank you very much.
Is the answer to your question "Can you find unit vectors to help guarantee that equality is achieved?" a vector
$$x=\left(\begin{array}{c}{0 \\ 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\0 \end{array}\right)$$
where the 1 is in the max_j-th row?

 

[morphism]

Yup, that'll get you that $\sum_i |a_{ij}| \leq \|Ax\|_1$ for each j.