MHB System no/infinitely many solution(s)

[mathmari]

Hey!

We have the matrix $A=\begin{pmatrix}1 & -1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1\end{pmatrix}$ and the vectors $b_1=\begin{pmatrix}1 \\ 0 \\1\end{pmatrix}$ and $b_2=\begin{pmatrix}-1 \\ 1 \\2\end{pmatrix}$.
Check if the system $Ax=b_i$ for $i\in \{1,2\}$ has a solution.
If the system is impossible find the solution that we get if the vector $b_i$ is projected onto the column space.
If the system has infinitely many solutions find the solution that belongs to the row space. I have done the following:

• For $b_1$ the echelon form of the extended matrix is $\begin{pmatrix}\left.\begin{matrix}
  \begin{matrix}1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}
  \end{matrix}\right|\begin{matrix}1 \\ -1 \\ 2\end{matrix}\end{pmatrix}$.
  
  That means that the system is impossible.
  
  A basis for the column space of $A$ is $\left \{\begin{pmatrix}1\\ 1\\ 0\end{pmatrix}, \begin{pmatrix}-1\\ 0\\ 1\end{pmatrix}\right \}$, right? (Wondering)
  
  Let them be $q_1$ and $q_2$ respectively.
  
  The projection of $b$ onto the column space of $A$ is \begin{equation*}b_{p1}=(b_1^Tq_1)q_1+(b_1^Tq_2)q_2=1\cdot q_1+0\cdot g_2=q_1\end{equation*}
  Applying again the Gaussian elimination method with the new vector we get the echelon form $\begin{pmatrix}\left.\begin{matrix}
  \begin{matrix}1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}
  \end{matrix}\right|\begin{matrix}1 \\ 0 \\ 0\end{matrix}\end{pmatrix}$.
  
  So we get the solution \begin{equation*}\begin{pmatrix}x_1 \\ x_2\\ x_3\end{pmatrix}=\begin{pmatrix}1+x_2 \\ x_2\\ -x_2\end{pmatrix}=\begin{pmatrix}1 \\ 0\\ 0\end{pmatrix}+x_2\begin{pmatrix}1 \\ 1\\ -1\end{pmatrix}\end{equation*} Is everything correct? (Wondering)
• For $b_2$ the echelon form of the extended matrix is $\begin{pmatrix}\left.\begin{matrix}
  \begin{matrix}1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}
  \end{matrix}\right|\begin{matrix}-1 \\ 2 \\ 0\end{matrix}\end{pmatrix}$.
  
  That means that the system has infinitely many solutions.
  
  A basis for the row space of $A$ is $\left \{\begin{pmatrix}1\\ -1\\ 0\end{pmatrix}, \begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\right \}$, right? (Wondering)
  
  We get the solution \begin{equation*}\begin{pmatrix}x_1 \\ x_2\\ x_3\end{pmatrix}=\begin{pmatrix}x_1 \\ x_1+1\\ 1-x_1\end{pmatrix}=\begin{pmatrix}0 \\ 1\\ 1\end{pmatrix}+x_1\begin{pmatrix}1 \\ 1\\ -1\end{pmatrix}\end{equation*}
  
  How do we see that this belongs to the row space? Do we have to check if it is a linear combination of the basis vectors of the row space? (Wondering)

 

[I like Serena]

A basis for the column space of $A$ is $\left \{\begin{pmatrix}1\\ 1\\ 0\end{pmatrix}, \begin{pmatrix}-1\\ 0\\ 1\end{pmatrix}\right \}$, right?

Let them be $q_1$ and $q_2$ respectively.

The projection of $b$ onto the column space of $A$ is \begin{equation*}b_{p1}=(b_1^Tq_1)q_1+(b_1^Tq_2)q_2=1\cdot q_1+0\cdot g_2=q_1\end{equation*}

Hey mathmari!

