Abstract Nonsense

Crushing one theorem at a time

Halmos Chapter one Sections 10, 11, and 12: Subspaces, Calculus of Subspaces, and Dimension of Subspaces


1.

Problem: If \mathcal{M} and \mathcal{N} are finite-dimensional subspace with the same dimension n, and \mathcal{M}\subseteq\mathcal{N}, then \mathcal{M}=\mathcal{N}

Proof: Suppose not, then there is some v\in\mathcal{N}-\mathcal{M}. Then, if \{x_1,\cdots,x_n\} is the finite basis for \mathcal{M} we claim that \{x_1,\cdots,x_n,v\} is l.i. in \mathcal{N}. To see this suppose that

\alpha_1 x_1+\cdots+\alpha_n x_n+\alpha v=\bold{0}\quad (1)

We may conclude that \alpha=0 otherwise

\displaystyle v=\frac{-\alpha_1}{\alpha}x_1+\cdots+\frac{-\alpha_n}{\alpha} x_n\implies v\in\text{Span }\{x_1,\cdots,x_n\}=\mathcal{M}

and thus \alpha=0.  Thus, (1) may be rewritten as

\alpha_1x_1+\cdots+\alpha_n x_n=\bold{0}

and thus by the l.i. of \{x_1,\cdots,x_n\} we see that this implies that \alpha_1=\cdots=\alpha_n=0 and so \{x_1,\cdots,x_n,\alpha\} is a l.i. set in \mathcal{N}, but this contradicts that \dim\mathcal{N}=n. Thus, there is no v\in\mathcal{N}-\mathcal{M} and so \mathcal{M}=\mathcal{N}

2.

Problem: If \mathcal{M} and \mathcal{N} are subspaces of a vector space \mathcal{V} and if every vector in \mathcal{V} belongs to either \mathcal{N} or \mathcal{M}, then either \mathcal{M}=\mathcal{V} or \mathcal{N}=\mathcal{V}

Proof: We prove the contrapositive, if \mathcal{M},\mathcal{N} are subspaces of \mathcal{V} such that neither equal \mathcal{V} then \mathcal{M}\cup\mathcal{N}\subsetneq\mathcal{V}. To prove this, suppose not and \mathcal{M}\cup\mathcal{N}=\mathcal{V}. We first see by the condition that \mathcal{M},\mathcal{N}\ne\mathcal{V} that there are v\notin\mathcal{M} and w\notin\mathcal{N}. Now, since \mathcal{M}\cup\mathcal{N}=\mathcal{V} we can easily see that v\in\mathcal{N} and w\in\mathcal{M}, but where is v+w? If v+w\in\mathcal{M} then by virtue of \mathcal{M} being a subspace, so is (v+w)+(-w)=v which contradicts our assumption that v\notin\mathcal{M}. Similarly, v+w\in\mathcal{N}\implies (v+w)+(-v)=w\in\mathcal{N}. Thus, v+w\notin\mathcal{M}\cup\mathcal{N}=\mathcal{V} which is a contradiction. It follows that \mathcal{N}\cup\mathcal{M}\ne\mathcal{V}

3.

Problem: If x,y and z are vectors such that x+y+z=\bold{0}, then x and y span the same subspace as y and z

Proof: We are attempting to show that \text{Span }\{x,y\}=\text{Span }\{y,z\}. To see this, let v\in\text{Span }\{x,y\} then there exists \alpha_1,\alpha_2\in F such that \alpha_1x+\alpha_2y=v, but notice that x+y+z=0\implies -(y+z)=x and so this last equation may be restated as -\alpha_1(z+y)+\alpha_2=-\alpha_1z+(\alpha_2-\alpha_1)y=v. Thus, v\in\text{Span }\{y,z\}. Similarly, x+y+z=0\implies z=-(x+y) and so \alpha_1z+\alpha_2y=-\alpha_1 x+(\alpha_2-\alpha_2)y and so a similar reasoning may be applied. Of course, both of these sets equal \text{Span }\{x,z\}

Remark: One can clearly see how this extends to general linearly dependent sets.

4.

Problem: Suppose that x and y are vectors and \mathcal{M} is a subspace in a vector space \mathcal{V}; let \mathcal{H} be the subspace spanned by\mathcal{M} and x, and let \mathcal{K} be the subspace spanned by \mathcal{M} and y. Prove that if y\in\mathcal{H} but not in \mathcal{M} then x\in\mathcal{K}

