Solving non-square linear systems with the exterior product and Cramer's rule

Question

I'm reading the book Linear algebra via exterior products by Sergei Winitzki (which is the worst book, ever) and he shows that you can solve linear systems with a general solution with Cramer's rule and the exterior product. Let's say the vectors a,b,c are not a basis in the vectorspace V, then there exists a maximal nonzero exterior product of a linear independent subset of a,b,c Take an example

$2x+y=1$

$2x+2y+z=4$

$y+z=3$

Now $a=(2,2,0)$, $b=(1,2,1)$, $c=(0,1,1)$, $p=(1,4,3)$

We see that $a \wedge b \wedge c=0$. And the maximal nonzero exterior product can be written as $\omega =a \wedge b$ (which is not equal to zero. Now we can check if $p$ is a subset of the span ${a,b}$ with $\omega \wedge p=0$ so $p$ can be expressed with $a,b$. We can find the coefficients with Cramer's rule

$\alpha = \frac{p\wedge b}{a\wedge b}=-1$

$\beta = \frac{a\wedge p}{a\wedge b}= 3$

Therefore $p=-a+3b$ so the inhomogeneous solution is $x^{1}= (-1,3,0)$ Now to determine the space of homogeneous solutions, the vector $c$ get's decomposed into a linear combination of $a$ and $b$ again by Cramer's rule. This gives $c=-\frac{1}{2}a+b$ And the space of homogeneous solutions is given by the span of $x_{i}^{(0)(1)}=(-\frac{1}{2},1,-1)$. So the general solution is

$x_{i}=x_{i}^{1}+ \beta x_{i}^{(0)(1)}= (-1-\frac{1}{2}\beta, 3+\beta, -\beta)$

Then he gives another example with a non-square system

$x+y=1$

$y+z=1$

And the general solution is $x_{i}=(1,0,1)+\alpha (1,-1,1)$ (with no explanation).

I don't see a pattern here. What is going on?

Answer 1

OK. I'll try to explain the first example for you.

Our task is to solve the system of linear equations: $\begin{cases}2x+y=1 \\ 2x+2y+z=4 \\ y+z=3 \end{cases}$

Said another way, we're trying to find the space of vectors $(x,y,z)$ that get mapped to $\vec p = (1,4,3)$ under the given transformation $T$. That is: $T(x,y,z) = x(2,2,0) + y(1,2,1) + z(0,1,1) = (1,4,3) = \vec p$.

---

First, for reference, let's see how we'd do it using matrix algebra.

So let's use Gauss-Jordan elimination: $$ \left[\begin{array}{ccc|c} 2 & 1 & 0 & 1 \\ 2 & 2& 1 & 4 \\ 0 & 1 &1 & 3 \end{array} \right] \sim \left[\begin{array}{ccc|c} 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & 1 & 3 \end{array}\right] \sim \left[\begin{array}{ccc|c} 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 0 & 0 \end{array}\right]$$

Let's then set $z=t$ for some arbitrary value $t \in \Bbb R$. Then $y=3-t$ and $x=\frac 12(1-y) = \frac 12 (1-3+t) = -1+\frac 12 t$. So our general solution is $\vec x = \begin{bmatrix} -1 + \frac 12 t \\ 3-t \\ t\end{bmatrix}$. Which we can see is equivalent to the answer Dr. Winitzki got by the change of variable $t \mapsto -\beta$.

---

Now, let's try to do this with exterior algebra and Cramer's rule.

We need to first note that there is a theorem in linear algebra which says that the solution to a system of linear equations is the sum of any particular solution with the general solution to the corresponding homogeneous set of equations.

That is, if you have some transformation $T(x,y,z)=(1,4,3)$, then knowing some particular vector $(x_0,y_0,z_0)$ which transforms into $(1,4,3)$ via this transformation and the general solution to the related problem $T(t,u,v)=(0,0,0)$, your solution set will be $(x_0+t,y_0+u,z_0 + v)$.

So our first task is to find a vector $(x_0,y_0,z_0)$ that solves this system.

We first note that $\vec p \in \vec a \wedge \vec b$ because $x\vec a + y \vec b + z \vec c = \vec p \iff \vec p \in \text{span}(\vec a, \vec b, \vec c)$, but we know that $\text{span}(\vec a, \vec b, \vec c)=\text{span}(\vec a, \vec b)$ because $\vec a \wedge \vec b \wedge \vec c = 0$ and $\vec a \wedge \vec b \ne 0$. We also know that $\text{span}(\vec a, \vec b)$ is representable by $\vec a \wedge \vec b$.

Thus $\vec p = \alpha \vec a + \beta \vec b$ for some scalars $\alpha$ and $\beta$.

You will see why Cramer's rule works by simply taking the exterior product of that last equation with $\vec a$ and $\vec b$: $\ \vec p\wedge \vec b = (\alpha \vec a + \beta \vec b)\wedge \vec b = \alpha \vec a \wedge \vec b + \beta \vec b \wedge \vec b= \alpha \vec a \wedge \vec b + 0=\alpha \vec a \wedge \vec b$. Then dividing by $\vec a \wedge \vec b$ on the far left and far right sides gives $\alpha = \frac{\vec p\wedge \vec b}{\vec a \wedge \vec b}$. $\ \beta$ can be found similarly. Thus $\vec p=-\vec a+3\vec b=x_0\vec a + y_0\vec b + z_0\vec c$.

So now we've found $\vec x_p=(-1,3,0)$ which is a particular solution to our system. Note here that Cramer's rule is not powerful enough to get us EVERY solution to our system, but it can find us $1$ (assuming there is at least $1$).

Now we need the homogeneous solution. This means we need to find the solution to : $\begin{cases}2x+y=0 \\ 2x+2y+z=0 \\ y+z=0 \end{cases}\ \ \ \ $ Equivalently, we need to solve $x\vec a + y\vec b + z\vec c =0$.

But we know that $\vec c$ is a linear combination of vectors $\vec a$ and $\vec b$. We can then use the exact same method to determine that $\vec c = -\frac 12 \vec a + \vec b$.

Adding $-\vec c$ to both sides we get $-\frac 12 \vec a + \vec b -\vec c =0$. So apparently one solution is $(x,y,z)=(-\frac 12, 1, -1)$. From the rank-nullity theorem, we know that our homogeneous solution (AKA nullspace) is $1$-dimensional, so now that we've found $1$ solution, we know that all others will be a scalar multiple of that one.

So our general homogeneous solution is $\beta (-\frac 12, 1, -1)$, for some arbitrary $\beta \in \Bbb R$.

Putting this together with the particular solution we already found, we find that the general solution to the system of equations: $\begin{cases}2x+y=1 \\ 2x+2y+z=4 \\ y+z=3 \end{cases}\ \ \ $ is $(x,y,z) = (-1,3,0) + \beta(-\frac 12, 1, -1)$, which is just what we found from our matrix methods. Yay!