# Matrix theory question (to do with Linear Programming)

1. Sep 18, 2011

### flyingpig

1. The problem statement, all variables and given/known data

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?

2. Sep 19, 2011

### Staff: Mentor

y and b are column vectors, or if you like, n x 1 matrices. So ytb 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 ytb to byt, but you can write it as bty.

From the constraints on the dual problem, you have c <= Aty, so ct <= (Aty)t = ytA.

So ctx <= ytAx, and so on.

3. Sep 19, 2011

### flyingpig

Is (ytb)t = bt y

4. Sep 19, 2011

### Staff: Mentor

5. Sep 20, 2011

### flyingpig

Does that mean for z = ctx, 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

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

Last edited: Sep 20, 2011
6. Sep 20, 2011

### Staff: Mentor

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.

7. Sep 20, 2011

### flyingpig

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)

8. Sep 20, 2011

### flyingpig

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

9. Sep 22, 2011

### 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 yt = $$\begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix}$$

10. Sep 22, 2011

### Staff: Mentor

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

Suppose x and y are n x 1 (column vectors) and A is n x n. Then ytAx 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.

11. Sep 22, 2011

### Staff: Mentor

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, At $\neq$ -A, if that's what you're saying.

12. Sep 22, 2011

### flyingpig

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