Proof: Let \{x_1,\cdots,x_n\} be a basis for \mathcal{M}, then by y\in\mathcal{H} we know there exists \alpha_1,\cdots,\alpha_{n+1} such that y=\alpha_1x+\cdots+\alpha_n x_n+\alpha_{n+1}x. Now, if \alpha_{n+1}=0 we may rewrite this equation as y=\alpha_1x_1+\cdots+\alpha_n x_n which implies that y\in\text{Span }\{x_1,\cdots,x_n\}=\mathcal{M}, which it assumed not to. Thus, \alpha_{n+1}\ne 0 and thus

\displaystyle x=\frac{-\alpha_1}{\alpha_{n+1}}x_1+\cdots+\frac{-\alpha_{n}}{\alpha_{n+1}}x_n+\frac{1}{\alpha_{n+1}}y

which states precisely that

x\in\text{Span }\{x_1,\cdots,x_n,y\}=\mathcal{K}

Remark: We’ve tacitly assumed something here which I’ll prove as a technical lemma, namely:

Lemma: Let \mathcal{M} be a finite dimensional subspace of a vector space \mathcal{V} with a basis \{x_1,\cdots,x_n\} then

\text{Span }\left(\mathcal{M}\cup\{v\}\right)=\text{Span }\{x_1,\cdots,x_n,v\}

for any v\in\mathcal{V}

Proof: Recall that

\displaystyle \text{Span }\left(\mathcal{M}\cup\{x\}\right)=\bigcap_{\underset{\mathcal{M}\cup\{v\}\subseteq\mathcal{S}}{\mathcal{S}\sqsubseteq\mathcal{V}}}\mathcal{S}

(where \sqsubseteq means ” is a subspace of”). Thus, noting that

\text{Span }\left\{x_1,\cdots,x_n,v\right\}\sqsubseteq\mathcal{V}\text{ and }\mathcal{M}\cup\{v\}\subseteq\text{Span }\{x_1,\cdots,x_n,v\}

we see from the definition that

\text{Span }\left(\mathcal{M}\cup\{v\}\right)\subseteq\text{Span }\{x_1,\cdots,x_n,v\}

conversely, to show the opposite inclusion holds it suffices to prove that

\text{Span }\{x_1,\cdots,x_n,v\}\subseteq\mathcal{S}

for a fixed but arbitrary subspace containing \mathcal{M}\cup\{v\}. But, this is immediate since any subspace containing \mathcal{M}\cup\{v\} contains not only \{x_1,\cdots,x_n,v\} but all of the possible linear combinations, and so the above inclusion holds. Thus,

\displaystyle \text{Span }\{x_1,\cdots,x_n,v\}\subseteq\bigcap_{\underset{\mathcal{M}\cup\{v\}}{\mathcal{S}\sqsubseteq\mathcal{V}}}\mathcal{S}=\text{Span }\left(\mathcal{M}\cup\{v\}\right)

from where the conclusion follows.

5.

Problem: Suppose that \mathcal{L},\mathcal{M}, and \mathcal{N} are subspaces of a vector space \mathcal{V}.

a) Show that the equation

\mathcal{L}\cap\left(\mathcal{M}+\mathcal{N}\right)=\left(\mathcal{L}\cap\mathcal{M}\right)+\left(\mathcal{L}\cap\mathcal{N}\right)

isn’t necessarily true.

b) Prove that

\mathcal{L}\cap\left(\mathcal{M}+\left(\mathcal{L}\cap\mathcal{N}\right)\right)=\left(\mathcal{L}\cap\mathcal{M}\right)+\left(\mathcal{L}\cap\mathcal{N}\right)

Proof:

a) Consider \mathbb{R}^3 as a vector space and consider the three subspaces of \mathbb{R}^3 over \mathbb{R}

\mathcal{L}=\left\{(\alpha,0,0):\alpha\in\mathbb{R}\right\}

\mathcal{M}=\left\{(\beta,\beta,0):\beta\in\mathbb{R}\right\}

and

\mathcal{N}=\left\{(0,\gamma,0):\gamma\in\mathbb{R}\right\}

Notice that

\mathcal{L}\cap\mathcal{M}=\mathcal{L}\cap\mathcal{N}=\{(0,0,0)\}

But, since (1,1,0)\in\mathcal{M} and (0,-1,0)\in\mathcal{N} we see that (1,1+-1,0)=(1,0,0)\in\mathcal{M}+\mathcal{N} and so \mathcal{L}\cap\left(\mathcal{M}+\mathcal{N}\right) is not trivial.

