52
$\begingroup$

I am finding Rudin's proofs of these theorems very non-intuitive and difficult to recall. I can understand and follow both as I work through them, but if you were to ask me a week later to prove one or the other, I couldn't do it.

For instance, the use of a contraction mapping in the inverse function theorem seems to require one to memorize, at the very least, a non-obvious (at least to me) function (viz. $\phi(\mathbf{x}) = \mathbf{x} + \mathbf{A}^{-1}(\mathbf{y}-\operatorname{f}(\mathbf{x}))$) and constant (viz. $\lambda^{-1} = 2 \Vert \mathbf{A}^{-1}\Vert$), where $\mathbf{A}$ is the differential of $\operatorname{f}$ at $\mathbf{a}$.

The implicit function theorem proof, while not as bad, also requires one to construct a new function without ever hinting as to what the motivation is.

I searched the previous questions on this site and haven't found this addressed, so I figured I'd ask. I did finnd this proof to have a much more intuitive approach to the inverse function theorem, but would like to see what proofs are preferred by others.

$\endgroup$
7
  • 1
    $\begingroup$ I find Rudin hard going for new stuff. For implicit function theorem, etc., I like 'Functional analysis', by Kantorovich & Akilov. But these things are matters of taste. I like that K&A give formulae with explicit constants, etc. $\endgroup$
    – copper.hat
    Jun 30, 2013 at 22:51
  • 15
    $\begingroup$ $\phi(\mathbf{x}) = \mathbf{x} + \mathbf{A}^{-1}(\mathbf{y}-\operatorname{f}(\mathbf{x}))$ is (almost) Newton's method. $\endgroup$ Jun 30, 2013 at 22:57
  • $\begingroup$ I think Newton's method is a better proof in that it makes some details explicit that are otherwise lost. For example, if $f$ map some closed set $C$ into itself and the initial guess is in this set, then the solution is also. Ultimately most proofs I have seen rely on the contraction map. $\endgroup$
    – copper.hat
    Jun 30, 2013 at 23:04
  • 1
    $\begingroup$ @AnonSubmitter85 I learned these things from Edwards' Advanced Calculus, it looks like Rudin is not much different. I have seen an argument which avoids the contraction mapping argument in favor of some epsilon/delta type argument, however, I think it was less general and it didn't offer the error estimate which comes with the contraction technique. $\endgroup$ Jul 1, 2013 at 1:48
  • $\begingroup$ @copper.hat Can you give a reference for a proof using Newton's method? $\endgroup$
    – littleO
    Jan 28, 2017 at 13:18

3 Answers 3

60
$\begingroup$

