89
$\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$
11
  • 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$ Aug 15, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 23:09

8 Answers 8

45
$\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$
7
  • 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, 2011 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, 2011 at 12:41
  • 1
    $\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, 2012 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, 2015 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, 2015 at 13:18
15
$\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$
6
  • $\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, 2011 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$ Aug 15, 2011 at 22:35
  • $\begingroup$ @both: yes, the other thread seems to deal with issues which I don't normally worry about. $\endgroup$ Aug 15, 2011 at 23:05
  • $\begingroup$ How do you know that every finite dimensional normed space is Banach? $\endgroup$ Feb 3, 2013 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$ Feb 4, 2013 at 2:21
12
$\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$
3
  • 1
    $\begingroup$ What do you mean by every norm being continuous with respect to $\| \cdot \|_1$? $\endgroup$
    – Ramanujan
    Mar 24, 2019 at 11:48
  • 2
    $\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$ Mar 24, 2019 at 22:24
  • $\begingroup$ Thank you for sharing the link. Very neat proof! $\endgroup$
    – Bach
    Feb 11, 2020 at 16:33
11
$\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$
7
$\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
  • 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, 2011 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, 2011 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, 2011 at 3:05
  • $\begingroup$ @Mark Why do you mean by "all normed topologies on $\mathbb{R}^n$ are the product topology"? $\endgroup$
    – Ramanujan
    Mar 24, 2019 at 11:52
4
$\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$
0
$\begingroup$

Here is one approach, mentioned in Lang's analysis book.

Let $ V $ be an $ \mathbb{R} $-vector space with basis $ e_1 , \ldots, e_k $.

  • $ \| x_1 e_1 + \ldots + x_k e_k \|_\infty := \max\{ |x_1|, \ldots, |x_k| \} $ is a norm on $ V $.

  • $ \| \ldots \|_{\infty} $ makes $ V $ complete.

Let $ (v_j)_{j \geq 1} = (v_1, v_2, \ldots ) $ be a Cauchy sequence in $ V $. Exressing w.r.t basis vectors, $$ (v_1, v_2, \ldots ) = (e_1, e_2, \ldots, e_k) \begin{pmatrix} v_{11} &v_{12} &\ldots \\ v_{21} &v_{22} &\ldots \\ \vdots &\vdots &\ddots \\ v_{k1} &v_{k2} &\ldots \end{pmatrix}, \, \text{each }v_{ij} \in \mathbb{R} .$$ That is, $ v_{ij} $ is $ e_i $-coordinate of $ v_j $.
Notice sequence $ (v_{1j})_{j \geq 1} = (v_{11}, v_{12}, v_{13}, \ldots ) $ is Cauchy [because $ | v_{1n} - v_{1m} | \leq \| v_n - v_m \|_{\infty} $]. Similarly sequences $ (v_{1j}), (v_{2j}) , \ldots, (v_{kj}) $ are all Cauchy, hence convergent.
So let $ v_{1j} \to c_1, \ldots, v_{kj} \to c_k $ as $ j \to \infty $. Now $ v_j \to c_1 e_1 +\ldots + c_k e_k $ as $ j \to \infty $ [because $\| v_j - (c_1 e_1 + \ldots + c_k e_k) \|_\infty $ $ =\max \{ |v_{1j} - c_1| , \ldots, |v_{kj} - c_k | \} $ $ \to 0 $ as $ j \to \infty $], as needed.

  • Now let $ \| \ldots \| $ be any norm on $ V $. We'll try to show $ \| \ldots \| $ and $ \| \ldots \|_{\infty} $ are equivalent on $ V $, by induction on dimension $ k $ of the normed space. So lets assume $ \| \ldots \| $ and $ \| \ldots \|_{\infty} $ are equivalent on every proper subspace of $ V $.

  • Firstly, $$ \begin{align} \| x \| &= \| x_1 e_1 + \ldots + x_k e_k \| \\ &\leq |x_1| \| e_1 \| + \ldots + |x_k| \| e_k \| \\ &\leq \max \{|x_1 |, \ldots, |x_k|\} \left( \| e_1 \| + \ldots + \| e_k \| \right) \\ &= \| x \|_\infty C \end{align}$$ with $ C > 0 $.
    So we need only show $ \| x \|_\infty \leq D \| x \| $ for some $ D > 0 $.


