(a) Show there is an x 0 with Ax < 0 if and only if there is an x 0 with Ax 1. N

Question

(a) Show there is an x 0 with Ax < 0 if and only if there is an x 0 with Ax 1.

Note: we use the definition (x1, x2, . . . , xn) < (y1, y2, . . . , yn) if and only if x1 < y1, x2 < y2, . . . and xn < yn. This is the standard notation in matrix theory for matrix or vector inequalities. This may be contrary to your expectations. Mathematically speaking, the symbol > would generally mean and 6= but this is not true for matrices or vectors. A vector x might satisfy x 0 and also x 6= 0 and yet still have some 0 entries. Such a vector x with 0 entries has x 6>0.

(b)) Let A be an m × n matrix. Prove that either:

i) there exists an x 0 with Ax < 0 or

ii) there exists y 0 with AT y 0 and y 6= 0 but not both.

Hint: Extend the idea in a) and use it in setting up a primal dual pair

Explanation / Answer

(a) We can write a point in R n as X = (x1,..., xn). This point is often called a vector. Frequently it is useful to think of it as an arrow pointing from the origin to the point. Thus, in the plane R 2 , X = (1,2) can be thought of as an arrow from the origin to the point (1,2). Algebraic Properties Alg-1. ADDITION: If Y = (y1,..., yn), then X +Y = (x1 +y1,..., xn +yn). Example: In R 4 , (1,2,2,0)+(1,2,3,4) = (0,4,1,4). Alg-2. MULTIPLICATION BY A CONSTANT: cX = (cx1,..., cxn). Example: In R 4 , if X = (1,2,2,0), then 3X = (3,6,6,0). Alg-3. DISTRIBUTIVE PROPERTY: c(X +Y) = cX +cY . This is obvious if one writes it out using components. For instance, in R 2 : c(X +Y) = c(x1 +y1, x2 +y2) = (cx1 +cy1, cx2 +cy2) = (cx1, cx2)+(cy1, cy2) = cX +cY.

The inner product of vectors X and Y in R n is, by definition, hX, Yi := x1y1 +x2y2 +···+xnyn. (1) This is also called the dot product and written X ·Y . The inner product of two vectors is a number, not another vector. In particular, we have the vital identity kXk 2 = hX, Xi relating the inner product and norm. For added clarity, it is sometimes useful to write the inner product in R n as hX, YiRn . Example: In R 4 , if X = (1,2,2,0) and Y = (1,2,3,4), then hX, Yi = (1)(1) + (2)(2)+(2)(3)+(0)(4) = 3.

(b)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.