Matrix theory question (to do with Linear Programming)

[flyingpig]

Homework Statement

Suppose we have a maximum LOP P

max $$z = c^t x$$

s.t.

$$Ax \leq b$$
$$x \geq 0$$

and the dual to P is

min $$w = b^t y$$

$$A^t y \geq c$$

$$y \leq 0$$

Then the bounds are

$$z = c^t x \leq y^t Ax \leq y^t b = b^t y = w$$

question

Okay where the heck did $$y^t Ax$$ came from? And what property of matrix are they using for $$y^t b = b^t y$$? Neither y or b are numbers, they are points? column vectors?

 

[Mark44]

Homework Statement

Suppose we have a maximum LOP P

max $$z = c^t x$$

s.t.

$$Ax \leq b$$
$$x \geq 0$$

and the dual to P is

min $$w = b^t y$$

$$A^t y \geq c$$

$$y \leq 0$$

Then the bounds are

$$z = c^t x \leq y^t Ax \leq y^t b = b^t y = w$$

question

Okay where the heck did $$y^t Ax$$ came from? And what property of matrix are they using for $$y^t b = b^t y$$? Neither y or b are numbers, they are points? column vectors?

y and b are column vectors, or if you like, n x 1 matrices. So y^tb can be thought of as a 1 x n matrix multiplying an n x 1 matrix, which produces a 1 x 1 matrix (a number). This is just like a dot product, for which we know that u $\cdot$ v = v $\cdot$ u. In terms of matrix multiplication, you can't change y^tb to by^t, but you can write it as b^ty.

From the constraints on the dual problem, you have c <= A^ty, so c^t <= (A^ty)^t = y^tA.

So c^tx <= y^tAx, and so on.

 

[flyingpig]

Is (y^tb)^t = b^t y

 

[Mark44]

Yes. In general, (AB)^t = B^tA^t. This wiki page (http://en.wikipedia.org/wiki/Transpose) lists several properties of matrix transposes.

 

[flyingpig]

y and b are column vectors, or if you like, n x 1 matrices. So y^tb can be thought of as a 1 x n matrix multiplying an n x 1 matrix, which produces a 1 x 1 matrix (a number).

Does that mean for z = c^tx, that the argument is the same?

My book defines it this way

$$c^T = (c_1,...,c_n), x = (x_1,...,x_n)^T$$

Where it looks like (actually it is lol), c is 1 x n and x is n x 1

Why do we want the final results to be a 1 x 1 matrix? What's wrong with n x n?

Also, one a bit further.

Usually (and this I think might answer myt own question below) we write solutions as y = (y_1,y_2)^t (two elements for now) and by that product and tranpose property we have

((y_1, y_2)^t)^t

For y = (y_1, y_2)^t is 1 x 2 matrix and then tranpose gives back 2 x 1 so that it could multiply out with A

Yes. In general, (AB)^t = B^tA^t. This wiki page (http://en.wikipedia.org/wiki/Transpose) lists several properties of matrix transposes.

Yeah I just couldn't see it in the beginning.

 

[Mark44]

Does that mean for z = c^tx, that the argument is the same?

Yes.

My book defines it this way

$$c^T = (c_1,...,c_n), x = (x_1,...,x_n)^T$$

Where it looks like (actually it is lol), c is 1 x n and x is n x 1

Why do we want the final results to be a 1 x 1 matrix? What's wrong with n x n?

Because we want the objective function z to be a number. In typical problems, the objective function represents the profit that we're trying to maximize, or a cost that we're trying to minimize, or similar.

Yeah I just couldn't see it in the beginning.

 

[flyingpig]

Yes.
Because we want the objective function z to be a number. In typical problems, the objective function represents the profit that we're trying to maximize, or a cost that we're trying to minimize, or similar.

So z = [9] for instance, we can't just pull out the 9 from the matrix right? (I remember we could do this for determinants, but we are talking abut a matrix here)

 

[flyingpig]

So c^tx <= y^tAx, and so on.

Actually I just noticed one thing, quite subtle and important too

When you took the tranpsoe of both sides of the inequality, why wouldn't the inequality sign flip? Like would tranposing the matrix A suddenly make it into a negative matrix...(matrix with negative elements?)?

 

[flyingpig]

Mark, there is also something wrong with the multiplication.

Suppose A is 3 x 3 and that a D-feasible solution is $$y = (y_1, y_2, y_3)^t$$

Then the product $$y^t Ax$$ cann be defined since y^t = $$\begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix}$$

 

[Mark44]

Both x and y are column vectors, so y^t is a row vector.

Suppose x and y are n x 1 (column vectors) and A is n x n. Then y^tAx is [1 x n] * [n x n] * [n x 1], which works out to [1 x n] * [n x 1], or 1 x 1. IOW, a scalar, which is exactly what you want.

 

[Mark44]

Actually I just noticed one thing, quite subtle and important too

When you took the tranpsoe of both sides of the inequality, why wouldn't the inequality sign flip?

You're basically comparing two numbers, that just happen to be obtained from the product of several matrices. The transpose of a number is just the number, so nothing weird happens, like changing the direction of the inequality.

Like would tranposing the matrix A suddenly make it into a negative matrix...(matrix with negative elements?)?

And when you transpose a matrix it switches the rows and columns. It doesn't turn it into a "negative" matrix, whatever that means.

IOW, A^t $\neq$ -A, if that's what you're saying.

 

[flyingpig]

You're basically comparing two numbers, that just happen to be obtained from the product of several matrices. The transpose of a number is just the number, so nothing weird happens, like changing the direction of the inequality.


And when you transpose a matrix it switches the rows and columns. It doesn't turn it into a "negative" matrix, whatever that means.

IOW, A^t $\neq$ -A, if that's what you're saying.

Nah I just think that the concept (other than swapping rows and columns) of tranpose is similar to finding an "inverse", not the "inverse of a matrix". I know you have no idea what I just said, it's just something I don't want to believe in, but i have to.