Say there is no such $ D $. Then for every integer $ n > 0 $, there is a $ v_n $ with $ \| v_n \|_\infty > n \| v_n \| $.

Notice $ v_n \neq 0 $, i.e. each $ v_n $ has some non-zero coordinate.

So on defining $ w_n $ to be $ v_n $ divided by the coordinate of $ v_n $ with maximum absolute value, we have $ \| w_n \|_\infty = 1 $ and $ \| w_n \| = \| v_n \|_\infty ^{-1} \| v_n \| $ $\big($and hence $ \| w_n \| < \frac{1}{n} \big) $. Also each $ w_n $ has $ 1 $ as a coordinate.

Expressing sequence $ (w_n)_{n \geq 1} $ w.r.t basis vectors, $$ (w_1, w_2, \ldots ) = (e_1, e_2, \ldots, e_k) \begin{pmatrix} w_{11} &w_{12} &\ldots \\ w_{21} &w_{22} &\ldots \\ \vdots &\vdots &\ddots \\ w_{k1} &w_{k2} &\ldots \end{pmatrix}. $$ Every column has a $ 1 $, and every entry is $ \leq 1 $ in magnitude.

So there is a $ T \in \{ 1, 2, \ldots, k \} $ such that row $ w_{T 1}, w_{T 2}, \ldots $ has infinitely many $ 1 $s. Let $ J := \{ j : w_{T j} = 1 \} $ be the positions at which the $1$s occur in this row.

We'll now focus on sequence $ (w_j - e_T)_{j \in J} $.

Firstly, as $ (w_n)_{n \geq 1} $ itself converges to $ 0 $ w.r.t $ \| \ldots \| $, this sequence $ (w_j - e_T)_{j \in J} $ converges to $ (-e_T) $ w.r.t $ \| \ldots \| $.

Note the sequence $ (w_j - e_T)_{j \in J} $ lies in the subspace $ V_T := \{ x_1 e_1 + \ldots + x_k e_k : x_T = 0 \} $. It is also Cauchy in $ V_T $ w.r.t. $ \| \ldots \| $, because $ \| (w_n - e_T)-(w_m - e_T) \| = \| w_n - w_m\| $ $\leq \| w_n \| + \| w_m \| < \frac{1}{n} + \frac{1}{m}$.

But $ V_T $ is complete w.r.t $ \| \ldots \|_{\infty} $, and $ \| \ldots \| $ is equivalent to $ \| \ldots \|_{\infty} $ on $ V_T $. So $ V_T $ is complete w.r.t $ \| \ldots \| $. Hence $ (w_j - e_T)_{j \in J} $ must converge to a point in $ V_T $ w.r.t $ \| \ldots \| $, that is $ (-e_T) \in V_T $, a contradiction.

So there indeed is a $ D > 0 $ such that $ \| x \|_\infty \leq D \| x \| $ in $ V $, as needed.

$\endgroup$
0
$\begingroup$

Clearly, every norm in a one-dimensional vector space is equivalent, since $\|ae\|=|a|\thinspace \|e\|$ where $e$ is your basis vector, and so any two norms are in fact multiples of each other.

You can show easily that all one-dimensional vector spaces over complete fields (e.g., $\mathbf{R}$ and $\mathbf{C}$) are complete.

Now, suppose you've shown that all $n-1$-dimensional vector spaces are complete. Let $V$ be an $n$-dimensional vector space and let $\{e_1,\dots,e_n\}$ be a basis. Then $Span(e_1,\dots,e_{n-1})$ is a $n-1$-dimensional vector space, so it is complete. So it is closed in $V$. Let $r$ satisfy $B(e_n,r)\subset V\setminus Span(e_1,\dots,e_{n-1})$. If $a_n>0$, then $\|e_n-\sum_{k=1}^{n-1}(-a_k/a_n)\,e_k\|\geq r$, so $\|\sum_{k=1}^n a_k\,e_k\|\geq r|a_n|$.

You can do this with any of the basis vectors by renumbering, so $\sum_{k=1}^n |a_k|\leq C\|\sum_{k=1}^n a_k\,e_k\|$. Once you have that, you can show that your $n$-dimensional vector space is complete. Thus by induction, you have that all norms are equivalent to the 1-norm and also that all finite dimensional vector spaces are complete.

$\endgroup$

Your Answer

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