# Largest solution of a linear system

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 ?

• If $A$ has full column rank, then $A\vec{x}=\vec{b}$ has no more than one solution. As I noted in my answer, one can obtain a lower bound on the norms of the solutions without rank assumptions. Feb 23, 2019 at 19:29

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$$.