Is a vector, which is orthogonal to solution of undetermined system of linear equations, in a null space of such system?

Question

Let's have the following linear system $Ax = b$ and assume that $x_0$ is a solution this linear system, where $A$ is an $n \times m$ matrix, with $n < m$, $x$ is an $m$-dimensional column vector and $b$ is an $n$-dimensional column vector.

Let's have a vector $x_1$ which is orthogonal to the solution $x_0$. Is $x_1$ in a null space of $A$ ?

I want to prove that $x_0 + x_1$ is also a solution to $Ax = b$ and for this, $x_1$ has to be in the null space of $A$, so that this holds:

$$A(x_0 + x_1 )= b $$ $$Ax_0 + Ax_1 = b $$

$$b + Ax_1 = b $$ $$ Ax_1 = 0 $$

How to find whether the last equation holds?

Answer 1

From an answer of mine:

Given fat matrix $\mathrm A \in \mathbb R^{m \times n}$ ($m < n$) and vector $\mathrm b \in \mathbb R^m$, consider the following linear system in $\mathrm x \in \mathbb R^n$ $$\rm A x = b$$ where $\rm A$ has full row rank. Let the singular value decomposition (SVD) of $\rm A$ be as follows $$\mathrm A = \mathrm U \Sigma \mathrm V^\top = \mathrm U \begin{bmatrix} \Sigma_1 & \mathrm O \end{bmatrix} \begin{bmatrix} \mathrm V_1^\top \\ \mathrm V_2^\top \end{bmatrix} = \mathrm U \Sigma_1 \mathrm V_1^\top$$ The least-norm solution of $\rm A x = b$ is given by $$\mathrm x_{\text{LN}} := \mathrm A^\top \left( \mathrm A \mathrm A^\top \right)^{-1} \mathrm b = \cdots = \mathrm V_1 \Sigma_1^{-1} \mathrm U^\top \mathrm b$$ where the inverse of $\mathrm A \mathrm A^\top$ exists because $\rm A$ has full row rank.

---

Note that $\mathrm x_{\text{LN}}$ is in the column space of matrix $\mathrm V_1$, which is the orthogonal complement of the null space of matrix $\mathrm A$ (which is the column space of matrix $\mathrm V_2$).

For example, let $m = 1$ and $n=2$. In this case, the solution set of $\rm A x = b$ is a line in $\Bbb R^2$. The vector that spans this line is in the null space of matrix $\rm A$. The least-norm solution is the point on this line that is closest to the origin in the Euclidean norm. If one draws a line segment from the origin till the least-norm solution, this line segment will be orthogonal to the line. Thus, a vector orthogonal to the least-norm solution is in the null space. However, do note that I assumed that matrix $\rm A$ has full row rank. If matrix $\rm A$ does not have full row rank, then there is no unique least-norm solution.

Answer 2

You can not prove it because if $x_1$ is orthogonal to $x_0$, you can not say that $x_1+x_0$ is another solution to $Ax=b$.

For instance, suppose that $A= \begin{bmatrix}1 & -1 \\ 1 & -1\end{bmatrix}$. Then if $x_0=\begin{bmatrix}1 \\ 1\end{bmatrix}$, $b=\begin{bmatrix}0 \\ 0\end{bmatrix}$. But if you take $x_1=\begin{bmatrix}1 \\ -1\end{bmatrix}$, then $x_0$ and $x_1$ are orthogonal ($x_0.x_1=0$), and $A.(x_0+x_1)\neq\begin{bmatrix}0 \\ 0\end{bmatrix}$