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

[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.

 

[andrewkirk]

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}|$

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.

 

[pyroknife]

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.

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

 

[andrewkirk]

Next,
the supremum is defined as the "least upper bound."

That is correct.

Thus, the supremum of the above expression is simply the equal sign.

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?

 

[pyroknife]

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?

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?

I was influenced by an answer to another thread I made where I made a hypothetical example:
$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?

 

[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}|$

 

[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$).

 

[pyroknife]

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$).

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?

 

[andrewkirk]

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?

'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}$.

 

[pyroknife]

'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}$.

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?

 

[andrewkirk]

Yes, that's it!

 

[pyroknife]

Yes, that's it!

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.

 

[pyroknife]

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

 

[pyroknife]

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

 

[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?

 

[pyroknife]

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?

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$

 

[andrewkirk]

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

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.

 

[pyroknife]

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.

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.

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?

Also, for this post, how does the past previous posts prove that $$ ||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$?

 

[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.

 

[pyroknife]

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.

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}$