The formula you are using assumes that $q_1$ and $q_2$ have unit length.
But that is not the case is it? (Worried)

2. A basis for the row space of $A$ is $\left \{\begin{pmatrix}1\\ -1\\ 0\end{pmatrix}, \begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\right \}$, right?

We get the solution \begin{equation*}\begin{pmatrix}x_1 \\ x_2\\ x_3\end{pmatrix}=\begin{pmatrix}x_1 \\ x_1+1\\ 1-x_1\end{pmatrix}=\begin{pmatrix}0 \\ 1\\ 1\end{pmatrix}+x_1\begin{pmatrix}1 \\ 1\\ -1\end{pmatrix}\end{equation*}

How do we see that this belongs to the row space? Do we have to check if it is a linear combination of the basis vectors of the row space?

What happens if we find the projection of the solutions onto the row space? (Wondering)

 

[mathmari]

The formula you are using assumes that $q_1$ and $q_2$ have unit length.
But that is not the case is it? (Worried)

Ahh ok! Which is the correct formula that we have to use? Do we have to divide each part by the length, i.e. as follows?
\begin{equation*}b_{p1}=\frac{(b_1^Tq_1)}{q_1^Tq_1}q_1+\frac{(b_1^Tq_2)}{q_2^Tq_2}q_2\end{equation*}
(Wondering)

What happens if we find the projection of the solutions onto the row space? (Wondering)

Why do we have to do that? I got stuck right now. (Wondering)

 

[I like Serena]

Ahh ok! Which is the correct formula that we have to use? Do we have to divide each part by the length, i.e. as follows?
\begin{equation*}b_{p1}=\frac{(b_1^Tq_1)}{q_1^Tq_1}q_1+\frac{(b_1^Tq_2)}{q_2^Tq_2}q_2\end{equation*}

Yep. (Nod)

Why do we have to do that? I got stuck right now.

Well, we don't have to.
I merely wanted to show that you basically already have the answer. And also that the result is similar to the first part. (Emo)

Anyway, we are supposed to find the intersection of the line representing the solutions with the plane representing the row space. (Thinking)

 

[mathmari]

Yep. (Nod)

Ok! So we get \begin{equation*}b_{p1}=\frac{(b_1^Tq_1)}{q_1^Tq_1}q_1+\frac{(b_1^Tq_2)}{q_2^Tq_2}q_2=\frac{1}{2}\cdot q_1+\frac{0}{2}\cdot g_2=\frac{1}{2}q_1\end{equation*}

Applying again the Gaussian elimination method with the new vector we get the echelon form $\begin{pmatrix}\left.\begin{matrix}
\begin{matrix}1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}
\end{matrix}\right|\begin{matrix}\frac{1}{2} \\ 0 \\ 0\end{matrix}\end{pmatrix}$.

So we get the solution \begin{equation*}\begin{pmatrix}x_1 \\ x_2\\ x_3\end{pmatrix}=\begin{pmatrix}\frac{1}{2}1+x_2 \\ x_2\\ -x_2\end{pmatrix}=\begin{pmatrix}\frac{1}{2} \\ 0\\ 0\end{pmatrix}+x_2\begin{pmatrix}1 \\ 1\\ -1\end{pmatrix}\end{equation*} Is everything correct? (Wondering)

Well, we don't have to.
I merely wanted to show that you basically already have the answer. And also that the result is similar to the first part. (Emo)

Anyway, we are supposed to find the intersection of the line representing the solutions with the plane representing the row space. (Thinking)

Ok, so the intersection is $\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}$. That means that the solution that belongs to the row space is $\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}$, right? (Wondering)

 

[I like Serena]

Ok! So we get \begin{equation*}b_{p1}=\frac{(b_1^Tq_1)}{q_1^Tq_1}q_1+\frac{(b_1^Tq_2)}{q_2^Tq_2}q_2=\frac{1}{2}\cdot q_1+\frac{0}{2}\cdot g_2=\frac{1}{2}q_1\end{equation*}

