Solving a linear system with one more unknown than equations

Question

I have a linear system with 1 more unknown than equation. My questions are:

1. If I express this equation in matrix form, what 'result' will a computer spit out when solving it (say, with Maple and the command LinearSolve)? Will it choose one free variable on its own, and express all others in terms of this? (I have no specific data to test it myself, and I want a general answer as well, if one exists).

2. What if I want the solution vector $x$ which has the smallest Euclidean norm. How would I impose this restriction? How would I make a computer give me this specific solution? Are there infinitely many solutions in this case too, or does this condition remove that arbitrariness one has with an extra unknown and gives exactly one solution?

When expressed in matrix form, the linear system is tridiagonal, if that has any relevance.

Answer 1

1. Depends on the software. In Maple, solving symbolically, you get a symbolic solution with one free variable. In Matlab, solving by A\b, you get a numeric solution with fewest nonzero elements (this is not the same as smallest Euclidean norm). For example: solving $$\begin{pmatrix}1&2&3 \\ 4 & 5 & 7\end{pmatrix} x = \begin{pmatrix}7 \\ 8\end{pmatrix}$$ with Matlab in this way yields $(-3, 0, 3.33)^T$.

2. Theoretically: the lowest norm solution of $Ax =b$ can be obtained by solving $(AA^T) z=b$ and letting $x=A^Tz$. (Explanation). With the above example, this means solving $$\begin{pmatrix} 14 & 32 \\ 32 & 77 \end{pmatrix} z = \begin{pmatrix}7 \\ 8\end{pmatrix}$$ (solution: $z=(5.24, -2.07)^T$) and then computing $x=A^Tz$, namely $(-3.06, 0.11, 3.28)^T$. In practical terms, software often has more convenient routines for least squares solutions, such as lsq(A,b) in Scilab or pinv(A)*b in Matlab.

Are there infinitely many solutions in this case too

No, the solution of least norm is unique. The reason is Pythagorean theorem: the nearest point of the affine subspace $\{x:Ax=b\}$ to $0$ is the orthogonal projection of $0$ onto this subspace.