Suppose you want to find the inverse of the mapping $F: \mathbb{R}^n \rightarrow \mathbb{R}^n$ near a point $x_o$ where $F'(x_o)$ is invertible. The derivative (Jacobian matrix) provides an approximate form for the map $F(x) = F(x_o)+F'(x_o)(x-x_o)+\eta$. If you set $y = F(x)$ and ignore the error term $\eta$ then solving for $x$ gives us the first approximation to the inverse mapping. $$ x = x_o+[F'(x_o)]^{-1}(y-F(x_o)). $$ Then, you iterate. The technical details are merely to insure this iteration does indeed converge to the inverse mapping, but at the start, it's just using the derivative to linearize the problem.

I don't know if this helps or not, but really the approach is almost brute force, to invert $F(x)=y$ what do you do? You solve for $x$. We can't do that abstractly for $F$ so instead we solve the next best thing, the linearization. Then the beauty of the contraction mapping technique completes the argument.

$\endgroup$
4
  • $\begingroup$ I just re-worked through the proof and this actually helps tremendously. $\endgroup$ Jul 2, 2013 at 23:39
  • 6
    $\begingroup$ @AnonSubmitter85 good to hear, I spent about 5 hours going through this proof and its surrounding theory with one of my students. Btw, the motivation for that weird function construction for the implicit mapping theorem proof is simply that of convenience. You could go through a similar argument by solving the linearized level equation for $y$ to prove the implicit mapping theorem... but, why bother when we can instead just borrow the result from the inverse mapping theorem. I think some motivation could be made from how we parametrize surfaces which are graphs in calculus III... $\endgroup$ Jul 2, 2013 at 23:59
  • $\begingroup$ I like the "inverting the linearization" intuition but the map $\varphi(x) = x + [F'(x_0)]^{-1} ( y - F(x) )$ used by Rudin is slightly different from what your argument yields. Is there a better explanation than convenience for the replacements $x_0 \mapsto x$ that he makes? $\endgroup$ May 18, 2018 at 17:17
  • 2
    $\begingroup$ I would guess there is more than one way to set-up this proof. I think of $x_o$ as fixed whereas apparently Rudin takes $y$ as fixed in his construction of $\phi(x)$. This answer is not a complete argument, it really just offers intuition, the complete argument is about 3 pages in Edward's Advanced Calculus of Several Variables. Maybe I'll get a chance to prove it properly next semester... $\endgroup$ May 18, 2018 at 21:06
17
$\begingroup$

The other answer takes care of the Inverse Function Theorem case. Therefore, I'll give "another" proof of the Implicit Function Theorem. (Note that I inverted the order of $\mathbb{R}^n$ and $\mathbb{R}^m$, compared to Rudin's)


Consider the commutative diagram

enter image description here

where $F(x,y)=\big(x,f(x,y)\big)$. By the Inverse Function Theorem, it follows that locally we have

enter image description here

Due to how $F$ is defined, the commutativity of the diagram above is obvious. Due to how $F$ is defined and due to the fact that it is invertible in the given neighbourhood, the existence of $g$ is clear, and $g=\pi_2 \circ F^{-1} \circ i$ is also clear. Since $g=\pi_2 \circ F^{-1} \circ i$, $g$ is $C^1$. The rest of the Implicit Function Theorem follows by using the composition of the diagonal arrows.


As to why take the function $F$ as is, just note that the proof is basically finding a function $F$ making everything commute. The choice of $F$ is the natural one (actually, practically imposed one) to make that happen.

$\endgroup$
9
  • $\begingroup$ I liked this answer, and wanted to understand each part of the diagram. I guess $i(x) =(x,0)$. Why is $i \times \pi_2$ part of the composition of the diagonal arrow in the square? Further, isn't $i \times \pi_2 = (i(x),g(x)) = (x,0,g(x)) \in \mathbb R^n \times \mathbb R^m \times \mathbb R^m$? $\endgroup$ Dec 3, 2017 at 19:38
  • $\begingroup$ @AnthonyPulido Yes, $i(x)=(x,0)$ or $i(x)=(x,c)$ for whatever $c$ you are taking in $f(x,y)=c$ in the statement of the theorem (it suffices $c=0$, and most texts suppose so). For the next part, sorry for the ambiguity, but the correct interpretation is $i \times (\pi_2 \circ F^{-1} \circ i)$, not $(i \times \pi_2) \circ ~etc$. $\endgroup$
    – Aloizio Macedo
    Dec 3, 2017 at 19:44
  • $\begingroup$ Thanks. Do we not have the same problem, though? Recall that $g = \pi_2 \circ F^{-1} \circ i$. Then $i \times g(x) = (i(x),g(x)) = (x,0,g(x)) \in \mathbb R^{n + m + m}$. $\endgroup$ Dec 3, 2017 at 20:03
  • $\begingroup$ @AnthonyPulido Yes, maybe I should have used an $\iota$ (or simply $\mathrm{Id}$) in the product map, since that "$i$" in the product map $i \times g$ is the identity. I can fix these notational issues (if there are any more, please tell me), but it will require some time since those diagrams are on images and not directly mathjax. I'll try to update it later today. $\endgroup$
    – Aloizio Macedo
    Dec 3, 2017 at 20:07
  • $\begingroup$ Thanks, again. Please take your time updating the diagram. It isn't urgent, at least for me. Just after I posted I noticed that it should probably be the identity. My question is now, why write it that way? Isn't $F^{-1} \circ i$ enough? $\endgroup$ Dec 3, 2017 at 20:22
14
$\begingroup$

I first studied the proof of the inverse function theorem over 20 years ago, and it seemed opaque. But now I finally understand the proof well enough that it seems clear and almost straightforward.

I like the presentation of Spivak's proof that is given in Jerry Shurman's excellent book "Calculus and Analysis in Euclidean Space". I'll attempt to explain the proof here in a way that provides intuition and emphasizes the key ideas.

Statement of theorem: Suppose that $f:\mathbb R^n \to \mathbb R^n$ is a continuously differentiable function and $a \in \mathbb R^n$ is a point where the derivative matrix $f'(a)$ is invertible. Then there exists an open set $U$ containing $a$ and an open set $V$ containing $f(a)$ such that:

  1. The restriction of $f$ to $U$ (denoted $f \mid_U$) is an invertible mapping from $U$ onto $V$.
  2. The inverse of $f|_U$ is a differentiable function from $V$ to $U$.

Comment: The fundamental strategy of calculus is to take a nonlinear function $f$ (difficult) and approximate it locally by a linear function (easy). In more detail, we have $$ \tag{1} f(x) \approx f(a) + f'(a)(x - a) $$ and the approximation is good when $x$ is near $a$. Since the function $L(x) = f(a) + f'(a)(x - a)$ is invertible, it seems quite plausible that $f$ should also be invertible on some sufficiently small neighborhood of $a$.

Terence Tao refers to the approximation (1) as "Newton's approximation". I'll use this name for it also. It is essentially the definition of $f'(a)$.


Proof: I'll start by proving the theorem in the special case where $f'(a) = I$, the $n \times n$ identity matrix. Later, the general theorem will be an easy corollary of this special case.

Step 1: Our first goal is to show that $f$ is "locally one-to-one". Is this plausible? If two points $x_1, x_2 \in \mathbb R^n$ are close to $a$, then by Newton's approximation we have $$ f(x_1) \approx f(a) + x_1 - a \quad \text{and} \quad f(x_2) \approx f(a) + x_2 - a $$ and so $$ f(x_1) - f(x_2) \approx x_1 - x_2 $$ and therefore $\| f(x_1) - f(x_2) \| \approx \| x_1 - x_2 \|$. So, it seems plausible that $$ \tag{2} \| f(x_1) - f(x_2) \| \geq \frac12 \| x_1 - x_2 \| $$ for all points $x_1, x_2$ that are sufficiently close to $a$.

We conclude that there exists a closed ball $\bar B$ centered at $a$ such that the inequality (2) holds for all points $x_1, x_2 \in \bar B$. The function $f$ is one-to-one on $\bar B$.

Exercise 1: Make the above argument rigorous by keeping track of the error terms when using Newton's approximation. (Hint: You will use the "mean value inequality" at the crucial moment.)

We can also choose $\bar B$ small enough that $f'(x)$ is invertible for all $x \in \bar B$.

The inequality (2) will continue to be helpful in step 2 and step 3 below.


Step 2: Our next goal is to show that $f$ is "locally onto". Let $y$ be a point near $f(a)$. We would like to find a point $x^* \in B$ such that $f(x^*) = y$. (Here $B$ is the interior of $\bar B$.)

Idea: Let's choose $x^*$ so that $f(x^*)$ is as close as possible to $y$, then hope to conclude that in fact $f(x^*) = y$. In other words, let's choose $x^* \in \bar B$ to be a minimizer of the function $$ \tag{3} L(x) = \| f(x) - y \|^2. $$ The extreme value theorem guarantees that such a point $x^* \in \bar B$ exists.

Comment: If you're familiar with least squares and nonlinear least squares, which are ubiquitous topics in applied math, then introducing this function $L$ feels quite natural. After spending many years doing applied math and solving optimization problems like this, I returned to the proof of the inverse function theorem and realized how comfortable I now feel with the function (3). For example, computing the derivative of $L$ using the chain rule is an effortless one-line calculation.

Exercise 2: Show that if $y$ is sufficiently close to $f(a)$ then $x^*$ must belong to the interior of $\bar B$. It follows that $$ 0 = L'(x^*) = 2(f(x^*) - y)^T f'(x^*) $$ and multiplying on the right by $f'(x^*)^{-1}$ yields $f(x^*) = y$.

Conclusion: there exists an open ball $V$ centered at $f(a)$ such that if $y \in V$ then $y = f(x^*)$ for some point $x^* \in B$.

Let $U = f^{-1}(V) \cap B$. Then $U$ is an open set, and the restriction of $f$ to $U$ is an invertible function from $U$ onto $V$. We are now mostly done with proving the inverse function theorem!


Step 3: Let $g: V \to U$ be the inverse of $f|_U$. We still need to show that $g$ is differentiable.

Let $y = f(x) \in V$. To show that $g$ is differentiable at $y$, we need to find a matrix $M$ such that that if a point $\hat y = f(\hat x)$ is close to $y$, then $$ \tag{4} g(\hat y) \approx g(y) + M(\hat y - y) $$ or equivalently $$ \hat x \approx x + M(f(\hat x) - f(x)) $$ or equivalently $$ \tag{5} f(\hat x) \approx f(x) + M^{-1}(\hat x - x). $$ Comparing (5) with Newton's approximation $$ \tag{6} f(\hat x) \approx f(x) + f'(x)(\hat x - x) $$ suggests that taking $M = f'(x)^{-1}$ will work.

Exercise 3: Make the above argument rigorous by showing if $M = f'(x)^{-1}$ then the error in the approximation (4) is sufficiently small when $\hat y$ is close to $y$. (Hint: Start by writing down the error term in the approximation (6), then calculate the error term in (4) and show that it is sufficiently small. The inequality (2) will be helpful again.)


The general case: Finally, I have been assuming all along that $f'(a) = I$. What if that is not true? In that case, we can define $$ F(x) = f'(a)^{-1} f(x) $$ and notice that $F'(a) = f'(a)^{-1} f'(a) = I$. By our special case of the inverse function theorem that we proved above, there exist an open set $U$ containing $a$ and an open set $V$ containing $F(a)$ such that the restriction of $F$ to $U$ is an invertible function onto $V$. Let $\tilde V = f'(a) V$. The set $\tilde V$ is open, and the restriction of $f$ to $U$ is an invertible function from $U$ onto $\tilde V$.

This completes the proof of the inverse function theorem.


Appendix 1: Solutions to the exercises

Solution to Exercise 1: Here's the idea. I'll try to explain this in a way that shows how someone might have thought of it. Let $r(x)$ be the error term in Newton's approximation. So the function $r$ is defined by $$ f(x) = f(a) + x - a + r(x) \quad \quad \text{for all } x \in \mathbb R^n. $$ If $x_1, x_2 \in \mathbb R^n$ then we have $$ f(x_1) - f(x_2) = x_1 - x_2 + r(x_1) - r(x_2) $$ and so $$ \tag{7} \| f(x_1) - f(x_2) \| \geq \| x_1 - x_2 \| - \underbrace{\| r(x_1) - r(x_2) \|}_{\substack{\text{hopefully small} \\ \text{compared to } \|x_1 - x_2\|}}. $$ Now we apply the "mean value inequality" to the term on the right. The mean value inequality tells us that if $\| r'(c) \| \leq M$ for all points $c$ on the line segment from $x_1$ to $x_2$ then $$ \| r(x_1) - r(x_2) \| \leq M \|x_1 - x_2 \|. $$ Here $\| r'(c) \|$ is the operator norm of the matrix $r'(c)$. If we could somehow guarantee that $\| r'(c) \| \leq \frac12$ for all points $c$ between $x_1$ and $x_2$, then we could take $M = \frac12$ and conclude that $$ \| r(x_1) - r(x_2) \| \leq \frac12 \| x_1 - x_2 \|. $$ Combining this with the inequality (7), we find that $$ \| r(x_1) - r(x_2) \| \geq \frac12 \| x_1 - x_2 \|, $$ which is the desired inequality.

To show that we can take $M = \frac12$, if $x_1$ and $x_2$ are sufficiently close to $a$, just note that $r'(x) = f'(x) - I$ and $r'(a) = 0$ (the zero matrix). Because the function $x \mapsto \| r'(x) \|$ is continuous, there exists a closed ball $\bar B$ centered at $a$ such that $\| r'(c) \| \leq 1/2$ for all points $c \in \bar B$.

So, in conclusion, if $x_1, x_2 \in \bar B$ then $\|f(x_1) - f(x_2) \| \geq \frac12 \| x_1 - x_2 \|$.


Solution to Exercise 2: First I'll give an intuitive explanation. Suppose that $x \in \partial \bar B$. Let $r$ be the radius of $\bar B$. By inequality (2) above we have $$ \| f(x) - f(a) \| \geq \frac12 \| x - a \| = \frac{r}{2}. $$ So $f(x)$ is "far away" from $f(a)$. If $y$ is very close to $f(a)$, then $f(x)$ is also far away from $y$. So $x$ can't be a minimizer for $L$ over $\bar B$. (In particular, $L(a) < L(x)$.)

To make this intuition rigorous, let $V$ be the open ball of radius $r/4$ centered at $f(a)$. If $y \in V$, then $\| f(x) - y \| > \| f(a) - y \|$ (as the picture below illustrates), and so $L(x) > L(a)$. This means that $x$ is not a minimizer of $L$ over $\bar B$.

enter image description here

If we don't want to use a picture proof, we can argue as follows. Let $y \in V$. If $x \in \partial \bar B$, then
\begin{align} \| f(x) - y \| &= \| f(x) - f(a) + f(a) - y \| \\ &\geq \underbrace{\| f(x) - f(a) \|}_{\geq \, r/2} - \underbrace{\| f(a) - y \|}_{< \, r/4} \\ &> \frac{r}{4}. \end{align} But $\| f(a) - y \| < \frac{r}{4}$. It follows that $L(a) < L(x)$, so $x$ is not a minimizer of $L$ over $\bar B$.


Solution to Exercise 3: Let $g:V \to U$ be the inverse of $f|_U$, and let $y \in V$. Our goal is to show that $g$ is differentiable at $y$. There exists $x \in U$ such that $f(x) = y$. Let $r:U \to \mathbb R^n$ be defined by $$ \tag{8} f(\hat x) = f(x) + f'(x) (\hat x - x) + r(\hat x) $$ for all $\hat x \in U$. In other words, $r$ is the error in Newton's approximation to $f$ near $x$. If $\hat y \in V$, then $\hat y = f(\hat x)$ for some $\hat x \in U$, and equation (8) can be stated equivalently as $$ g(\hat y) = g(y) + f'(x)^{-1}(\hat y - y) - r(\hat x). $$ Is the error term here sufficiently small? Notice that if $\hat y \neq y$ then \begin{align} \frac{\| r(\hat x) \|}{\|\hat y - y \|} &= \underbrace{\frac{\| r(\hat x) \|}{\| \hat x - x \|}}_{\text{approaches }0}\, \underbrace{\frac{\| \hat x - x\|}{\| \hat y - y \|}}_{\leq 2}. \end{align} The inequality (2), which has been repeatedly useful, tells us that the term on the right is at most $2$. As $\hat y$ approaches $y$, $\hat x$ approaches $x$ (thanks again to the inequality (2)), and so $ \frac{\| r(\hat x) \|}{\| \hat x - x \|} $ approaches $0$ because $f$ is differentiable at $x$. It follows that $$ \frac{\| r(\hat x)\|}{\|\hat y - y \|} \to 0 \quad \text{as} \quad \hat y \to y. $$ Therefore, $g$ is differentiable at $y$.

Appendix 2: Further comments

  • To simplify notation slightly, I assumed that the domain of $f$ is $\mathbb R^n$. But, it's trivial to rephrase the argument for the case where the domain of $f$ is an open subset of $\mathbb R^n$.
  • In case it's not clear how I took the derivative of $L$ using the chain rule, here is the calculation in more detail. Notice that $$ L(x) = s(t(x)) $$ where $s$ and $t$ are the functions defined by $$ t(x) = f(x) - y \quad \text{and} \quad s(u) = \| u \|^2 $$ for all $x, u \in \mathbb R^n$. The derivatives of $t$ and $s$ are $$ t'(x) = f'(x) \quad \text{and} \quad s'(u) = u^T. $$ The chain rule tells us that $$ L'(x) = s'(t(x)) t'(x) = (f(x) - y)^T f'(x). $$
$\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.