Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently working through "An Introduction to Convex Polytopes" by Arne Brondsted and there is a question in the exercises that I would like a hint, or a nudge in the right direction, please no full solutions (yet)!

The question is as follows,

For any subset $M$ of $\mathbb{R}^d$, show that $\dim(\text{aff M}) = \dim(\text{span M})$ when $\textbf{0} \in \text{aff M}$, and $\dim(\text{aff M}) = \dim(\text{span M}) - 1$ when $\textbf{0} \notin \text{aff M}$.

My general approach thus far has been to try and interpret the dimension of the affine hull aff $M$ in terms of the affine basis of $M$ and the linear hull span $M$ in terms of the linear basis of $M$. I tried to prove a lemma

Let $L=(x_{1},...,x_{n})$ be the linear basis of $M$ and let $A=(x_{1},...,x_{k})$ be the affine basis of $M$. For any $M \subseteq \mathbb{R}^d$, $\dim(L)=\dim(\text{span M})=n$ and $\dim(A)=\dim(\text{aff M})=k-1$.

I'm fairly certain that it is true, but I'm having trouble coming up with a rigorous proof.

In any case, taking that lemma to be true I was able to come up with following attempt at a proof,

We are guaranteed that there exists a linearly independent n-family $(x_{1},...,x_{n})$ of vectors from $M$ such that $\text{span M}$ is the set of all linear combinations $\sum_{i=1}^{n} \lambda_{i}x_{i}$; and that there exists an affinely independent k-family of $(x_{1},...,x_{k})$ of points from $M$ such that $\text{aff M}$ is the set of all linear combinations $\sum_{i=1}^{k} \lambda_{i} x_{i}$, with $\sum_{i=1}^{k} \lambda_{i} = 1$. This is equivalent to saying that for any $M \subseteq \mathbb{R}^d$, there exists a linear basis $L=(x_{1},...,x_{n})$ of $M$ and there exists an affine basis $A=(x_{1},...,x_{k})$ of $M$. We show that when $\textbf{0} \in \text{aff M}$ that $\dim(\text{aff M}) = \dim(\text{span M})$ and that when $\textbf{0} \notin \text{aff M}$ that $\dim(A) = \dim(L)$. By the lemma, this is equivalent to saying when $\textbf{0} \in \text{aff M}$ that $\dim(A)=\dim(L)$ and that when $\textbf{0} \notin \text{aff M}$ that $\dim(A)= \dim(L) -1$. Assume that for an arbitrary $M \subseteq \mathbb{R}^d$ that $\textbf{0} \in \text{aff M}$. We want to prove that $\dim(A)=\dim(L)$. Since $A=(x_{1},...,x_{k})$ is an affine basis of $M$, $A$ has dimension $k-1$ and since $L=(x_{1},...,x_{n})$ is a linear basis of $M$, $L$ has dimension $n$. We show that $k-1=n$. Since $\textbf{0} \in \text{aff M}$, then some affine combination from $M$ is equal to the zero vector. So, for $\lambda_{1}+...+\lambda_{k}=1$ we have that, \begin{equation} \sum_{i=1}^{k} \lambda_{i} x_{i} =\sum_{i=1}^{k} \lambda_{i} \cdot \sum_{i=1}^{k} x_{i} = \sum_{i=1}^{k} x_{i} = 0 \end{equation} [From here somehow relate this to a property of linear dependence or something else that shows $k-1=n$]. Assume that for an arbitrary $M \subseteq \mathbb{R}^d$ that $\textbf{0} \notin \text{aff M}$. We want to prove that $\dim(A)=\dim(L)-1$, which is that $k-1 = n-1$, so $k=n$. [Try a similar approach to the first part if it ends up working and show that $k=n$]. Therefore, $\dim(\text{aff M}) = \dim(\text{span M})$ when $\textbf{0} \in \text{aff M}$, and $\dim(\text{aff M}) = \dim(\text{span M}) - 1$ when $\textbf{0} \notin \text{aff M}$.

I would appreciate some suggestions that have a fair bit of detail, but nothing like a full solution please. If you happen to be able to rip off a quick proof of the lemma I'd like to see that, and if it is wrong or useless please tell me!


EDIT: I realize my other approach was a bit off. From the suggestion Robert gave I was able to construct the outline of the proof (I just need to actually show that either $B$ or $B \cup \textbf{0}$ is an affine basis of aff $M$ depending on the condition) as follows,

