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

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?

• What is the meaning of $p$ here? I can tell that $a, b, c$ are supposed to be normal vectors to the planes, but you state $p = (1,4,3)$ without explanation. – Muphrid Sep 16 '14 at 5:09
• Hi Muphrid, it's just a linear system of equations. Nothing special about (1,4,3). BTW: I'm doing this because I want to relearn analytic geometry and linear algebra with geometric algebra. If you know any source which explains this in more detail you can point me to it if you want. (the book from Macdonald doesn't help much, it's just a collection of problems without solutions). – JonnyPython Sep 16 '14 at 14:35
• I see. Well, in that case, I would recommend Dorst, Fontijne, and Mann. They go into a lot of detail about homogenous coordinates using geometric algebra, and their chapter on computing intersections of subspaces is very detailed. I can't recommend an approach using cramer's rule; it's essentially an algorithm for doing matrix inversion, which GA offers better alternatives for, and I feel computing the meet of blades is more direct. – Muphrid Sep 18 '14 at 19:50
• I actively avoid Cramer's rule (which while very useful for computer scientists is terribly inefficient for most pen and paper calculations), so I can't really explain how Dr. Winitzki used it to find the general solution. However just vanilla linear algebra works really quickly in this case. $x+y=1$ & $y+z=1$. So let $y=t$, then $x=1-t=z$. Thus your general solution is $(1-t,t,1-t)=(1,0,1)+t(-1,1,-1)$. – user137731 Sep 20 '14 at 15:22
• Or did you not understand the first example either? – user137731 Sep 20 '14 at 15:24

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!

• Hi, thank you very much ! I'll read through it. – JonnyPython Sep 26 '14 at 0:41
• @JonnyPython You should look at my corrected answer. I wasn't exactly right before. – user137731 Oct 18 '14 at 17:38
• Ok thx very detailed answer :) – JonnyPython Oct 18 '14 at 19:26