Applying again the Gaussian elimination method with the new vector we get the echelon form $\begin{pmatrix}\left.\begin{matrix}
\begin{matrix}1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}
\end{matrix}\right|\begin{matrix}\frac{1}{2} \\ 0 \\ 0\end{matrix}\end{pmatrix}$.

So we get the solution \begin{equation*}\begin{pmatrix}x_1 \\ x_2\\ x_3\end{pmatrix}=\begin{pmatrix}\frac{1}{2}1+x_2 \\ x_2\\ -x_2\end{pmatrix}=\begin{pmatrix}\frac{1}{2} \\ 0\\ 0\end{pmatrix}+x_2\begin{pmatrix}1 \\ 1\\ -1\end{pmatrix}\end{equation*}

Is everything correct?

Ok, so the intersection is $\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}$. That means that the solution that belongs to the row space is $\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}$, right?

All correct. (Nod)

Note that in the first part we projected $b_1$ onto the column space and found a unique solution.
We have solved for the closest point to the range of the matrix.

And in the second part we effectively projected the solution on the row space to find a unique solution.
We have a solution that is as close as possible to the range of the inverse matrix. (Nerd)

 

[mathmari]

Note that in the first part we projected $b_1$ onto the column space and found a unique solution.

But we have a free variable $x_2$ so we don't have a unique solution. Or have I understood that wrongly? (Wondering)

 

[I like Serena]

But we have a free variable $x_2$ so we don't have a unique solution. Or have I understood that wrongly?

Ah yes, we still have a line there. (Blush)

Still, it is a unique solution if we intersect it with the row space. (Emo)

 

[GJA]

Hi mathmari and Klaas van Aarsen,

I want to politely and respectfully suggest that the analysis for the solution to the system $Ax = b_{p1}$ -- i.e., where $b_{1}$ has been projected to the column space of $A$ -- should be re-examined. In particular, the projection of $b_{1}$ onto the column space is not given by \begin{equation*}b_{p1}=(b_1^Tq_1)q_1+(b_1^Tq_2)q_2=1\cdot q_1+0\cdot q_2=q_1.\end{equation*}

Please refer to the attached image.

The projection of $b_{1}$ onto the column space of $A$ is the "shadow" $b_{1}$ casts on the plane determined by $q_{1}$ and $q_{2}.$ Here, $b_{1}$ is shown in blue; $b_{1p}$ is shown in red; and $q_{1}$ and $q_{2}$ in black. As we can see, it is possible for $b_{1}$ to be orthogonal to $q_{2}$ in $\mathbb{R}^{3}$, yet its projection onto the column space will contain a $q_{2}$ component nevertheless. The equation we must consider is $$b_{p1} = c_{1}q_{1} + c_{2}q_{2}\qquad (1).$$ Visually speaking, the magnitude of $c_{1}$ and $c_{2}$ are given by the lengths of the orange and purple line segments, respectively.

How do we solve for $c_{1}$ and $c_{2}$? This is done by taking dot products of (1) with $q_{1}$ and $q_{2}.$ It is very important to note here that $q_{1}$ and $q_{2}$ are not orthogonal, so $q_{1}\cdot q_{2}$ will not vanish. Doing this will yield a system of 2 equations that can be used to solve for $c_{1}$ and $c_{2}$. From there you can proceed to solving $Ax=b_{p1}$ using the row echelon technique applied previously.View attachment 9680

 

[I like Serena]

In particular, the projection of $b_{1}$ onto the column space is not given by \begin{equation*}b_{p1}=(b_1^Tq_1)q_1+(b_1^Tq_2)q_2=1\cdot q_1+0\cdot q_2=q_1.\end{equation*}

Oh yes, I forgot to take into account that $q_1$ and $q_2$ are not perpendicular in addition to not being of unit length. (Blush)

 

[mathmari]