Let $M$ be an arbitrary subset of $\mathbb{R}^d$. We want to show that if $\textbf{0} \in \text{aff M}$, then $\dim(\text{aff M}) = \dim(\text{span M})$ and that if $\textbf{0} \notin \text{aff M}$, then $\dim(\text{aff M}) = \dim(\text{span M}) - 1$. Since aff $M$ is an affine subspace of $\mathbb{R}^d$, then for an affine basis $A=(x_{1},...,x_{n})$ of aff $M$, $\dim(A)=\dim(\text{aff M})=n-1$. Similarly, since span $M$ is a linear subspace of $\mathbb{R}^d$, then for a linear basis $L=(x_{1},...,x_{n})$ of span $M$, $\dim(L)=\dim(\text{span M})=n$. So, we equivalently show for a linear basis $B$ of span $M$ that if $\textbf{0} \in \text{aff M}$, then $B \cup \{\textbf{0}\}$ is an affine basis for aff $M$ and that if $\textbf{0} \notin \text{aff M}$, then $B$ is an affine basis for aff $M$. Assume that $\textbf{0} \in \text{aff M}$ and that $B=(x_{1},...,x_{n})$ is a linear basis of span $M$. We want to prove that $B \cup \{\textbf{0}\}$ is an affine basis of aff $M$, since that would show $\dim(B \cup \{\textbf{0}\})=\dim(\text{aff M})=n$. Since $B$ is a linear basis of span $M$, then it would show that $\dim(B)=\dim(\text{span M})=n$, so we would have that $\dim(\text{aff M}) = \dim(\text{span M})$. [Show here that $B \cup \{\textbf{0}\}$ is an affine basis of aff $M$]. Assume that $\textbf{0} \notin \text{aff M}$ and that $B=(x_{1},...,x_{n})$ is a linear basis of span $M$. We want to prove that $B$ is an affine basis of aff $M$, since that would show $\dim(B)=\dim(\text{aff M})=n-1$. Since $B$ is a linear basis of span $M$, then it would show that $\dim(B)=\dim(\text{span M})=n$, so we would have that $\dim(\text{aff M})=\dim(\text{span M}) -1$. [Show here that $B$ is an affine basis of aff $M$]. Therefore, for any subset $M$ of $\mathbb{R}^d$, if $\textbf{0} \in \text{aff M}$ then $\dim(\text{aff M}) = \dim(\text{span M})$, and if $\textbf{0} \notin \text{aff M}$ then $\dim(\text{aff M}) = \dim(\text{span M}) - 1$.

Given that I can prove the condition for the affine basis in each case, would this be a complete proof? I'm still working on showing the condition, but I want to know if the construction of the proof is correct. Thanks!


SECOND EDIT: I have posted an attempted proof as an answer, please comment on it and let me know if it is correct.

share|improve this question
2  
Your lemma makes no sense because you're using the same letter $x$ for the members of both bases. Also don't say "the" linear basis and "the" affine basis: there are lots of both kinds of basis. What you might show is this. Suppose $B$ is a linear basis of $\text{span} M$. If $0$ is not in $\text{aff} M$, then $B$ is an affine basis for $\text{aff} M$, while if if $0$ is in $\text{aff} M$, then $B \cup \{0\}$ is an affine basis for $\text{aff} M$. –  Robert Israel Jan 8 '12 at 4:11
1  
@Robert Israel. Shouldn't you need to assume that $B \subset M$? –  a.r. Jan 9 '12 at 4:58
    
I've edited my proof and need help on one part when I'm assuming $\textbf{0} \notin \text{aff }M$. Could one you take a look at it? –  Samuel Reid Jan 10 '12 at 23:17

1 Answer 1

up vote 0 down vote accepted

Question: For any subset $M$ of $\mathbb{R}^d$, show that $\dim(\text{aff }M) = \dim(\text{span }M)$ when $\textbf{0} \in \text{aff }M$, and $\dim(\text{aff }M) = \dim(\text{span }M) - 1$ when $\textbf{0} \notin \text{aff }M$.

Attempted Proof:

Let $M$ be an arbitrary subset of $\mathbb{R}^d$. We want to show that $\dim(\text{aff }M) = \dim(\text{span }M)$ when $\textbf{0} \in \text{aff }M$, and $\dim(\text{aff }M) = \dim(\text{span }M) - 1$ when $\textbf{0} \notin \text{aff }M$.

Assume that $\textbf{0} \in \text{aff }M$ and let $A=(x_{1},...,x_{n})$ be an affine basis of aff $M$. Then, there exists an affine combination from $M$ that is equal to the zero vector. So, $\lambda_{1}x_{1} + ... + \lambda_{n}x_{n} = \textbf{0}$ with $\lambda_{1}+...+\lambda_{n}=1$. So, by the preclusion of $\lambda_{1}=...=\lambda_{n}=\textbf{0}$, we then have that $A$ is linearly dependent and so $\dim(\text{span }M) \leq n-1$. Yet, $A$ is an affine basis of aff $M$ and so $\dim(\text{aff }M)=n-1$. By definition, $\dim(\text{aff }M) \leq \dim(\text{span }M)$. Thus, $n-1=\dim(\text{aff }M)\leq \dim(\text{span }M) \leq n-1$. Therefore, $\dim(\text{aff }M)=\dim(\text{span }M)$.

Assume that $\textbf{0} \notin \text{aff }M$ and let $L=(x_{1},...,x_{n})$ be a linear basis of span $M$. Then, $L$ is linearly independent and $\dim(\text{span }M)=n$. Since the n-family $(x_{1},...,x_{n})$ of vectors from $L$ is linearly independent, $L$ is also affinely independent because any $(n-1)$-family $(x_{1},...,x_{n-1})$ of vectors from $L$ is linearly independent. Since $\text{aff }M \subseteq \text{span }M$, and $\textbf{0} \notin \text{aff }M$ then $\text{aff }M = \text{aff }L$. Thus, $L$ is an affine basis of aff $M$ and $\dim(\text{aff }M)=n-1$. Therefore, $\dim(\text{aff }M)=\dim(\text{span }M)-1$.

Therefore, for any subset $M$ of $\mathbb{R}^d$, we have that $\dim(\text{aff }M) = \dim(\text{span }M)$ when $\textbf{0} \in \text{aff }M$, and $\dim(\text{aff }M) = \dim(\text{span }M) - 1$ when $\textbf{0} \notin \text{aff }M$.

QED

The one point I feel I may not be justified in saying is,

Since $\text{aff }M \subseteq \text{span }M$, and $\textbf{0} \notin \text{aff }M$ then $\text{aff }M = \text{aff }L$.

I know that $\text{aff }M = \text{aff }L$ must be true when $\textbf{0} \notin \text{aff }M$, but I may not have given a sufficient explanation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.