# General form of the solution to the linear system with one more unknowns than equations

Suppose we have the following linear system $$\begin{bmatrix} a_1^1 & \ldots & a_1^{N+1}\\ \vdots & \ddots & \vdots \\ a_{N-1}^1 & \ldots & a_{N-1}^{N+1} \\ 1 & \ldots & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ \vdots \\ \vdots \\ x_{N+1} \end{bmatrix}=\begin{bmatrix} b_1\\ \vdots \\ b_{N-1} \\ 1 \end{bmatrix},$$ where $$a_n^i$$ and $$b_n$$ are all known constants that are strictly positive for $$n=1,\ldots,N-1$$ and $$i=1,\ldots,N+1$$.

Is there a general form of the solution to the above system such that $$\begin{bmatrix} x_1 \\ \vdots \\ \vdots \\ x_{N+1} \end{bmatrix}=v_1+\alpha v_2,$$ where $$v_1$$ and $$v_2$$ are fixed vectors in $$\mathbb{R^{N+1}}$$ and $$\alpha$$ is a free variable in $$\mathbb{R}$$?

Thanks in advance for any help!

Edit From Gerry Myerson's reply, I realized that we need to add the following constraints to make sure that the system has a solution $$0 < a_n^{N+1} < a_n^N < \ldots < a_n^1$$ for all $$n=1,\ldots,N-1$$. Also, $$x_{i}$$ is strictly positive for $$i=1,\ldots,N+1$$.

• If you know how to solve an $N \times N$ system, move $x_{N+1}$ to the other side in all equations, then solve the resulting $N \times N$ system for $x_1, \dots, x_N$ in terms of $a_i^j$ and $x_{N+1}$.
– dxiv
May 12, 2021 at 2:57
• @dxiv Thanks for your reply! Do you mean we can transform the linear equation as follows $$\begin{bmatrix} a_1^1 & \ldots & a_1^N\\ \vdots & \ddots & \vdots \\ a_{N-1}^1 & \ldots & a_{N-1}^N \\ 1 & \ldots & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ \vdots \\ \vdots \\ x_N \end{bmatrix}=\begin{bmatrix} b_1-a_1^{N+1}x_{N+1}\\ \vdots \\ b_{N-1}-a_{N-1}^{N+1}x_{N+1} \\ 1-x_{N+1} \end{bmatrix},$$ and solve from here?
– Xuan
May 12, 2021 at 3:26
• Right, which you can also write as $\;= \begin{bmatrix} b_1\\ \vdots \\ b_{N-1} \\ 1 \end{bmatrix} - x_{N+1} \begin{bmatrix} a_1^{N+1}\\ \vdots \\ a_{N-1}^{N+1} \\ 1 \end{bmatrix}\;$ if you want to keep the free variable separate.
– dxiv
May 12, 2021 at 3:37
• I know that we can then solve the equation by the formula, $$x=A^{-1}b',$$ where $A=\begin{bmatrix} a_1^1 & \ldots & a_1^N\\ \vdots & \ddots & \vdots \\ a_{N-1}^1 & \ldots & a_{N-1}^N \\ 1 & \ldots & 1 \end{bmatrix}$ and $b'=\begin{bmatrix} b_1\\ \vdots \\ b_{N-1} \\ 1 \end{bmatrix} - x_{N+1} \begin{bmatrix} a_1^{N+1}\\ \vdots \\ a_{N-1}^{N+1} \\ 1 \end{bmatrix}$. But, it still seems to be rather complicated to solve. Is there a general form to this problem?
– Xuan
May 12, 2021 at 3:58
• That is the general form. There may exist shortcuts if there is something special about the equations that you can exploit, but in the general case it's just a linear system of $N$ equations that you need to solve using the standard methods.
– dxiv
May 12, 2021 at 4:01

The system might not have any solutions, e.g., $$\pmatrix{1&1&1\cr1&1&1\cr}\pmatrix{x_1\cr x_2\cr x_3\cr}=\pmatrix{2\cr1\cr}$$
EDIT: Despite the edit to the question, the system still might have no solutions, e.g., $$\pmatrix{4&3&2&1\cr4&3&2&1\cr1&1&1&1\cr}\pmatrix{x_1\cr x_2\cr x_3\cr x_4\cr}=\pmatrix{2\cr1\cr1\cr}$$