b) Let v\in\mathcal{L}\cap\left(\mathcal{M}+\left(\mathcal{L}\cap\mathcal{N}\right)\right) then v\in\mathcal{L} and v=x+y for some x\in\mathcal{M} and some y\in\mathcal{L}\cap\mathcal{N}. But, since y,v\in\mathcal{L} and x=v-y we see that x\in\mathcal{L}. Thus, x\in\mathcal{L}\cap\mathcal{M} and so v=x+y where x\in\mathcal{M}\cap\mathcal{L} and y\in\mathcal{L}\cap\mathcal{N} and so v\in\left(\mathcal{L}\cap\mathcal{M}\right)+\left(\mathcal{L}\cap\mathcal{N}\right)

Conversely, let v\in\left(\mathcal{L}\cap\mathcal{M}\right)+\left(\mathcal{L}\cap\mathcal{M}\right), then v=x+y where x\in\mathcal{L}\cap\mathcal{M} and y\in\mathcal{L}\cap\mathcal{N}. But, since v is the sum of two elements of \mathcal{L}, which is a subspace we immediately see that v\in\mathcal{L}. But, with the same credence we can can see that x\in\mathcal{M} so that v=x+y where x\in\mathcal{M} and y\in\mathcal{L}\cap\mathcal{N}, thus v\in\mathcal{M}+\left(\mathcal{L}\cap\mathcal{N}\right). Putting this together we get that v\in\mathcal{L}\cap\left(\mathcal{M}+\left(\mathcal{L}\cap\mathcal{N}\right)\right).

The conclusion follows.

6.

Problem:

a) Can it happen that a non-trivial subspace of a vector space \mathcal{V} has a unique complement?

b) If \mathcal{M} is an m-dimensional subspace of an n-dimensional vector space, then every complement \mathcal{N} of \mathcal{M} has dimension n-m

Proof:

a) Yes,there are lots of examples ;). In fact, if

b) By assumption we have that \mathcal{M} and \mathcal{N} are subspaces of \mathcal{V} and so we know there exists bases \{x_1,\cdots,x_m\} and \{y_1,\cdots,y_k\} for \mathcal{M} and \mathcal{N} respectively. We will show that \{x_1,\cdots,x_m,y_1,\cdots,y_k\} is a basis for \mathcal{V}. To see this suppose that

\displaystyle \sum_{i\leqslant n}\alpha_i x_i+\sum_{i\leqslant k}\beta_i y_i=\bold{0}

then

\displaystyle \sum_{i\leqslant n}\alpha_i x_i=\sum_{i\leqslant k}(-\beta_i)y_i

but the LHS is an element of \mathcal{M} and the RHS an element of \mathcal{N} and since \mathcal{M}\cap\mathcal{N}=\{\bold{0}\} it follows that

\displaystyle \sum_{i\leqslant n}\alpha_i x_i=\sum_{i\leqslant k}(-\beta_i)y_i=\bold{0}

and by the l.i. of \{x_1,\cdots,x_m\} and \{y_1,\cdots,y_k\} this implies that

\alpha_1=\cdots=\alpha_m=\beta_1=\cdots=\beta_k=0

from where l.i. follows. Now, the fact that

\text{Span }\{x_1,\cdots,x_m,y_1,\cdots,y_k\}=\mathcal{V}

is fairly clear. By assumption for every v\in\mathcal{V} there exists x\in\mathcal{M} and y\in\mathcal{N} such that

\displaystyle v=x+y=\sum_{i\leqslant m}\alpha_i x_i+\sum_{i\leqslant k}\beta_i y_,i,\quad \alpha_1,\cdots,\alpha_m,\beta_1,\cdots,\beta_k\in F

since

\text{Span }\{x_1,\cdots,x_m\}=\mathcal{M}\text{ and }\text{Span }\{y_1,\cdots,y_k\}=\mathcal{N}

It follows that \{x_1,\cdots,x_m,\cdots,y_1,\cdots,y_k\} is a basis for \mathcal{V} and so

\text{card }\{x_1,\cdots,x_m,y_1,\cdots,y_k\}=m+k=\dim_F\left(\mathcal{V}\right)=n

from where it follows that

\dim_F\left(\mathcal{N}\right)=k=n-m

7.

Problem:

a) Show that if both \mathcal{M},\mathcal{N} are three-dimensional subspaces of a five dimensional vecto space, then \mathcal{M} and \mathcal{N} are disjoint.

b) If \mathcal{M} and \mathcal{N} are finite dimensional subspaces of a vector space, then

\dim\left(\mathcal{M}+\mathcal{N}\right)=\dim\left(\mathcal{M}\right)+\dim\left(\mathcal{N}\right)-\dim\left(\mathcal{M}\cap\mathcal{N}\right)

Proof:

a)

Lemma: Let \mathcal{M},\mathcal{N} be subspaces of some vector space \mathcal{V}. Then, if \{x_1,\cdots,x_m\} and \{y_1,\cdots,y_n\} are respective bases then

