Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Matrix theory question (to do with Linear Programming)

  1. Sep 18, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose we have a maximum LOP P

    max [tex]z = c^t x[/tex]


    [tex]Ax \leq b[/tex]
    [tex]x \geq 0[/tex]

    and the dual to P is

    min [tex]w = b^t y[/tex]

    [tex]A^t y \geq c[/tex]

    [tex]y \leq 0[/tex]

    Then the bounds are

    [tex]z = c^t x \leq y^t Ax \leq y^t b = b^t y = w[/tex]


    Okay where the heck did [tex]y^t Ax[/tex] came from? And what property of matrix are they using for [tex] y^t b = b^t y [/tex]? Neither y or b are numbers, they are points? column vectors?
  2. jcsd
  3. Sep 19, 2011 #2


    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 [itex]\cdot[/itex] v = v [itex]\cdot[/itex] 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.
  4. Sep 19, 2011 #3
    Is (ytb)t = bt y
  5. Sep 19, 2011 #4


    Staff: Mentor

  6. Sep 20, 2011 #5
    Does that mean for z = ctx, that the argument is the same?

    My book defines it this way

    [tex]c^T = (c_1,...,c_n), x = (x_1,...,x_n)^T[/tex]

    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
  7. Sep 20, 2011 #6


    Staff: Mentor

    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.
  8. Sep 20, 2011 #7
    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)
  9. Sep 20, 2011 #8
    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?)?
  10. Sep 22, 2011 #9
    Mark, there is also something wrong with the multiplication.

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

    Then the product [tex]y^t Ax [/tex] cann be defined since yt = [tex]\begin{bmatrix}

  11. Sep 22, 2011 #10


    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.
  12. Sep 22, 2011 #11


    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 [itex]\neq[/itex] -A, if that's what you're saying.
  13. Sep 22, 2011 #12
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook