58
$\begingroup$

The following is a well-known result in functional analysis:

If the vector space $X$ is finite dimensional, all norms are equivalent.

Here is the standard proof in one textbook. First, pick a norm for $X$, say $$\|x\|_1=\sum_{i=1}^n|\alpha_i|$$ where $x=\sum_{i=1}^n\alpha_ix_i$, and $(x_i)_{i=1}^n$ is a basis for $X$. Then show that every norm for $X$ is equivalent to $\|\cdot\|_1$, i.e., $$c\|x\|\leq\|x\|_1\leq C\|x\|.$$ For the first inequality, one can easily get $c$ by triangle inequality for the norm. For the second inequality, instead of constructing $C$, the Bolzano-Weierstrass theorem is applied to construct a contradiction.

The strategies for proving these two inequalities are so different. Here is my question,

Can one prove this theorem without Bolzano-Weierstrass theorem?

UPDATE:

Is the converse of the theorem true? In other words, if all norms for a vector space $X$ are equivalent, then can one conclude that $X$ is of finite dimension?

$\endgroup$
  • 2
    $\begingroup$ It's not really different from Bolzano-Weierstrass, but we can use the compacity of $\left\{x\in X, \lVert x\rVert =1\right\}$ and the fact that the map $x\mapsto \lVert x\rVert_0$ is continuous. $\endgroup$ – Davide Giraudo Aug 15 '11 at 22:03
  • 4
    $\begingroup$ Well, Bolzano-Weierstrass is essentially equivalent to compactness of the unit ball with respect to the norm which you call $\|\cdot\|_0$ and everyone else I know calls $\|\cdot\|_1$. See also Fabian's proof here where the maximum norm is used. $\endgroup$ – t.b. Aug 15 '11 at 22:10
  • 1
    $\begingroup$ I'm not really talking about the unit ball directly :) Starting at "Now" I argue why a bounded set $S$ contains a convergent subsequence: If $S$ is bounded and $v_n \in S$ then using Bolzano-Weierstrass I can extract a subsequence that converges coordinate-wise, hence with respect to $\|\cdot\|_1$. If $S$ is in addition closed, then the limit point will belong to $S$. Does that help? $\endgroup$ – t.b. Aug 16 '11 at 1:43
  • 5
    $\begingroup$ Side note: if $F$ is a field with absolute value, then it makes sense to define a norm on an $F$-vector space. If $F$ is complete, then the same theorem is true: for a finite-dimensional vector space all norms are equivalent. Note: compactness is not available for the proof! 2nd note: this theorem may fail if $F$ is not complete. $\endgroup$ – GEdgar Aug 16 '11 at 14:51
  • 1
    $\begingroup$ A reference for the statement mentioned by GEdgar would be Section 5 of Paul Garrett's notes on topological vector spaces. As GEdgar says no compactness is needed, but completeness is essential, as he outlines in his answer on MO. However, the notes don't prove that any two norms are equivalent, but this can also be shown. $\endgroup$ – t.b. Aug 16 '11 at 23:09
36
$\begingroup$

To answer the question in the update:

If $(X,\|\cdot\|)$ is a normed space of infinite dimension, we can produce a non-continuous linear functional: Choose an algebraic basis $\{e_{i}\}_{i \in I}$ which we may assume to be normalized, i.e., $\|e_{i}\| = 1$ for all $i$. Every vector $x \in X$ has a unique representation $x = \sum_{i \in I} x_i \, e_i$ with only finitely many nonzero entries (by definition of a basis).

Now choose a countable subset $i_1,i_2, \ldots$ of $I$. Then $\phi(x) = \sum_{k=1}^{\infty} k \cdot x_{i_k}$ defines a linear functional on $x$. Note that $\phi$ is not continuous, as $\frac{1}{\sqrt{k}} e_{i_k} \to 0$ while $\phi(\frac{1}{\sqrt{k}}e_{i_k}) = \sqrt{k} \to \infty$.

There can't be a $C \gt 0$ such that the norm $\|x\|_{\phi} = \|x\| + |\phi(x)|$ satisfies $\|x\|_\phi \leq C \|x\|$ since otherwise $\|\frac{1}{\sqrt{k}}e_k\| \to 0$ would imply $|\phi(\frac{1}{\sqrt{k}}e_k)| \to 0$ contrary to the previous paragraph.

