"Correcting" an inconsistent system of linear equations by introducing variables

Question

Given an inconsistent system of linear equations, it seems always possible to make it consistent by introducing new variables and adding them in convenient places.

For a baby example, given the system of equations \begin{align*} x + y &= 0 \\ x + y &= 1 \end{align*} one can make it consistent by adding a new variable $w$ to get \begin{align*} x + y &= 0 \\ w + x + y &= 1 \end{align*} (I shouldn't have added it to both equations, however.)

Is there a systematic method to achieve this? How many variables do I need to add to a system of $n$ equations in $n$ unknowns? Is there a "degree of inconsistency" (e.g. the number of equations I need to take out to get a consistent system of equations)?

Answer 1

Write your system like this:

$$a_{11}x_{1} + a_{12}x_{1} + \cdots + a_{1n}x_{n} = b_1$$ $$a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} = b_2$$ $$\vdots$$ $$a_{m1}x_{1} + a_{m2}x_{2} +\cdots + a_{mn}x_{n} = b_m$$

Or equivalently as $Ax = b$:

$$\underbrace{\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix}}_{A}\underbrace{\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix}}_{x} = \underbrace{\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m\end{pmatrix}}_{b}$$

This system being inconsistent is equivalent to the fact that $b$ is not in the linear span of the columns of the matrix $\{A_1, A_2, \ldots, A_n\} \subseteq \mathbb{R}^m$ where $A_j = \begin{pmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj}\end{pmatrix}$.

In particular, the set $\{A_1, A_2, \ldots, A_n\}$ does not span the space $\mathbb{R}^m$, meaning that $$\dim \operatorname{span}\{A_1, A_2, \ldots, A_n\} < m$$

Adding additional unknowns to the system in the way you propose amounts to adding more vectors to this set, until the set is large enough so that $b$ is contained in its linear span.

Namely, adding an extra unknown to the $i$-th equation augments the matrix like this:

$$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & 0\\ a_{21} & a_{22} & \cdots & a_{2n} & 0\\ \vdots & \vdots & \cdots & \vdots & \vdots\\ a_{i1} & a_{i2} & \cdots & a_{in} & 1\\ \vdots & \vdots & \cdots & \vdots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} & 0\\ \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ w\end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m\end{pmatrix}$$

The set of columns is now $\{A_1, \ldots, A_n, e_j\}$. Since the unit vectors $\{e_1, \ldots, e_m\}$ span $\mathbb{R}^m$, it is clear that if you add enough of them into $\{A_1, \ldots, A_n\}$, you will achieve that $b$ is in the span of the matrix columns.

If adding unknowns multiplied by a scalar is allowed, then you can simply add $b$ into the set $\{A_1, \ldots, A_n\}$ so that you have

$$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1\\ a_{21} & a_{22} & \cdots & a_{2n} & b_2\\ \vdots & \vdots & \cdots & \vdots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m\\ \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ w\end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m\end{pmatrix}$$

which is trivially solvable with $x_1 = \cdots = x_m = 0$ and $w = 1$.

Answer 2

If you allow coefficients for the new variables, you can always achieve this with one extra variable. Indeed, given the system $$a_{11}x_{1} + a_{12}x_{2} +\cdots + a_{1n}x_{n} = b_1 \\ a_{21}x_{1} + a_{22}x_{2} +\cdots + a_{2n}x_{n} = b_2\\ ...\\ a_{m1}x_{1} + a_{m2}x_{2} +\cdots + a_{mn}x_{n} = b_m\\$$ the new system $$a_{11}x_{1} + a_{12}x_{2} +\cdots + a_{1n}x_{n}+b_1w = b_1 \\ a_{21}x_{1} + a_{22}x_{2} +\cdots + a_{2n}x_{n}+b_2w = b_2\\ ...\\ a_{m1}x_{1} + a_{m2}x_{2} +\cdots + a_{mn}x_{n}+b_mw = b_m\\$$ is always consistent.