# Is this proof of an $\infty$ norm valid?

1. Jan 26, 2016

### pyroknife

I am trying to prove
$||A||_{\infty} = max_i \sum_{j} |a_{ij}|$
which reads as the $\infty$ norm is the max row sum of matrix A.
$i$ is the row index and $j$ is the column index.

Here is what I thought of:

$||A||_{\infty} = sup_{x\neq 0} \frac{||Ax||_{\infty}}{||x||_{\infty}}$
The numerator can be written as:
$||Ax||_{\infty} = max_i \sum_{j} |a_{ij} x_j| \leq max_i \sum_{j} |a_{ij}|\ |x_j| \leq max_j |x_j| * max_i \sum_{j} |a_{ij}| = ||x||_{\infty} * max_i \sum_{j} |a_{ij}|$
Therefore,
$||Ax||_{\infty} \leq ||x||_{\infty} * max_i \sum_{j} |a_{ij}|$
Next,
$\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq max_i \sum_{j} |a_{ij}|$
Next,
the supremum is defined as the "least upper bound." Thus, the supremum of the above expression is simply the equal sign. Thus,
$||A||_{\infty} = max_i \sum_{j} |a_{ij}|$

Do you guys see any flaws in this proof? I saw various other proofs that went on to prove that the "<" condition cannot exist, which is still correct, but I don't understand what the point is when you know that the supremum is the "LEAST" upper bound.

2. Jan 26, 2016

### andrewkirk

The first equality is incorrect. However, it's fixable. Replace
$$||Ax||_{\infty} = max_i \sum_{j} |a_{ij} x_j|$$
by
$$||Ax||_{\infty} = max_i \left\vert \sum_{j} a_{ij} x_j\right\vert\leq max_i \sum_{j} |a_{ij} x_j|$$
I haven't looked through the rest yet. Will do that a bit later, but have to run off now.

3. Jan 26, 2016

### pyroknife

Ah yes! Thanks. that is a typo, but the rest of the proof did not carry over that typo.

4. Jan 26, 2016

### andrewkirk

That is correct.
I'm afraid that doesn't make sense. A supremum is a number. An equals sign is not. Nor can I see any way of interpreting this statement to make it both meaningful and correct.

