Modifying solution of system of linear equations

Question

Suppose that we have a linear system of equations

$$Ax=b$$

where $A$ is a $3 \times 3$ matrix and $x$ and $b$ are $3$-vectors. Let $y$ denote the solution of this system of equations. I want to change matrix $A$ such that the new solution is vector $z$ in which

$$z_1 > y_1, \qquad z_2 = y_2, \qquad z_3 < y_3$$

Is there a systematic way to achieve this? In other words, I want a systematic way of finding out what changes I should introduce in matrix $A$ such that

• some entries of the new solution $z$ are greater than the corresponding entries of the old solution $y$.

• other entries of the new solution $z$ are equal to the corresponding entries of the old solution $y$.

• some other entries of the new solution $z$ are less than the corresponding entries of the old solution $y$.

Is there a method or technique to achieve this? What is it called? Thank you.

Answer 1

Here is a systematic way of doing it. Numerically solve an optimization problem to find a matrix $E$, which is smallest in some sense, let's say Frobenius norm, such that $$(A+E)x = b$$ $$x_1 \ge y_1 + d$$ $$x_2 = y_2$$ $$x_3 \le y_3 - d$$where $d$ is some specified moimnimum amount of separation between the old and new solution elements, and is needed because numerical optimization solvers don't deal with strict inequalities for continuous variables.

I show here an implementation in CVX (under MATLAB) for 3 by 3 $A$. But this easily generalizes to higher dimensions and many variations. $A$, $b$, $y$, and $d$ are the input data to the optimization problem, and $x$ and $E$ are the (decision) variables being solved for in the optimization.

cvx_begin
variables x(3) E(3,3)
minimize(norm(E,'fro'))
subject to
(A+E)*x == b
x(1) >= y(1) + d
x(1) == y(2) 
x(3) <= y(3) - d
cvx_end

At the conclusion of which E will be the matrix having smallest Frobenius norm which satisfies the constraints. Note that if $A$ is singular and there is a solution satisfying all the constraints with $E$ being the zero matrix (i.e., not "changing" $A$), then such a solution will be found by this optimization approach without any special logic being required.

Answer 2

If you want to, given a solution, obtain the matrix $A$, for the system $Ax=b$. You can do: $$Ax=[a_1,a_2,a_3]x=x_1a_1+x_2a_2+x_3a_3=b$$ Being $a_i$ the columns of the matrix A.

Choose linearly independent vectors $a_1$ and $a_2$ and compute $a_3$ as follows: $$a_3=\frac{1}{x_3}b-\frac{x_1}{x_3}a_1-\frac{x_2}{x_3}a_2$$ Make sure that the resulting matrix $A$ is nonsingular if you want a unique solution, i.e. choose for example $a_1$ and $a_2$ perpendicular to $b$.