Simplify the matrix of a linear system knowing that some of the solutions are equal

Question

In order to improve the efficiency of my python program I'm trying to take advantage of some properties of a linear system I need to solve.

I have a linear system $Ax = b$ and I know beforehand that some of the solutions are equal, though I don't know their values before solving the system (i.e. $x_1 = x_{10}$, $x_3 = x_5$, ...).

Is there any way I can simplify my system ($A$ and b) for faster solving? My first thought was to eliminate one of the two unknowns for each pair and to do the sum of both columns associated with the elements of the pair, weighted by 1/2, but I'm not sure at all that this is mathematically correct.

Answer 1

Let us call $(c_i)_i$ the columns of$A$.

The equation can be written as: $$b = \sum_{i=1}^{n} x_ic_i $$

If for example we know that $x_1 = x_2$, the equation becomes: $$b = x_2(c_1 + c_2) + \sum_{i=3}^{n} x_ic_i $$

The procedure follows:

• Replace $c_2$ by $c_1 + c_2$
• Suppress $c_1$
• Remove $x_1$ from the set of unknown values
• Don't modify $b$