# Modifying solution of system of linear equations

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.

• What is the rank of $A$? If the matrix is singular, you may not have to update it. – Rodrigo de Azevedo Jul 11 '18 at 15:29

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.

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$.