\mathcal{M}+\mathcal{N}=\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)=\text{Span }\{x_1,\cdots,x_m,y_1,\cdots,y_n\}

Proof: We first prove that

\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)=\text{Span }\left\{x_1,\cdots,x_m,y_1,\cdots,y_n\right\}

To do this we first remember that

\mathcal{M}+\mathcal{N}\overset{\text{de}\text{f.}}{=}\left\{x+y:x\in\mathcal{M}\text{ and }y\in\mathcal{N}\right\}

and since evidently \text{Span }\left\{x_1,\cdots,x_m,y_1,\cdots,y_n\right\} a subspace of \mathcal{V} which contains \mathcal{M}\cup\mathcal{N} it is immediate that

\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)\subseteq\text{Span }\{x_1,\cdot,x_m,y_1,\cdots,y_n\}

Conversely, let v\in\text{Span }\{x_1,\cdots,x_m,y_1,\cdots,y_n\}. To show that \text{Span }\left(\mathcal{M}\cup\mathcal{N}\right) it suffices to show that v\in\mathcal{S} for a fixed but arbitrary subspace containing \mathcal{M}\cup\mathcal{N}. But, clearly \mathcal{M}\cup\mathcal{N}\subseteq\mathcal{S} implies that \{x_1,\cdots,x_m,y_1,\cdots,y_m\}\subseteq\mathcal{S}, but since \mathcal{S} is a subspace we see that any linear combination of elements of \{x_1,\cdots,x_m,y_1,\cdots,y_n\} is contained in S, in particular by definition v is a linear combination of such vectors and so v\in\mathcal{S}. The conclusion follows.

We now prove that

\mathcal{M}+\mathcal{N}=\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)

To see this, we first begin by remembering a definition, namely:

\displaystyle \text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)\overset{\text{de}\text{f.}}{=}\bigcap_{\underset{\mathcal{M}\cup\mathcal{N}\subseteq\mathcal{S}}{\mathcal{S}\sqsubseteq\mathcal{V}}}\mathcal{S}

To see this let v\in\mathcal{M}+\mathcal{N}, to show that v\in\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right) it suffices to show that v\in\mathcal{S} for a fixed but arbitrary subspace containing \mathcal{M}\cup\mathcal{N}, but this is immediate since v=x+y,\text{ }x,y\in\mathcal{M}\cup\mathcal{N} and so x,y\in\mathcal{S}, but since it’s a subspace x+y=v\in\mathcal{S}

Conversely, we merely note that \mathcal{M}+\mathcal{N} is a subspace which contains \mathcal{M}+\mathcal{N} and so by definition

\text{Span }\left(\mathcal{M}\cup\mathcal{N}\right)\subseteq\mathcal{M}+\mathcal{N}

and so the conclusion follows. \blacksquare

Lemma: Let \mathcal{M},\mathcal{N} be two subspace of \mathcal{V} (over F) with

\dim_F\left(\mathcal{M}\right)=m\text{ and }\dim_F\left(\mathcal{N}\right)=n

then if

\mathcal{M}\cap\mathcal{N}=\{\bold{0}\}

then \mathcal{M}+\mathcal{N} is a subspace and

\dim_F\left(\mathcal{M}+\mathcal{N}\right)=m+n

Proof: The fact that it’s a subspace is elementary, and clear thus it suffices to prove the second claim. To do this let \{x_1,\cdots,x_m\} and \{y_1,\cdots,y_n\} be bases for \mathcal{M} and \mathcal{N} respectively, we claim that \{x_1,\cdots,x_m,y_1,\cdots,y_n\} is a base for \mathcal{M}+\mathcal{N}. To do this suppose that

\displaystyle \sum_{j\leqslant m}\alpha_j x_j+\sum_{j\leqslant n}\beta_j y_j=\bold{0}

for some \alpha_1,\cdots,\alpha_m,\beta_1,\cdots,\beta_n\in F, then

\displaystyle \sum_{j\leqslant m}\alpha_j x_j=\sum_{j\leqslant n}\left(-\beta_j\right)y_j

but the LHS is an element of \mathcal{M} and the RHS an element of \mathcal{N} and so by assumption

\displaystyle \sum_{j\leqslant m}\alpha_j x_j=\sum_{j\leqslant n}\left(-\beta_j\right)y_j=\bold{0}

and so by the l.i. of \{x_1,\cdots,x_m\} and \{y_1,\cdots,y_n\} we see that

\alpha_1=\cdots=\alpha_m=\beta_1=\cdots=\beta_n=\bold{0}