This shows that on an infinite-dimensional normed space there are always inequivalent norms. In other words, the converse you ask about is true.

$\endgroup$
  • 1
    $\begingroup$ Aha! But now: is it consistent with ZF that there is some infinite-dimensional vector space where all norms are equivalent... $\endgroup$ – GEdgar Aug 16 '11 at 12:14
  • $\begingroup$ @GEdgar: Apparently I was too obviously trying to avoid that question... Short answer: I don't know. $\endgroup$ – t.b. Aug 16 '11 at 12:41
  • $\begingroup$ @GEdgar Apparently there isn't any contradiction. Note that $\|\cdot\|_\phi$ is defined not on $X$, but on a subspace of $X$ that has a countable basis. $\endgroup$ – user1551 Dec 19 '12 at 3:35
  • $\begingroup$ @GEdgar Is it true in ZF that all infinite dimensional vector space can be given a norm.(Then only we can talk about your question otherwise an infinite dimensional vector space which doesn't have norm will trivially satisfy the condition)? I don't know whether we can define norm on each vector space in ZF, Please tell $\endgroup$ – Sushil Jul 8 '15 at 10:33
  • $\begingroup$ @t.b. can we prove in ZF only that countable no. of linearly independent vectors in a infinite dimensional vector space,(Because any set of finite vectors can't be maximal linearly independent set, right?) $\endgroup$ – Sushil Jul 8 '15 at 13:18
12
$\begingroup$

You are going to need something of this nature. A Banach Space is a complete normed linear space (over $\mathbb{R}$ or $\mathbb{C}$). The equivalence of norms on a finite dimensional space eventually comes down to the facts that the unit ball of a Banach Space is compact if the space is finite-dimensional, and that continuous real-valued functions on compact sets achieve their sup and inf. It is the Bolzano Weirstrass theorem that gives the first property.

In fact, a Banach Space is finite dimensional if and only if its unit ball is compact. Things like this do go wrong for infinite-dimensional spaces. For example, let $\ell_1$ be the space of real sequences such that $\sum_{n=0}^{\infty} |a_n| < \infty $. Then $\ell_1$ is an infinite dimensional Banach Space with norm $\|(a_n) \| = \sum_{n=0}^{\infty} |a_n|.$ It also admits another norm $\|(a_n)\|' = \sqrt{ \sum_{n=0}^{\infty} |a_{n}|^2}$ , and this norm is not equivalent to the first one.

$\endgroup$
  • $\begingroup$ Apparently there are some generalizations -- see this MO-thread. Admittedly I was unable to follow the discussion (but I didn't really bother to try). I'm happy with what paul garrett explained there. $\endgroup$ – t.b. Aug 15 '11 at 22:18
  • $\begingroup$ In that MO thread @Theo B. mentions, the questioner was apparently as much interested in very weak hypotheses on the topological field... didn't want it to have a topology defined by a norm, etc. All those complications (which I barely followed) are irrelevant to the present question. $\endgroup$ – paul garrett Aug 15 '11 at 22:35
  • $\begingroup$ @both: yes, the other thread seems to deal with issues which I don't normally worry about. $\endgroup$ – Geoff Robinson Aug 15 '11 at 23:05
  • $\begingroup$ How do you know that every finite dimensional normed space is Banach? $\endgroup$ – André Caldas Feb 3 '13 at 21:51
  • $\begingroup$ @Andre: You know that because the equivalence of norms on a f.d. space gives isomorphism to $\mathbb{R}^{n}$, with the usual normal $\|(x_{1},\ldots ,x_{n}) \| = \sum_{i=1}^{n}|x_{i}|.$ The proof of this only uses completeness of $\mathbb{R}^{n}$ with respect to this norm- it does not assume completeness of the other space. $\endgroup$ – Geoff Robinson Feb 4 '13 at 2:21
8
$\begingroup$

Here's a proof of the equivalence of norms in finite dimension that does not use compactness arguments. It breaks down into three steps.

We set some notation first: given a normed finite dimensional real vector space $E$, write $E'$ for its algebraic dual space (set of all linear forms) and $E^{*}$ for its topological dual space (set of all continuous linear forms).

  • All linear forms on $E$ are continuous, i.e $E'=E^{*}$, whatever the norm $\|.\|$ on $E$.

The Hahn-Banach theorem states that every continuous form on a subspace of $E$ can be extended to all of $E$. In particular, given $x\in E$, there is a $\varphi:E\rightarrow \mathbb{R}$ for which $\varphi(x)\neq 0$, since there are non trivial forms $\mathbb{R}x\rightarrow \mathbb{R}$ and these can be extended. As a consequence, the map \begin{align*} E &\rightarrow (E^{*})' \\ x &\mapsto (\phi\rightarrow \phi(x)) \end{align*} is injective. We also have isomorphisms $E'\simeq E$ and $E^{*}\simeq (E^{*})'$. Composing the three maps we have an injection $E' \rightarrow E^{*}$ so that $\dim E' \leqslant \dim E^{*}$. On the other hand since $E^{*}\subset E'$ we must have $\dim E^{*}=\dim E'$ and $E^{*}=E'$ as desired.

  • All linear maps between finite dimensional normed spaces are continuous.

Let $A:F\rightarrow E$ be such a map and $e_{i},i\in I$ a basis for $E$. Let $(e_{i}^{*})$ be the dual basis of $(e_{i})$ and $\tilde{e_{i}}$ the linear map $\mathbb{R}\rightarrow E$ that maps $1$ to $e_{i}$. Then $Id_{E}=\sum_{i\in I}\tilde{e_{i}}e_{i}^{*}$. In particular, $A=\sum \tilde{e_{i}}e_{i}^{*}A$. The the $\tilde{e_{i}}$ are continuous and so are the $e_{i}^{*}A$, since they are linear forms. Hence $A$ is continuous as a sum of composites of continuous maps.

  • All norms are equivalent.

Given two norms $\|.\|_{1}, \|.\|_{2}$ on $E$, the identity, being linear, defines an homeomorphism between $E,\|.\|_{1}$ and $E,\|.\|_{2}$. It is easy to check that this means that the norms are equivalent.

This proof is really a way of saying that the topology induced by a norm on a finite-dimensional vector space is the same as the topology defined by open half-spaces; in particular, all norms define the same topology and all norms are equivalent. There are other ways to prove that using the Hahn-Banach theorem.

$\endgroup$
6
$\begingroup$

One doesn't really need a different argument for each side of the inequality. If $\vert\vert \cdot \vert\vert_1,\vert\vert \cdot \vert\vert_2$ are two norms on a finite-dimensional vector space (over $\mathbb{R}$ or $\mathbb{C}$), then the restriction of $\vert\vert \cdot \vert\vert_1$ to the closed unit ball of $\vert\vert \cdot \vert\vert_2$ is a continuous function on a compact set (here the finite-dimensionality is used) and is therefore bounded from above by some $M > 0$. By positive homogeneity, it follows that $\vert\vert \cdot \vert\vert_1 \le M \vert\vert \cdot \vert\vert_2$. Switching the roles of $\vert\vert \cdot \vert\vert_1$ and $\vert\vert \cdot \vert\vert_2$, you get $\vert\vert \cdot \vert\vert_2 \le m \vert\vert \cdot \vert\vert_1$, hence $\frac{1}{m} \vert\vert \cdot \vert\vert_2 \le \vert\vert \cdot \vert\vert_1$, for some $m>0$.

Don't take this theorem too seriously though. This kind of equivalence relation between norms is pretty weak and two normed spaces with $\mathbb{R}^n$ as the underlying vector space can be completely different as far as their geometry is concerned (for instance, some norms come from an inner product [hence satisfy the nice geometric property which we call the "Parallelogram law"] and some don't).

$\endgroup$
  • 4
    $\begingroup$ Hm. I'm not convinced. Isn't it much more cumbersome to prove that closed and bounded implies compact with respect to both norms than using the triangle inequality once? $\endgroup$ – t.b. Aug 16 '11 at 0:23
  • 1
    $\begingroup$ To add to that, you seem to be assuming that the norms are already continuous with respect to each other. How do you know that? $\endgroup$ – t.b. Aug 16 '11 at 0:35
  • 3
    $\begingroup$ I guess I was tacitly assuming that one knows that all normed topologies on $\mathbb{R}^n$ are the product topology. $\endgroup$ – Mark Aug 16 '11 at 3:05
  • $\begingroup$ @Mark Why do you mean by "all normed topologies on $\mathbb{R}^n$ are the product topology"? $\endgroup$ – Viktor Glombik Mar 24 at 11:52
3
$\begingroup$

Theorem. Let $X$ be a real or complex finite-dimensional vector space, and let $\lVert\cdot\lVert_a$ and $\lVert\cdot\lVert_b$ be norms on $X$. Then $\lVert\cdot\lVert_a$ and $\lVert\cdot\lVert_b$ are equivalent, in the sense that there are constants $C,D>0$ such that for every $x\in X$, $$C\lVert x\lVert_b\leqslant \lVert x\lVert_a\leqslant D\lVert x\lVert_b\,.$$

I really like this proof by Steven G. Johnson at MIT. It uses Heine–Borel though, so it's not really any more elementary than the proof described in the original post that uses Bolzano–Weirstras; but perhaps it's at least a little bit cleaner/neater.

It consists of making the following four observations (it's a good exercise to try to prove them yourself, before looking at Johnson's much more detailed write-up):

  1. Equivalence of norms is an equivalence relation. Hence, it's sufficient to show that every norm on $X$ is equivalent to $\lVert\cdot\rVert_1$, defined as in the original post.

  2. It's sufficient to consider $x\in X$ with $\Vert x\Vert_1=1$, i.e. $x$ that lie on the unit sphere $S=\{x\in X:\Vert x\Vert_1=1\}$.

  3. Every norm $\lVert\cdot\rVert$ on $X$ is continuous with respect to $\lVert\cdot\rVert_1$.

  4. By Heine–Borel, the sphere $S$ is compact with respect to $\lVert\cdot\rVert_1$, and so, by the extreme value theorem, $\lVert\cdot\rVert$ must attain a minimum $m$ and a maximum $M$ on $S$.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by every norm being continuous with respect to $\| \cdot \|_1$? $\endgroup$ – Viktor Glombik Mar 24 at 11:48
  • 1
    $\begingroup$ Let $X$ be a finite-dimensional real or complex vector space with some fixed basis $\mathcal{B}$, and let $\lVert\cdot \lVert$ be an arbitrary norm on $X$. What I claim is that if we equip $X$ with the metric induced by $\lVert\cdot\lVert_1$ (the 1-norm with respect to $\mathcal{B}$), then the function $\lVert\cdot\lVert\colon X\to\mathbb{R}$ becomes continuous. In other words: for any $x_0\in X$ and any $\varepsilon>0$ we can find a $\delta>0$ such that $$\lVert x-x_0\lVert_1<\delta\Longrightarrow \big\lvert\, \lVert x\lVert-\lVert x_0\lVert\,\big\lvert<\varepsilon\,.$$ $\endgroup$ – Oskar Henriksson Mar 24 at 22:24
2
$\begingroup$

Here's another answer to the question in the update. It's inspired by Geoff's answer and similar to tb's. tb's is superior in the sense that it shows how to construct unbounded linear functional on any infinite dimensional space. However, one might prefer the answer here because it just exhibits two very natural norms and shows they are inequivalent.

Let $X$ be an infinite dimensional space with basis $\{e_i\}_{i \in I}$. Each $x \in X$ has a unique representation of the form $x = \sum_{i \in I} c_i e_i$ with $c_i = 0$ for all but finitely many $i$. Define $\|x\|_1 = \sum_{i \in I} |c_i|$ and $\|x\|_{\infty} = \max_{i \in I} |c_i|$. It's easy to check these are indeed norms. For each $N \in \mathbb{N}$, there is an $x \in X$ such that $\|x\|_1 > N \| x \|_{\infty}$. Indeed, $x = \sum_{i=1}^{N+1} e_i$ has $\|x\|_1=N+1$ and $\|x\|_{\infty}=1$. Thus $\|{}\cdot{} \|_1$ and $\|{}\cdot{} \|_{\infty}$ are inequivalent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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