# Every subspace of $\mathbb{R}^{n}$ has a complement

Exercise $2.41$ from Elon's book Algebra Linear (in Portuguese)

For all subspace $F\subset \mathbb{R}^{n}$, show that there exist a subspace $G\subset \mathbb{R}^{n}$ such that $\mathbb{R}^{n}=F\oplus G$.

The author haven't defined base so far. It is a basic Linear Algebra textbook, so I don't think I am supposed use the Zorn's Lemma.

I would appreciate any help.

-
In a finite dimensional space, any appeal to Zorn's lemma should reduce to a simple induction argument. –  Nate Eldredge Feb 3 '12 at 22:11

Consider the vectors $\mathbf{e}_1,\ldots,\mathbf{e}_n$.

1. If $\mathbf{e}_1\in F$, then discard. If $\mathbf{e}_1\notin F$, then keep.

2. Assuming you have made a decision about $\mathbf{e}_1,\ldots,\mathbf{e}_k$, $1\leq k\lt n$, then: if $\mathbf{e}_{k+1}$ can be written as a linear combination of an element of $F$ and $\mathbf{e}_1,\ldots,\mathbf{e}_k$, then discard $\mathbf{e}_{k+1}$. Otherwise, keep.

3. Repeat until we reach $\mathbf{e}_n$. Let $G$ be the subspace of $\mathbb{R}^n$ generated by the $\mathbf{e}_i$ that were kept.

Since every vector in $\mathbb{R}^n$ can be written as a linear combination of $\mathbf{e}_1,\ldots,\mathbf{e}_n$, by replacing any discarded $\mathbf{e}_i$, working from last to first, by linear combinations of a vector in $F$ and previous $\mathbf{e}_i$, we can see that $\mathbb{R}^n = F+G$.

If there is some element of $F$ that lies in $G$, express that element as a linear combination of the $\mathbf{e}_i$ that were kept; if any coefficient is not zero, then look at the largest one with nonzero coefficient: then we can express that $\mathbf{e}_k$ as an element of $F$ plus a linear combination of $\mathbf{e}_1,\ldots,\mathbf{e}_{k-1}$, contradicting the fact that we kept $\mathbf{e}_k$. Hence, $F\cap G = \{\mathbf{0}\}$.

(Yes, we are essentially using a "basis" behind the scenes.)

-