Help with inequality proof please

Hiya I was wondering if someone could help me with question 2ii) in the picture.

Note

||z||_\infty = \displaystyle\mathrm{max}_{j=1,..,N} |z_j|

I proved 2i) basically using the triangle inequality.

For 2ii) I was thinking that

if we choose

d

\mathrm{such \ that}

d_i = 1

\mathrm{for \ all}

1 \leq i \leq N

then

Unparseable latex formula:

||Bd||_\infty = \displaystyle\mathrm{max}_{i=1,..,N} \displaystyle\sum_{j=1}^N |b_i_j|

I'm pretty sure this is true anyway. Then surely since it is true (which I think it is) then I can say that the inequality I am trying to prove in 2ii) holds. This feels really really cheap though and I don't think it is correct, could anyone point me in the right direction?

biddledy.png34.0KB

Reply 1

ghostwalker

Original post by TheBhramaBull

if we choose

d

\mathrm{such \ that}

d_i = 1

\mathrm{for \ all}

1 \leq i \leq N

then

Unparseable latex formula:

||Bd||_\infty = \displaystyle\mathrm{max}_{i=1,..,N} \displaystyle\sum_{j=1}^N |b_i_j|

I'm pretty sure this is true anyway.

Let

B= \begin{pmatrix} 1 & -1 \\-1 & 1\end{pmatrix}

Now tell me it's true.

Reply 2

TheBhramaBull

Original post by ghostwalker

Let

B= \begin{pmatrix} 1 & -1 \\-1 & 1\end{pmatrix}

Now tell me it's true.

Point taken haha that is so obvious too. Do you have any advice on question 2ii) then?

Reply 3

ghostwalker

Original post by TheBhramaBull

Point taken haha that is so obvious too. Do you have any advice on question 2ii) then?

Consider the particular i, that gives the maximum for the RHS, then construct your d

Reply 4

TheBhramaBull

Original post by ghostwalker

Consider the particular i, that gives the maximum for the RHS, then construct your d

I can only think to choose d such that d_i = -1 if b_ij < 0, d_i = 1 if b_ij greater than or equal to 0. But we cannot choose d we need to find it so im stuck.

I don't understand, which particular i gives the maximum for the RHS, why is there a particular i that gives the maximum for the RHS?

Reply 5

ghostwalker

Original post by TheBhramaBull

For a given B one of the values for i must make the RHS a maximum.

There isn't one value of i for all Bs, but for any given B, there must be at least one value of i, that makes the RHS a maximum.

Same with the d; there isn't going to be one value for d that works for all Bs, but you can construct one for any given B

Reply 6

TheBhramaBull

Original post by ghostwalker

But then does that mean that I am allowed to use the answer:

choose d such that d_i = -1 if the sum from j=1 to N of b_ij < 0, or d_i = 1 if the sum of b_ij from j = 1 to N is greater than or equal to 0.

Sorry but that's what I am understanding from your previous post. I do appreciate the help, thanks a lot.

Reply 7

ghostwalker

Original post by TheBhramaBull

Apply your thought process to the example I gave; does it work?

Also I'm not clear whether you saying this for all i. You need to be precise. Look at my previous post.

Reply 8

TheBhramaBull

Original post by ghostwalker

Apply your thought process to the example I gave; does it work?

Also I'm not clear whether you saying this for all i. You need to be precise. Look at my previous post.

Okay so how about choose d such that for

i = 1,2,...,N

Unparseable latex formula:

\displaystyle\sum_{j=1}^N b_i_j < 0

then set

d_i = -1

, if

Unparseable latex formula:

\displaystyle\sum_{j=1}^N b_i_j \geq 0

then set

d_i = 1

Or is this not sufficient. It's basically the same as what I said before, although I feel it is more precise, and should seem a bit clearer to you.

Reply 9

ghostwalker

Original post by TheBhramaBull

Okay so how about choose d such that for

i = 1,2,...,N

Unparseable latex formula:

\displaystyle\sum_{j=1}^N b_i_j < 0

then set

d_i = -1

, if

Unparseable latex formula:

\displaystyle\sum_{j=1}^N b_i_j \geq 0

then set

d_i = 1

Or is this not sufficient. It's basically the same as what I said before, although I feel it is more precise, and should seem a bit clearer to you.

OK, it's clearer what you're saying, but I don't think you've followed what I was saying in my previous posts.

2 things:

1) check that value of d using the example I gave in my first post. Does it work?

2) You don't need to be concerned with all the values that "i" can take, only one that makes the RHS a maximum. That's what you have to construct your "d" against, and it's not necessarily going to be all "1"s or all "-1"s.

(edited 13 years ago)

Reply 10

TheBhramaBull

Original post by ghostwalker

Okay so

1. By my calculations its does work using your first example where by my rules we would have d = (1,1) and

Unparseable latex formula:

||Bd||\infity = 0

and so the inequality holds.

2. I still am struggling with this, I don't know how one can say for any square matrix B, only one value in d makes the RHS a maximum, and for this specific d_i I don't see how one could decide whether it should be 1 or -1.

Reply 11

ghostwalker

Original post by TheBhramaBull

Okay so

1. By my calculations its does work using your first example where by my rules we would have d = (1,1) and

Unparseable latex formula:

||Bd||\infity = 0

and so the inequality holds.

LHS = 0, and RHS = 2. And the last time I checked

0 \ge 2

was false.

2. I still am struggling with this, I don't know how one can say for any square matrix B, only one value in d makes the RHS a maximum, and for this specific d_i I don't see how one could decide whether it should be 1 or -1.

I really don't know what else to say; perhaps someone else may be able to explain it better.

For a given B, there is at least one i, that makes the RHS a maximum. For that value of i, you will need to find "d", i.e. all the d_i, that make the inequality true (there are multiple values of d that will work, you just need to find one.

It is unfortunate that the same suffix notation is being used for both sides of the inequality which may be confusing things. Perhaps call them d_k on the LHS, and you need to find all the ones that make up a specific d.

Reply 12

TheBhramaBull

Original post by ghostwalker

LHS = 0, and RHS = 2. And the last time I checked

0 \ge 2

was false.

I really don't know what else to say; perhaps someone else may be able to explain it better.

For a given B, there is at least one i, that makes the RHS a maximum. For that value of i, you will need to find "d", i.e. all the d_i, that make the inequality true (there are multiple values of d that will work, you just need to find one.

It is unfortunate that the same suffix notation is being used for both sides of the inequality which may be confusing things. Perhaps call them d_k on the LHS, and you need to find all the ones that make up a specific d.

1. Can you explain this please? I have RHS = |-1 + 1| = 0

Reply 13

ghostwalker

Original post by TheBhramaBull

1. Can you explain this please? I have RHS = |-1 + 1| = 0

This is equation labelled (4) in your attachment.

RHS = max {i=1,2} sum {j=1,2} |b_i,j|

|b_ij| = 1 for all entries in the example. Hence summing two of them gives you "2".