and so \{x_1,\cdots,x_m,y_1,\cdots,y_n\} is l.i. Next, we note from the above that

\mathcal{M}+\mathcal{N}=\text{Span }\{x_1,\cdots,x_m,y_1,\cdots,y_n\}

and thus it follows that \{x_1,\cdots,x_m,y_1,\cdots,y_n\} is a basis for \mathcal{M}+\mathcal{N} and so in particular

\dim_F\left(\mathcal{M}+\mathcal{N}\right)=\text{card }\{x_1,\cdots,x_m,y_1+\cdots,y_n\}=m+n

thus the lemma is proven. \blacksquare

Corollary: Given an \ell-dimensional vector space \mathcal{V} and m,n-dimensional vector spaces \mathcal{M} and \mathcal{N} such that m+n>\ell then \mathcal{M}\cap\mathcal{N}\supsetneq\{\bold{0}\}

b) Let \{x_1,\cdots,x_m\} be a basis for \mathcal{M}\cap\mathcal{N}, then we may extend it to a basis \{x_1,\cdots,x_m,y_1,\cdots,y_k\} (where x_i\ne y_j,\text{ }\forall i,j)  for \mathcal{M} and a basis \{x_1,\cdots,x_m,z_1,\cdots,z_\ell\}( same condition) for \mathcal{N}. We claim that \{x_1,\cdots,x_m,y_1,\cdots,y_k,z_1,\cdots,z_\ell\} is a basis for \mathcal{M}+\mathcal{N}. It is evident that

\text{Span }\{x_1,\cdots,x_m,y_1,\cdots,y_k,z_1,\cdots,z_\ell\}=\mathcal{M}+\mathcal{N}

and so it suffices to prove l.i. Suppose that

\displaystyle \sum_{j\leqslant m}\alpha_j x_j+\sum_{j\leqslant k}\beta_j y_j+\sum_{j\leqslant \ell}\gamma_j z_j=\bold{0}

where not all the coefficients are zero. Now, clearly we must have that \beta_j\ne 0 and \gamma_i\ne 0 for some i,j since \{x_1,\cdots,x_m,y_1,\cdots,y_k\} and \{x_1,\cdots,x_m,z_1,\cdots,z_\ell\}  are l.i. Thus

\displaystyle \sum_{j\leqslant m}\alpha_j x_m+\sum_{j\leqslant \ell}\gamma_j z_j=\sum_{j\leqslant k}\beta_j y_j

and so there is some non-zero (considering what we just said) vector

v\in\text{Span }\{y_1,\cdots,y_k\}\cap\text{Span }\{x_1,\cdots,x_m,z_1,\cdots,z_\ell\}

But, this implies that v\in \mathcal{M}\cap\mathcal{N} and so v\in\text{Span }\{y_1,\cdots,y_k\}\cap\text{Span }\{x_1,\cdots,x_m\} and since the two sets are disjoint it follows that v=\bold{0} which is a contradiction. It follows that \{x_1,\cdots,x_m,y_1,\cdots,y_k,z_1,\cdots,z_\ell\} is a basis  for \mathcal{M}+\mathcal{N}. Note, that in particular this implies that y_j\ne z_i,\text{ }\forall i,j. So

\text{card }\{x_1,\cdots,x_m,y_1,\cdots,y_k\}+\text{card }\{x_1,\cdots,x_m,z_1,\cdots,z_\ell\}=m+k+m+\ell

(the last part using the disjointness of the sets), but this is equal to

m+k+\ell+m=\text{card }\{x_1,\cdots,x_m,y_1,\cdots,y_k,z_1,\cdots,z_\ell\}+\text{card }\{x_1,\cdots,x_m\}

But, noticing that m=\dim\left(\mathcal{M}\cap\mathcal{N}\right), m+k=\dim\mathcal{M}, m+\ell=\dim\mathcal{N}, and m+k+\ell=\dim\left(\mathcal{M}+\mathcal{N}\right) we may put this all together to get

\dim\mathcal{M}+\dim\mathcal{N}=\dim\left(\mathcal{M}+\mathcal{N}\right)+\dim\left(\mathcal{M}\cap\mathcal{N}\right)

as desired.

Advertisements

September 27, 2010 - Posted by | Fun Problems, Halmos, Linear Algebra | , , , , , , ,

2 Comments »

  1. Nice. What do you do when you can’t figure out how to prove something? Or does that never happen? : )

    Comment by Ragnarok | September 28, 2010 | Reply

  2. Ha! It happens a lot. When, it does I like to think about it. Do something else, you know. If I can’t I sometimes get impatient and look at the first line of a proof in a book or something haha.

    Comment by drexel28 | September 29, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: