0
$\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 at 15:18
1
$\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 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 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$ – Rodrigo de Azevedo Apr 4 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 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.