How to use a projection to solve this linear system of equations?

by Sother   Last Updated July 09, 2017 00:20 AM

I am watching a lecture from my professor at MIT, and he says that we can solve this system of linear equations using a projection. I’m not able to see how it done.

We are solving for $dx$ and $ds$ which are vectors:

$\mu dx + ds = 1 \mu$ where $\mu$ is a scalar, real number.

$ A dx = 0$

$(dy) A + ds = 0$

He says that since we know:

$dx \in A$

$ds \in A^\perp$

…then we can use a projection to solve for $dx$ and $ds$. (we will get $dy$ too I think, but we don’t care about its value). He say:

“Find a vector, that’s the all ones vector, and break it up into a part that is inside of A and a part that is perpendicular to A. This is a projection”.

I have not had any luck going about solving this. But I have a few confusions about this.

  • 1) The equation $ A dx = 0$ does not mean that $dx$ is inside of A. It means it is in the nullspace of A, so I think that the professor is wrong here in saying that.

  • 2) The professor is also wrong in saying that it is the “all ones” vector we are projecting. It is not the “all ones” vector that we are projecting, it is a scaled version of the all ones vector, which admittedly doesn’t change the direction, but still changes the solution to the linear system.

  • 3) No matter what I use for the matrix A, when I solve this using a projection, I always get the $ds$ vector as the zero vector, and the $dx$ vector as having all non-zero values. This causes most of the equations to be violated. E.g., I get values for $dx$ s.t. $A dx \ne 0$

How do I solve this using a projection of the all ones vector?

P.S. I am watching at approximately minute 53.

Answers 1

Starting at 53:26, the speaker has swapped the symbols $A$ and $A^\perp$. If $A \cdot \overline{dx} = \overline{0}$, (where I use overlines to indicate vectors because the MathJax "$\vec{dx}$" is awful) then $dx$ is perpendicular to each row vector in $A$, so $dx \in A^\perp$.

Note that $\mu \, \overline{dx} + \overline{ds} = \overline{1} \, \mu$ can be rescaled to $\overline{dx} + \frac{1}{\mu} \overline{ds} = \overline{1}$, so we can just as easily think of this as projecting $\overline{1}$ into a "perpendicular to the $Ax = b$ constraint ($\overline{dx}$) component" and a "scaled copy of the parallel component". Some prefer the equation with only one mention of $\mu$ and some prefer not having the division. Both represent equivalent computations.

When I try the easiest possible version of solving this system, with $A = 1$ (the $1 \times 1$ matrix containing $1$), I get $\overline{dx} = 0$, $\overline{dy} = -\mu$, and $\overline{ds} = \mu$. Are you sure you're solving the system correctly?

Eric Towers
Eric Towers
July 08, 2017 23:31 PM

Related Questions

Is every linear projection normal?

Updated October 10, 2017 08:20 AM

linear inequalities

Updated March 21, 2016 08:08 AM