Largest solution of a linear system

Question

Given an $n\times m$ matrix $A$ of full-column rank, and a vector $\vec b$ of size $n$. We consider the solution of the linear system: $$ A\vec{x}=\vec{b} $$ Since $A$ is full-column rank, the solutions of the linear system are bounded. Is it possible to get an upper bound on the norm of these solutions ?

Answer 1

Suppose that $A\vec{x}=\vec{b}$ is solvable.

Unless $A$ has full column rank, the system $A\vec{x}=\vec{b}$ has infinitely many solutions. The set $$ \{\lVert\vec{x}\rVert:A\vec{x}=\vec{b}\} $$ turns out to be bounded below, but not above. In fact, it is possible to prove that $$ \inf\{\lVert\vec{x}\rVert:A\vec{x}=\vec{b}\}=\lVert\vec{x}^+\rVert $$ Here, $\vec{x}^+=A^+\vec{b}$ where $A^+$ is the Moore-Penrose inverse or pseudoinverse of $A$. The vector $\vec{x}^+$ also satisfies $A\vec{x}^+=\vec{b}$.

Note that this is true regardless of the rank of $A$.

To convince yourself that $\{\lVert\vec{x}\rVert:A\vec{x}=\vec{b}\}$ is not bounded above, consider \begin{align*} A &= \left[\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \end{array}\right] & \vec{b} &= \left[\begin{array}{r} 0 \\ 0 \end{array}\right] \end{align*} The solutions to $A\vec{x}=\vec{b}$ are of the form $$ \vec{x} = \left[\begin{array}{r} 0 \\ 0 \\ c \end{array}\right] $$ for $c\in\Bbb R$.