So isn't there a general formula? Do we have to derive the formula by solving the system for $c_1$ and $c_2$ ? (Wondering)

 

[I like Serena]

So isn't there a general formula? Do we have to derive the formula by solving the system for $c_1$ and $c_2$ ? (Wondering)

As I see it, we can do one of:

1. Set up the system and solve it as GJA suggested.
2. Orthogonalize $q_1$ and $q_2$ and use the formula that you already used. We can use $\tilde q_2=q_2 - (q_2\cdot q_1)q_1 / \|q_1\|^2$ for that (Gram-Schmidt process).
3. Use the formula $\text{projection}(b)=b-(b\cdot n)n$, where $n$ is a vector of unit length that is orthogonal to both $q_1$ and $q_2$. It's the projection to the space normal to $n$, which is the desired space.
(Thinking)

 

[GJA]

I would suggest using equation (1) from my previous post and taking dot products of it with $q_{1}$ and $q_{2}.$ If that is too vague, here are some details that will hopefully make it make clear what I am suggesting. Note that $$b_{1} = c_{1}q_{1} + c_{2}q_{2} +c_{3}n,$$ where $n$ is a non-zero vector orthogonal to the $q_{1}$-$q_{2}$ plane. This is the mathematical way to express the fact that in the picture I posted $b_{1}$ equals orange + purple + green. Since $$b_{p1} = b_{1} - c_{3}n,$$ (1) becomes $$b_{1} - c_{3}n = c_{1}q_{1} + c_{2}q_{2}\qquad (2).$$ Taking dot products of (2) with $q_{1}$ and $q_{2}$, we get $$b_{1}\cdot q_{1} = c_{1}q_{1}\cdot q_{1} + c_{2}q_{2}\cdot q_{1}$$
and $$b_{1}\cdot q_{2} = c_{1}q_{1}\cdot q_{2} + c_{2}q_{2}\cdot q_{2},$$ because $n\cdot q_{1} = 0 = n\cdot q_{2}$.

If you work out those dot products you can get the system of equations for $c_{1}$ and $c_{2}$. Solve this system for $c_{1}$ and $c_{2}$, then solve the $Ax=b_{p1}$ equation using the row echelon technique you previously applied.

 

[mathmari]

I will try to solve the system as GJA suggested! First I tried to use the second way

2. Orthogonalize $q_1$ and $q_2$ and use the formula that you already used. We can use $\tilde q_2=q_2 - (q_2\cdot q_1)q_2 / \|q_2\|^2$ for that (Gram-Schmidt process).

Are the orthogonal vectors then:
\begin{align*}&\tilde q_1=q_1=\begin{pmatrix}1 \\ 1\\ 0\end{pmatrix} \\ &\tilde q_2=q_2 - \frac{q_2\cdot q_1 }{ \|q_1\|^2}q_1=\begin{pmatrix}-1 \\ 0\\ 1\end{pmatrix} - \frac{-1}{ 2}\begin{pmatrix}1 \\ 1\\ 0\end{pmatrix}=\begin{pmatrix}-1 \\ 0\\ 1\end{pmatrix} + \begin{pmatrix}\frac{1}{ 2} \\ \frac{1}{ 2}\\ 0\end{pmatrix}= \begin{pmatrix}-\frac{1}{ 2} \\ \frac{1}{ 2}\\ 1\end{pmatrix}\end{align*}
And so is the formula for the projection the following? \begin{equation*}b_{p1}=\frac{b_1\cdot \tilde q_1}{\|\tilde q_1\|^2}\tilde q_1+\frac{b_1\cdot \tilde q_2}{\|\tilde q_2\|^2}\tilde q_2\end{equation*}

(Wondering)

 

[I like Serena]

Yep. (Nod)

And I see you fixed the mistake I made in the Gram-Schmidt formula. Good.

 

[mathmari]

Great! Thank you for your help! (Star)(Mmm)