2
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 19:29

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ sorry, the first version of the question wasn't making sense... $\endgroup$
    – Tanj
    Feb 23, 2019 at 0:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .