Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Calculating norm of a matrx

  1. Sep 20, 2008 #1
    1. The problem statement, all variables and given/known data
    I am trying to show that
    (1) [tex]||A||_1 = \max_j \sum_i |a_{ij}|[/tex]
    (2) [tex]||A||_2 = \sqrt{max\_eigval\_ of\_{ } A^* A}[/tex] where A* is the conjugate transpose
    (3) [tex]||A||_\infty = \max_i \sum_i |a_{ij}|[/tex]


    2. Relevant equations
    In general,
    [tex]||A||_p = max_{x\neq 0} {{||Ax||_p}\over{||x||_p}}[/tex]
    where for a vector we have
    [tex]||x||_p = \left( \sum_i |x_i|^p \right)^{1\over p}[/tex]


    3. The attempt at a solution
    First of all, write
    [tex](Ax)_i = \sum_j a_{ij} x_j[/tex].
    (1) Here we have
    [tex]||Ax||_1 = max_{x} {{\sum_i \left|\sum_j a_{ij} x_j \right|}\over{\sum_j |x_j|}}[/tex].
    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
    [tex]||Ax||_2^2 = max_x {{x^* A^* A x}\over{x^* x}}[/tex] using [tex]||x||_2^2 =x^* x [/tex]
    Now, I read somewhere that the x that maximizes this is an eigenvector of [tex]A^* A[/tex]. So we get
    [tex]||Ax||_2^2 = \lambda_{max}[/tex], the largest eigenvalue.
    My only problem with this is: How do we know that an eigenvector will maximize it?
    (3) Here we have
    [tex]||Ax||_\infty = max_x {{max_i \left( \left| \sum_j a_{ij} x_j \right| \right)}\over{max_j (|x_j|)}}[/tex]
    using
    [tex]||x||_\infty = max_j (x_j)[/tex].
    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||.
     
    Last edited: Sep 20, 2008
  2. jcsd
  3. Sep 21, 2008 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

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

    [tex]\left| \sum_j a_{ij} x_j \right| \leq \sum_j |a_{ij}| |x_j| \leq \max_j |a_{ij}| \sum_j |x_j|.[/tex]

    Use this to conclude that [itex]\|Ax\|_1 \leq \max_j \sum_i |a_{ij}|[/itex]. 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 [itex]x=k_1 v_1+\cdots+k_n v_n[/itex], we see that (with respect to the basis B)

    [tex]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.[/tex]

    Can you take it from here?
     
  4. Sep 21, 2008 #3
    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
    [tex]x=\left(\begin{array}{c}{0 \\ 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\0 \end{array}\right)[/tex]
    where the 1 is in the max_j-th row?
     
  5. Sep 21, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Yup, that'll get you that [itex]\sum_i |a_{ij}| \leq \|Ax\|_1[/itex] for each j.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook