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

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?

• And I have tried empiricaly that it does not hold for in general, but is there any way where it holds? – pikachu Apr 3 at 15:18

## 2 Answers

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.

• I have approved it because I guess it is correct, but it is hard to understand it from this answer.. – pikachu Apr 4 at 11:09
• Thanks, this comment helps ! Do you mind adding it to the answer for others? If it would be possible for you, I have another question (where you posted comment that this is sister question), how does this relate to the first point of that question, please? – pikachu Apr 4 at 11:20
• I noticed you posted two questions in a row and that they seemed to be related to some extent. In that case, cross-linking may help readers understand where you're coming from. – Rodrigo de Azevedo Apr 4 at 11:31
• Thats right, I could have done it better. I am not sure whether and how can I cross link them now, but you have added a comment there and it seems as a good way for reference. – pikachu Apr 4 at 11:32

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