# Prove there is a homogeneous system of equations where solution is $M \subseteq \mathbb{R}^n$

So, I've been thinking of how to prove this. For example.

Let $\{(1, 1, 0, -1), (1, 0, 1, 2)\}$ be the base vectors of subspace $M \subseteq \mathbb{R}^4$.

One needs to show there is a system of linear equations where its solution would be equal to $M$.

The system solution to the example is

$$x_1 - x_2 - x_3 = 0$$

$$x_2 - 2x_3 + x_4 = 0 .$$

The process of the solution is next. Space $M$ can be described as a linear combination of its base vectors.

$$\alpha(1, 1, 0, -1) + \beta(1, 0, 1, 2)$$ This means that

$$x_1 = \alpha + \beta,~ x_2 = \alpha,~ x_3 = \beta,~ x_4 = -\alpha + 2\beta$$

From this one can derive the system whose coefficients can be put into a matrix.

$$\left( \begin{smallmatrix} 1&-1&-1&0&|&0\\ 0&1&-2&1&|&0 \end{smallmatrix} \right)$$

The solution is definitely equal to $M$.

How can one form a generalized proof?

-
You should explain how you arrived at $P = \begin{pmatrix} 1 & -1 & -1 & 0 \\ 0 & 1 & -2 & 1 \\ \end{pmatrix}$, And you most probably mean $\ker P = M$, i.e. $PX = 0 \iff x \in M$. –  Calvin Lin Jan 9 '13 at 1:10
@CalvinLin If I replace $\alpha$ and $\beta$ with $x_2$ and $x_3$ the system which is in the beginning of the question has exactly these coefficients which are then added to the matrix. I've edited the question again, each column before | represents a different variable of the system and the values are coefficients. –  Looft Jan 9 '13 at 1:13
Precisely, now you see why we can't generalize your solution. Because it replies on the chance fact that $x_2, x_3$ had no $\beta, \alpha$ (or $\gamma$ if you had another basis vector) accordingly. IF this is true in your generalized problem, that you can proceed. –  Calvin Lin Jan 9 '13 at 1:21
@CalvinLin Well, it needs to be true. Maybe there are solutions of other form but the problem asks of me only to provide one. I just can't seem to generalize my example. –  Looft Jan 9 '13 at 1:24
The generalization is what is listed below. What you found, i.e. $(1, -1, -1, 0)$ and $(0, 1, -2, 1)$ are orthogonal to your basis vectors, which means that the dot product is 0. The standard way to calculate orthogonal vectors is by Gram-Schmidth, though there are other brute force approaches too. –  Calvin Lin Jan 9 '13 at 1:30

Let $B=\{v_1,.., v_n \}$ be a basis for $M$. Complete $B$ to a basis $B \cup B'=\{v_1,.., v_n,v_{n-1},..,v_m \}$ of $\mathbb R^d$. use Gram Schmith to get a basis $\{ w_1,.,w_m \}$ of $\mathbb R^d$.

Then $M$ is the null space of the matrix whose colums are $w_{n+1},..,w_m$.

-

You need to find a basis for $M^\bot$. One way would be to apply Gram Schmidt to the vectors $(1, 1, 0, -1)^T, (1, 0, 1, 2)^T, e_1,...,e_4$, and use the last two non-zero vectors (which will span $M^\bot$).

Then if $M^\bot = \text{sp} \{ v_1,...,v_k \}$, you can write $M = \{x | v_i^T x = 0, i=1,...,k \}$.

In this case, $v_1 = (6,-7,-4,-1)^T$, $v_2 = (0 , 1, -2, 1)^T$ work (I modified the results to have nice integer coefficients).

-
I must admit I do not understand the answer. Maybe my question isn't clear? I have provided the solution for the example. The problem is simple, really simple, I'm just looking for the generalized proof. + Only undergraduate first semester linear algebra knowledge is in my posession. So, I've never heard of Gram Schmidt... –  Looft Jan 9 '13 at 0:18
The system for $M$ on line 3 shows the system of linear equations whose solution is $M$. –  copper.hat Jan 9 '13 at 0:20
Are you familiar with a way of finding a dual basis that is orthogonal to a given basis? –  copper.hat Jan 9 '13 at 0:23

Represent $M$ as a blade in the clifford algebra. Here, you have two vectors $u_1, u_2$ that span $M$. The bivector $u_1 \wedge u_2$ therefore represents this planar subspace.

One can then find the dual blade $M^*$, which is equal to $iM$, where $i$ is the pseudoscalar of the space.

Finally, one can construct a basis for $M^*$ through an orthonormalization procedure.

Example: let's take your two vectors $u_1 = e_1 + e_2 - e_4$ and $u_2 = e_1 + e_3 + 2 e_4$. The bivector $M$ is then

\begin{align*} M &= u_1 \wedge u_2 \\ &= e_1 e_3 + 2 e_1 e_4 + e_2 e_1 + e_2 e_3 + 2 e_2 e_4 - e_4 e_1 - e_4 e_3 \\ &=-e_1e_2 + e_1 e_3 + 3 e_1 e_4 + e_2 e_3 + 2 e_2 e_4 + e_3 e_4\end{align*}

Multiply by $i = e_1 e_2 e_3 e_4$, the pseudoscalar, to find the dual.

$$M^* = iM = e_3 e_4 + e_2 e_4 - 3 e_2 e_3 - e_1 e_4 + 2 e_1 e_3 - e_1 e_2$$

Now we need two vectors $b_1, b_2$ that will span the dual space. Try $b_1 = e_1 \cdot M^*$.

$$b_1 = e_1 \cdot M^* = -e_4 + 2 e_3 - e_2$$

Now find $b_2 = b_1 \cdot M^*$:

\begin{align*} b_2 &= (-e_4 + 2 e_3 - e_2) \cdot M^* \\ &= -e_4 + 3 e_3 - e_1 + 2 e_4 + 6 e_2 - 4 e_1 + e_3 + e_2 - e_1 \\ &= -6 e_1 + 7 e_2 + 4 e_3 + e_4\end{align*}

These vectors yield two equations:

\begin{align*} -x^2 + 2 x^3 - x^4 &= 0 \\ -6 x^1 + 7 x^2 + 4 x^3 + x^4 &= 0 \end{align*}

And as you can check yourself, these equations hold for any vector in $M$.

So, what we're doing is finding the dual space $M^*$ and just finding a basis for it. These basis vectors must be orthogonal to any vector in $M$.

-
I imagine that if one is sufficiently au fait with Clifford algebras to understand the above, then the original question would be somewhat moot. –  copper.hat Jan 9 '13 at 0:32
Admittedly, once I saw the OP was not familiar with Gram-Schmidt, I did feel pretty silly, but that was after I'd typed all this up. Alas. –  Muphrid Jan 9 '13 at 0:34
I misjudged that one too... –  copper.hat Jan 9 '13 at 0:35
I just thought there was a simpler solution. I mean, the solution for the example which I provided is extremely simple and requires minimal effort. The question asks for a generalization of that solution. –  Looft Jan 9 '13 at 0:41
@leolinus If you say that the solution for your examples is 'extremely simple and requires minimal effort', you should sketch out how your did it, without 'guess and check'. If you do have a process to approach the problem, it will be very difficult to generalize it –  Calvin Lin Jan 9 '13 at 0:50
show 1 more comment