# multiplication of nonzero scalar in a constraint of the primal

Suppose we have primal and its dual in standard form, that is

\begin{align*} (P) \max z = cx \\ st \; \; Ax = b \\ \; \; \; x \geq 0 \\ \end{align*}

\begin{align*} (D) \min z = by \\ st \; \; yA \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Where $$A$$ is an $$m$$ by $$n$$ matrix an $$x$$ is an n vector and $$y$$ is an m vector.

Suppose we multiply one of the constraints of the primal by some number $$\alpha > 0$$. Does this affect the solution of the dual?

## Thoughts:

Since a constraint is of the form $$a_{ij} \cdot x$$, take one of the $$i's$$, say we multiply

$$a_{i1}x_1 + a_{i2} x_2 + ... + a_{in} x_n$$

by $$\alpha$$

Once we set up our tableau, once we divide this row by $$\alpha$$, then in the LFH, we would have

$$\frac{ b_i}{\alpha}$$

the ith component of the vector $$b$$. Doesnt it change the solution in the primal tableau? Since solutions are the same for primal and dual???

Multiplication by a non-zero scalar is equivalent to multiplication of an elementary matrix, $$E$$.

\begin{align*} (P') \max z = c^Tx \\ st \; \; (EA)x = (Eb) \\ \; \; \; x \geq 0 \\ \end{align*}

The dual is \begin{align*} (D') \min z = (Eb)^Ty \\ st \; \; y^T(EA) \geq c \\ \; \; \; y \; \; \; free \\ \end{align*}

Suppose $$w$$ is the original dual solution, then $$y=E^{-T}w.$$

For the operation of multiplication by a scalar, we have $$E^T=E$$.

Hence $$y=E^{-1}w$$. That is if we multiply $$\alpha$$ to the $$i$$-th constraint, now for the dual solution, we would divide $$w_i$$ by $$\alpha$$ and we can keep the rest to be the same.

• Can you help me with this related problem: math.stackexchange.com/questions/2989440/… – Mikey Spivak Nov 8 '18 at 15:11
• at first glance, it seems that doing that operation might cause the primal problem to become infeasible. – Siong Thye Goh Nov 8 '18 at 15:24
• But isnt it doing the same operations as the previous case but this time to the dual? – Mikey Spivak Nov 8 '18 at 18:06
• the duality is in inequality form, multiplying an inequality and adding it to another one might change the feasible set. Also, if you multiply by a negative number, the inequality get flipped. – Siong Thye Goh Nov 8 '18 at 18:09
• You are right :/ – Mikey Spivak Nov 8 '18 at 18:23