What you have proven (it needs a couple more steps added in, but you're close enough) is that
$$||A||_{\infty} \leq max_i \sum_{j} |a_{ij}|$$
Now you need to prove that
$$||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$

Hint, use the definition of the infinity norm, and consider only vectors $x$ of norm 1. What's the biggest value of $\|Ax\|_\infty$ you can get given that $x$ has norm 1?

5. Jan 26, 2016

### pyroknife

This is the part where I got stuck on.

I am not sure if it was the way I worded it, but I mean to say the supremum is the condition given by the equal sign, since it would be the "lowest" "upper" bound. Does that still not make sense?

$x\leq y$
sup(x) = y

so carried over to the current problem, wouldn't that make it the condition given by the equal sign?

6. Jan 26, 2016

### pyroknife

i.e., $sup_{x\neq 0} \frac{||Ax||_{\infty}}{||x||_{\infty}} = max_i \sum_{j} |a_{ij}|$

since we know the least upper bound of $\frac{||Ax||_{\infty}}{||x||_{\infty}}$ is $max_i \sum_{j} |a_{ij}|$

7. Jan 27, 2016

### andrewkirk

Since we know $||A||_{\infty}$ is an upper bound for $\frac{||Ax||_{\infty}}{||x||_{\infty}}$, to prove it's a least upper bound, all that's needed is to find a vector $x$ for which $||A||_{\infty}=\frac{||Ax||_{\infty}}{||x||_{\infty}}$.

This is equivalent to finding a vector $x$ with unit infinity-norm, such that $||A||_{\infty}=||Ax||_{\infty}$.
Can you think of such a unit vector? Since you want to make the vector as 'big' as possible, what's the 'biggest' vector you can think of that has unit infinity-norm (start by thinking of 'big' as meaning the size of the usual norm on $\mathbb{R}^n$).

8. Jan 27, 2016

### pyroknife

Thank you. I think I know what I was missing. I basically used the end result to arrive st the end result which doesn't make much sense, since I am to prove the end result.

Are you saying x has to be a unit vector with an infinity norm equal to 1?
If so wouldn't that just be a vector with all zero elements except for one element which is 1?

9. Jan 27, 2016

### andrewkirk

'UNit vector' just means a vector with norm equal to 1. Since all the norms being used here are infinity norms, that means a vector $x$ such that $\|x\|_\infty=1$, which in turn means a vector for which the largest absolute value of any of its components is 1. For example, if $n=3$, then (1 0 0), (1 1 0), (0 1 0), (0 -1 1), (1 1 1), (1 -1 1), (0.5 0 1), (0.5 -0.5 -1) are all unit vectors.

What I'm suggesting in my post is that you consider which of the vectors like this have the largest 2-norm, where the 2-norm of vector $x$ is the 'usual' (not infinity) norm calculation $\|x\|_2\equiv\left(\sum_{k=1}^n x_k{}^2\right)^\tfrac{1}{2}$.

10. Jan 27, 2016

### pyroknife

Oh I see.
Largest 2-norm would be (1,1,1), (-1, -1, -1), and so on.

So $||x||_{\infty} = 1$
and
$||Ax||_{\infty} = max_i |\sum_{j} a_{ij}|$

is this the idea?

11. Jan 27, 2016

### andrewkirk

Yes, that's it!

12. Jan 27, 2016

### pyroknife

Thanks. Dumb question, but I am not seeing how this proves the infinite norm of a matrix.
I just showed $||Ax||_{\infty} = max_i |\sum_j a_{ij}|$
but I am unsure how this relates to
$||A_{\infty}||$

I think I'm missing a simple connection here.

13. Jan 27, 2016

### pyroknife

In particular, I am not understanding why we looked for a vector with a unit infinity norm that maximizes the 2-norm.

14. Jan 27, 2016

### pyroknife

I am not understanding why we looked for a vector with a unit infinity norm that maximizes the 2-norm.

15. Jan 27, 2016

### andrewkirk

Above it was shown that, for all vectors $x$, we have
$$\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq \max_i \sum_{j} |a_{ij}|$$
So $\max_i \sum_{j} |a_{ij}|$ is an upper bound for $\frac{||Ax||_{\infty}}{||x||_{\infty}}$ over $x$.
You have just identified a value of $x$, namely $x'\equiv (1 1 1)$, for which $\frac{||Ax'||_{\infty}}{||x'||_{\infty}} = \max_i \sum_{j} |a_{ij}|$.

What does that tell you about whether there can be an upper bound $u$ for $\frac{||Ax||_{\infty}}{||x||_{\infty}}$ that is less than $\max_i \sum_{j} |a_{ij}|$?

And what does that then tell you about what sort of an upper bound $\max_i \sum_{j} |a_{ij}|$ is?

16. Jan 27, 2016

### pyroknife

So I'm thinking, what if we have:
$A = \begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix}$

and $x = \begin{bmatrix} 1\\ 0 \end{bmatrix}$

We can see that $||Ax||_{\infty} = 1$ and $||x||_{\infty} = 1$
thus $\frac{||Ax||_{\infty}}{||x||_{\infty}}= 1$
but
$\max_i \sum_{j} |a_{ij}| = 2$
so the equality doesn't hold?

$\max_i \sum_{j} |a_{ij}|$ would always be greater or equal to $\frac{||Ax||_{\infty}}{||x||_{\infty}}$ for all $x$

17. Jan 27, 2016

### andrewkirk

Yes, but that doesn't advance the proof at all, as you already proved that in the OP. The missing piece is to show that it's a least upper bound, not just any old upper bound. Focus on the two questions at the end of my post #15.

18. Jan 27, 2016

### pyroknife

For the first question:
There can't be an upper bound $u$ less than $\max_i \sum_j |a_{ij}|$ Anything lower wouldn't be considered an "upper" bound.
For the second question:
Since anything lower is a no longer an "upper" bound, $\max_i \sum_j |a_{ij}|$ is simply the "least" upper bound.

I think these are the missing piece?

I still don't understand why we picked a unit vector with an infinity norm = 1 and a maximum 2-norm.
Also, for this post, how does the past previous posts prove that $$||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$?

19. Jan 27, 2016

### andrewkirk

They don't. That's (equivalent to) the extra bit that you have to prove. See post 15 for hints on how to prove that.

20. Jan 27, 2016

### pyroknife

So carrying on we have shown that for
$x'\equiv (1 1 1)$, $\frac{||Ax'||_{\infty}}{||x'||_{\infty}} = \max_i \sum_{j} |a_{ij}|$.
The next statement can be
$$||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$

So in one line:
$||Ax||_{\infty} = sup_{x\neq 0}\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq max_i \sum_{j} |a_{ij}| = \frac{||Ax'||_{\infty}}{||x'||_{\infty}} \leq ||Ax||_{\infty}$