5
$\begingroup$

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.

  • 0
    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?2012-01-10

1 Answers 1

1

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.