1
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I have approved it because I guess it is correct, but it is hard to understand it from this answer.. $\endgroup$
    – pikachu
    Apr 4, 2021 at 11:09
  • $\begingroup$ 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? $\endgroup$
    – pikachu
    Apr 4, 2021 at 11:20
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2021 at 11:31
  • $\begingroup$ 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. $\endgroup$
    – pikachu
    Apr 4, 2021 at 11:32
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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