A system of \(n\) linear equations in \(n\) unknowns obeys a simple law: either it has exactly one solution for every right-hand side, or the homogeneous system has a nonzero solution. Around 1900 Fredholm discovered that the integral equation

obeys the same law, although it is an equation in infinitely many unknowns, the values of \(u\) . The shifts of Chapter 2 showed that nothing of the kind holds for bounded operators in general. What is special about the integral operator?

The answer is that it sends bounded sets into sets with compact closure. Such an operator is, in a precise sense, almost finite-dimensional: on a Hilbert space it is a limit in norm of operators of finite rank, and it turns weakly convergent sequences into convergent ones. The first part of this chapter develops these operators; the next chapter completes Fredholm’s law for them. The second part treats a related question for nonlinear maps. When does an equation of the form \(u=T(u)\) have a solution? Three theorems answer under progressively weaker assumptions on \(T\) : Banach’s contraction principle, which is constructive and needs only completeness; Schauder’s theorem, which needs compactness and convexity and gives existence without uniqueness; and Kakutani’s theorem, which allows \(T\) to be set-valued.

9.1 Operators that compress bounded sets

A compact operator is bounded, since otherwise there would be unit vectors \(x_n\) with \(\lVert Tx_n\rVert\to\infty\) , and no subsequence of \((Tx_n)\) could converge. Three observations set the scene. A bounded operator of finite rank, meaning one whose range is finite-dimensional, is compact: it maps bounded sets to bounded subsets of a finite-dimensional space, where bounded sequences have convergent subsequences (Theorem 1.10). Sums and scalar multiples of compact operators are compact, and so is a product \(ST\) in which one factor is compact and the other bounded; so \(\mathcal K(X)\) is a two-sided ideal in \(\mathcal B(X)\) . And the identity operator on an infinite-dimensional space is not compact, by Theorem 1.10 again. Consequently a compact operator on an infinite-dimensional space is never invertible: if \(T\) were compact with bounded inverse, then \(I=T^{-1}T\) would be compact.

In particular every norm limit of finite-rank operators is compact. In a Hilbert space the converse holds, and compactness has a description in terms of weak convergence.

Condition (b) is the cleanest way to think about a compact operator on a Hilbert space: it upgrades weak convergence to norm convergence. Condition (c) explains why compact operators behave like matrices. The equivalence of (a) and (b) did not use separability.

9.2 The contraction principle

We turn to fixed points, beginning with the theorem that needs least and gives most.

The map \(T\) need not be linear and \(X\) need not be a vector space; a closed subset of a Banach space is the usual setting. The first error bound is known before any iteration beyond the first has been carried out, the second after each step. The Neumann series of Chapter 2 is the special case of an affine map \(Tx=Ax+b\) on a Banach space with \(\lVert A\rVert<1\) . The most famous application is the existence and uniqueness theorem for the initial value problem \(u'=F(x,u)\) , \(u(x_0)=u_0\) , with \(F\) continuous and Lipschitz in \(u\) , which Differential Equations proves by applying Theorem 9.6 to an integral operator (math.differential-equations.picard-lindelof).

9.3 Fixed points from compactness

The contraction principle demands a quantitative hypothesis. The next family of theorems demands none, only continuity, at the price of compactness and convexity of the domain. The finite-dimensional case is a theorem of topology which we quote.

In one dimension \(C\) is an interval \([a,b]\) and the theorem follows from the intermediate value theorem applied to \(f(x)-x\) . In higher dimensions the proof requires tools from algebraic or combinatorial topology and belongs to no course in this library; we use the theorem as a black box. It gives no uniqueness and no algorithm. In infinite dimensions the statement is false for closed balls, as Example 9.7 will show, and the extra ingredient that restores it is compactness.

The proof shows what compactness is for: it makes the nonlinear problem approximable by finite-dimensional ones, uniformly, and then lets the approximate fixed points accumulate. A nonlinear map that is continuous and sends bounded sets into sets with compact closure is itself called compact; by the Arzelà–Ascoli theorem, which says that a bounded and equicontinuous family in \(C[0,1]\) has compact closure, integral operators are the standard source.

9.4 Fixed points of set-valued maps

In some problems the natural map assigns to each point not one value but a set of values. If \(x\) describes the behaviour of the participants in an economic model, the set \(F(x)\) might consist of all best replies to \(x\) , and a point with \(x\in F(x)\) is an equilibrium. Let \(K\) be a subset of \(\mathbb R^n\) . A correspondence \(F\) from \(K\) to \(K\) assigns to each \(x\in K\) a nonempty subset \(F(x)\subseteq K\) . It has closed graph if \(x_j\to x\) , \(y_j\in F(x_j)\) , and \(y_j\to y\) together imply \(y\in F(x)\) . A fixed point of \(F\) is a point with \(x\in F(x)\) .

When \(F(x)=\{f(x)\}\) is single-valued, a closed graph into a compact set is the same as continuity of \(f\) , and the theorem reduces to Brouwer’s. The principal application lies outside this course: the existence of a Nash equilibrium in mixed strategies, proved in Game Theory by applying Theorem 9.10 to the best-reply correspondence on a product of simplices (math.game-theory.nash-existence-theorem).

Exercises

1. For \(a,b\) in a Hilbert space \(H\) let \(Tx=\langle x,a\rangle b\) . Show that \(T\) is compact, find \(\lVert T\rVert\) , and find \(T^*\) .

   Answer

   \(T\) has rank at most one, so it is compact. \(\lVert Tx\rVert=\lvert\langle x,a\rangle\rvert\lVert b\rVert\le\lVert a\rVert\lVert b\rVert\lVert x\rVert\) with equality at \(x=a\) , so \(\lVert T\rVert=\lVert a\rVert\lVert b\rVert\) . From \(\langle Tx,y\rangle=\langle x,a\rangle\langle b,y\rangle=\langle x,\langle y,b\rangle a\rangle\) we get \(T^*y=\langle y,b\rangle a\) .

2. Let \((Dx)_k=x_k/\sqrt k\) on \(\ell^2\) . Is \(D\) compact? Compute \(\lVert D-P_nD\rVert\) , and determine how large \(n\) must be for the finite-rank truncation to approximate \(D\) within \(0.1\) in operator norm.

   Answer

   Yes: \(d_k=1/\sqrt k\to 0\) . \(\lVert D-P_nD\rVert=\sup_{k>n}k^{-1/2}=1/\sqrt{n+1}\) , which is at most \(0.1\) exactly when \(n\ge 99\) . Compare \(d_k=1/k\) in Example 9.1, where \(n=9\) suffices: the slower the diagonal decays, the larger the rank needed.

3. Let \(T\in\mathcal K(X)\) and \(S\in\mathcal B(X)\) . Prove that \(ST\) and \(TS\) are compact.

   Hint

   If \((x_n)\) is bounded, pick a subsequence along which \(Tx_n\) converges; then \(STx_n\) converges because \(S\) is continuous. For \(TS\) , the sequence \((Sx_n)\) is bounded, so \(T(Sx_n)\) has a convergent subsequence.

4. Let \(X\) and \(Y\) be Banach spaces with \(Y\) infinite-dimensional, and let \(T\in\mathcal K(X,Y)\) . Prove that \(T\) is not surjective.

   Solution

   Suppose \(T\) were surjective. Since \(X\) and \(Y\) are Banach spaces, the open mapping theorem (Theorem 5.1) gives \(\delta>0\) with

   \[ B_Y(0,\delta)\subseteq T(B_X(0,1)) . \]

   Because \(T\) is compact, the closure of \(T(B_X(0,1))\) is a compact subset of \(Y\) . The closed ball \(\{y:\lVert y\rVert\le\delta/2\}\) is a closed subset of that compact set, hence compact. Scaling by \(2/\delta\) , which is a homeomorphism of \(Y\) , the closed unit ball of \(Y\) is compact. By Theorem 1.10, \(Y\) is finite-dimensional, contrary to hypothesis. So \(T\) is not surjective.

   The argument combines three chapters: the open mapping theorem turns surjectivity into the statement that the image of the unit ball is large, compactness says that it is small, and the theorem of Riesz on the unit ball says that the two are incompatible in infinite dimensions. A sharper statement is true and follows from the same reasoning applied to the closure of the range: the range of a compact operator contains no closed infinite-dimensional subspace. The diagonal operator of Example 5.2 illustrates it, with a dense range that is not closed.

5. Show that the inclusion of \(\ell^1\) into \(\ell^2\) is bounded but not compact, and explain how the Arzelà–Ascoli theorem shows that the inclusion of \(C^1[0,1]\) , with the norm \(\lVert f\rVert_\infty+\lVert f'\rVert_\infty\) , into \(C[0,1]\) is compact.

   Hint

   The unit vectors \(e_k\) are bounded in \(\ell^1\) and their images in \(\ell^2\) are at mutual distance \(\sqrt2\) . For the second inclusion, a set bounded in \(C^1[0,1]\) is bounded in the supremum norm and, by the mean value theorem, uniformly Lipschitz, hence equicontinuous.

6. Compute \(\lVert k\rVert_{L^2}\) for the kernels \(k(x,y)=xy\) and \(k(x,y)=x+y\) on \([0,1]^2\) . For the first, compare with the exact operator norm on \(L^2[0,1]\) found in Exercise 7 of Chapter 2Chapter 2 and explain why they agree.

   Solution

   For \(k(x,y)=xy\) ,

   \[ \lVert k\rVert_{L^2}^2=\int_0^1x^2\,dx\int_0^1y^2\,dy=\tfrac13\cdot\tfrac13=\tfrac19,\qquad\lVert k\rVert_{L^2}=\tfrac13 . \]

   For \(k(x,y)=x+y\) ,

   \[ \lVert k\rVert_{L^2}^2=\int_0^1\!\!\int_0^1(x^2+2xy+y^2)\,dy\,dx=\tfrac13+\tfrac12+\tfrac13=\tfrac76,\qquad\lVert k\rVert_{L^2}=\sqrt{7/6}\approx 1.080 . \]

   Exercise 7 of Chapter 2Chapter 2 found that the operator with kernel \(xy\) has norm exactly \(\tfrac13\) on \(L^2[0,1]\) . So the bound \(\lVert K\rVert\le\lVert k\rVert_{L^2}\) of Proposition 9.5 is an equality in this case. The reason is that the operator has rank one: \(Kf=\langle f,u\rangle u\) with \(u(x)=x\) , whose operator norm is \(\lVert u\rVert_2^2\) , while \(\lVert k\rVert_{L^2}=\lVert u\rVert_2\lVert u\rVert_2\) because the kernel is a product.

   For \(x+y\) the operator has rank two and the inequality is strict. On the invariant subspace spanned by \(1\) and \(x\) one computes \(K1=x+\tfrac12\) and \(Kx=\tfrac12x+\tfrac13\) , and the resulting \(2\times 2\) matrix has eigenvalues \(\tfrac12\pm\tfrac1{\sqrt3}\) . Since the kernel is symmetric the operator is self-adjoint and its norm is the largest absolute eigenvalue, \(\tfrac12+\tfrac1{\sqrt3}\approx 1.077\) , slightly below \(1.080\) . The squares of the two eigenvalues add up to \(2(\tfrac14+\tfrac13)=\tfrac76\) , which is \(\lVert k\rVert_{L^2}^2\) : the Hilbert–Schmidt bound measures all the eigenvalues together, the operator norm only the largest.

7. Use the Arzelà–Ascoli theorem to prove that the Volterra operator is compact on \(C[0,1]\) with the supremum norm.

   Hint

   For \(\lVert f\rVert_\infty\le 1\) : \(\lvert Vf(x)\rvert\le 1\) and \(\lvert Vf(x)-Vf(x')\rvert\le\lvert x-x'\rvert\) . So the image of the unit ball is bounded and equicontinuous.

8. Show that \(T(x)=\cos x\) maps \([0,1]\) into itself and is a contraction there, give its constant, and use the a priori bound of Theorem 9.6 to find a number of iterations from \(x_0=1\) that guarantees an error below \(10^{-3}\) .

   Solution

   For \(0\le x\le 1\) we have \(\cos 1\le\cos x\le 1\) , and \(\cos 1\approx 0.5403>0\) , so \(T\) maps \([0,1]\) into itself. The interval is a complete metric space. If \(f\) is differentiable on an interval then \(\lvert f(x)-f(y)\rvert\le\sup\lvert f'\rvert\,\lvert x-y\rvert\) , by the mean value theorem (math.real-analysis.mean-value-theorem). Here \(\lvert f'(x)\rvert=\sin x\le\sin 1\) on \([0,1]\) , so

   \[ \lvert\cos x-\cos y\rvert\le q\,\lvert x-y\rvert,\qquad q=\sin 1\approx 0.8415<1 . \]

   By Theorem 9.6 there is a unique fixed point \(x^\star\in[0,1]\) ; numerically \(x^\star\approx 0.739085\) .

   From \(x_0=1\) , \(x_1=\cos 1\) and \(\lvert x_1-x_0\rvert=1-\cos 1\approx 0.4597\) . The a priori bound requires

   \[ \frac{q^n}{1-q}\cdot 0.4597<10^{-3},\qquad\text{that is}\qquad q^n<3.45\times 10^{-4},\qquad n>\frac{\ln(3.45\times 10^{-4})}{\ln 0.8415}\approx 46.2 . \]

   So \(n=47\) iterations are guaranteed to suffice. In fact the error first drops below \(10^{-3}\) at \(n=15\) . The discrepancy has a clear source: the contraction constant \(\sin 1\) is the worst case over the whole interval, while near the fixed point the map contracts by about \(\sin(0.739)\approx 0.674\) per step. The a posteriori bound, which uses the actual step \(\lvert x_n-x_{n-1}\rvert\) , would detect convergence much earlier.

9. Solve \(u(x)=x+\lambda\int_0^1xy\,u(y)\,dy\) in \(C[0,1]\) exactly for every real \(\lambda\ne 3\) . For which \(\lambda\) does Theorem 9.6 guarantee a unique solution in \(C[0,1]\) with the supremum norm, and what happens at \(\lambda=3\) ?

   Solution

   The integral \(\int_0^1y\,u(y)\,dy\) is a number, so any solution has the form \(u(x)=cx\) with \(c=1+\lambda\int_0^1y\,u(y)\,dy\) . Substituting \(u=cx\) : \(\int_0^1y\cdot cy\,dy=c/3\) , so

   \[ c=1+\frac{\lambda c}{3},\qquad c=\frac{3}{3-\lambda}\quad(\lambda\ne 3),\qquad u(x)=\frac{3x}{3-\lambda} . \]

   For every \(\lambda\ne 3\) this is the one and only solution. For example \(\lambda=1\) gives \(u=\tfrac32x\) , and indeed \(x+\int_0^1xy\cdot\tfrac32y\,dy=x+\tfrac12x\) .

   Write the equation as \(u=T(u)\) with \(T(u)=g+\lambda Ku\) , \(g(x)=x\) , and \(K\) the operator with kernel \(xy\) . Then \(\lVert T(u)-T(v)\rVert_\infty\le\lvert\lambda\rvert\lVert K\rVert\lVert u-v\rVert_\infty\) , and \(\lVert K\rVert=\tfrac12\) on \(C[0,1]\) (Exercise 7 of Chapter 2Chapter 2). So Theorem 9.6 applies when \(\lvert\lambda\rvert<2\) . For \(2\le\lvert\lambda\rvert\) with \(\lambda\ne 3\) the theorem is silent in this norm, but the explicit formula shows that a unique solution exists anyway: being a contraction is sufficient for unique solvability, not necessary.

   At \(\lambda=3\) the equation for \(c\) reads \(c=1+c\) , which is impossible, so there is no solution. At the same time the homogeneous equation \(u=3\int_0^1xy\,u(y)\,dy\) has the nonzero solution \(u(x)=x\) . Loss of existence and loss of uniqueness occur at the same value of \(\lambda\) , namely the reciprocal of the eigenvalue \(\tfrac13\) of \(K\) . Chapter 10 proves that this coincidence is a general law for compact operators.

10. Find the flaw: “The map \(T(x)=x+1/x\) on \([1,\infty)\) satisfies \(\lvert Tx-Ty\rvert<\lvert x-y\rvert\) for \(x\ne y\) , so it is a contraction on a complete metric space and has a unique fixed point.”

    Answer

    A contraction requires one constant \(q<1\) with \(\lvert Tx-Ty\rvert\le q\lvert x-y\rvert\) for all \(x,y\) . Here the ratio \(\lvert Tx-Ty\rvert/\lvert x-y\rvert=1-1/(xy)\) is less than \(1\) for each pair but has supremum \(1\) . The map has no fixed point, since \(T(x)>x\) .

11. Prove the a posteriori bound \(d(x_n,x^\star)\le\frac{q}{1-q}d(x_n,x_{n-1})\) of Theorem 9.6 in detail, and explain why it is usually sharper in practice than the a priori bound.

    Hint

    Start from \(d(x_n,x^\star)\le d(x_n,x_{n+1})+d(x_{n+1},x^\star)\) , bound the first term by \(q\,d(x_{n-1},x_n)\) and the second by \(q\,d(x_n,x^\star)\) , and solve for \(d(x_n,x^\star)\) . It uses the observed step size instead of the initial one, so it reflects the actual, often faster, local rate of contraction.

12. Let \(T:X\to X\) be a map on a complete metric space such that some power \(T^m\) is a contraction. Prove that \(T\) has exactly one fixed point, and apply this to \((Tu)(x)=1+\int_0^xu(t)\,dt\) on \(C[0,1]\) with the supremum norm.

    Solution

    Let \(S=T^m\) , a contraction of the complete metric space \(X\) . By Theorem 9.6, \(S\) has a unique fixed point \(x^\star\) . Then

    \[ S(Tx^\star)=T^{m+1}x^\star=T(Sx^\star)=Tx^\star , \]

    so \(Tx^\star\) is also a fixed point of \(S\) . By uniqueness \(Tx^\star=x^\star\) . Conversely any fixed point of \(T\) is a fixed point of \(S=T^m\) , hence equals \(x^\star\) . So \(T\) has exactly one fixed point. Moreover the iterates of \(T\) from any starting point converge to it, since each of the \(m\) subsequences \((T^{mj+r}x_0)_j\) , \(r=0,\dots,m-1\) , is a sequence of iterates of \(S\) .

    For \((Tu)(x)=1+\int_0^xu\) on \(C[0,1]\) we have \(Tu-Tv=V(u-v)\) , where \(V\) is the Volterra operator, so the best Lipschitz constant of \(T\) is \(\lVert V\rVert=1\) and \(T\) is not a contraction for the supremum norm on \([0,1]\) . But \(T^2u-T^2v=V^2(u-v)\) , and \(\lVert V^2\rVert=\tfrac12\) by Example 2.5. So \(T^2\) is a contraction with \(q=\tfrac12\) , and \(T\) has a unique fixed point in \(C[0,1]\) . It is the solution of \(u'=u\) , \(u(0)=1\) , namely \(u(x)=e^x\) . The same device proves global existence for linear initial value problems on any bounded interval, where a single application of the integral operator need not contract.

13. Deduce the one-dimensional case of Theorem 9.7 from the intermediate value theorem, and give a continuous map of the open interval \((0,1)\) into itself with no fixed point.

    Answer

    Let \(f:[a,b]\to[a,b]\) be continuous and \(g(x)=f(x)-x\) . Then \(g(a)\ge 0\) and \(g(b)\le 0\) , so \(g\) vanishes somewhere. On \((0,1)\) the map \(f(x)=x/2\) has no fixed point; the interval is not compact.

14. Let \(k\) be continuous on \([0,1]^2\) and \(g:\mathbb R\to\mathbb R\) continuous and bounded. Prove that the equation \(u(x)=\int_0^1k(x,y)\,g(u(y))\,dy\) has at least one solution \(u\in C[0,1]\) .

    Solution

    Let \(m=\sup\lvert g\rvert\) and \(\kappa=\max\lvert k\rvert\) , and let \(C\) be the closed ball of radius \(R=m\kappa\) in \(C[0,1]\) , a closed convex set. Define \((Tu)(x)=\int_0^1k(x,y)g(u(y))\,dy\) .

    \(T\) maps \(C[0,1]\) into \(C\) . \(\lvert Tu(x)\rvert\le\kappa m=R\) , and \(Tu\) is continuous by the estimate that follows.

    Equicontinuity. Given \(\varepsilon>0\) , uniform continuity of \(k\) on the compact square gives \(\delta>0\) with \(\lvert k(x,y)-k(x',y)\rvert\le\varepsilon\) whenever \(\lvert x-x'\rvert\le\delta\) . Then \(\lvert Tu(x)-Tu(x')\rvert\le\varepsilon m\) for every \(u\) . So \(T(C)\) is bounded and equicontinuous, and by the Arzelà–Ascoli theorem its closure is compact; that closure lies in the closed set \(C\) .

    Continuity of \(T\) . Let \(u_n\to u\) uniformly. All these functions take values in some bounded interval \([-r,r]\) , on which \(g\) is uniformly continuous, so \(g\circ u_n\to g\circ u\) uniformly, and \(\lVert Tu_n-Tu\rVert_\infty\le\kappa\lVert g\circ u_n-g\circ u\rVert_\infty\to 0\) .

    The hypotheses of Theorem 9.9 hold, so \(T\) has a fixed point \(u\in C\) , which is a continuous solution of the equation. No Lipschitz condition on \(g\) was needed, and none is available in general; correspondingly the solution need not be unique.

15. For the map \(T\) of Example 9.7, verify continuity, compute \(T(x)\) and \(\lVert T(x)-x\rVert\) for \(x=0\) and for \(x=e_1\) , and state which hypothesis of Theorem 9.9 fails.

    Hint

    Continuity: \(x\mapsto\lVert x\rVert\) and the shift are continuous, and \(t\mapsto\sqrt{1-t^2}\) is continuous on \([0,1]\) . \(T(0)=e_1\) at distance \(1\) from \(0\) ; \(T(e_1)=e_2\) at distance \(\sqrt2\) from \(e_1\) . The image \(T(B)\) is not contained in a compact set.

16. On \(K=[0,1]\) find all fixed points of the correspondences \(F(x)=[0,1-x]\) and \(G(x)=\{1-\tfrac12x\}\) , and verify the hypotheses of Theorem 9.10 for each.

    Answer

    \(x\in F(x)\) means \(0\le x\le 1-x\) , so the fixed points of \(F\) are the points of \([0,\tfrac12]\) . \(x\in G(x)\) means \(x=1-\tfrac12x\) , so \(x=\tfrac23\) . In both cases the values are closed intervals or points, hence convex, and the graphs are closed sets; \(G\) is a continuous function.

17. Let \(K\subseteq\mathbb R^n\) be compact and \(f:K\to K\) a function. Prove that the correspondence \(F(x)=\{f(x)\}\) has closed graph if and only if \(f\) is continuous.

    Hint

    If \(f\) is continuous and \(x_j\to x\) , \(f(x_j)\to y\) , then \(y=f(x)\) . Conversely, if the graph is closed and \(x_j\to x\) , every subsequence of \((f(x_j))\) has, by compactness of \(K\) , a further subsequence converging to some \(y\) , and the closed graph forces \(y=f(x)\) ; so \(f(x_j)\to f(x)\) .

18. Let \(T\) be a compact operator on a Hilbert space and \((e_k)\) an orthonormal sequence. Prove that \(Te_k\to 0\) , and deduce that if \(Te_k=\lambda_ke_k\) for all \(k\) then \(\lambda_k\to 0\) .

    Solution

    An orthonormal sequence converges weakly to \(0\) : for every \(y\in H\) , Bessel’s inequality (Proposition 7.6) gives \(\sum_k\lvert\langle y,e_k\rangle\rvert^2\le\lVert y\rVert^2\) , so \(\langle e_k,y\rangle\to 0\) , and by Corollary 8.2 this is weak convergence. A compact operator maps weakly convergent sequences to norm convergent ones; this is the implication from (a) to (b) in Theorem 9.3, whose proof did not use separability. Hence \(Te_k\to T0=0\) in norm.

    If moreover \(Te_k=\lambda_ke_k\) , then \(\lvert\lambda_k\rvert=\lVert\lambda_ke_k\rVert=\lVert Te_k\rVert\to 0\) .

    Two consequences are worth recording. First, a compact operator cannot have infinitely many orthonormal eigenvectors with eigenvalues bounded away from \(0\) ; in particular each eigenspace for a nonzero eigenvalue of a compact self-adjoint operator is finite-dimensional. Second, the criterion gives quick proofs of non-compactness: for multiplication by \(x\) on \(L^2[0,1]\) , Example 9.3 found an orthonormal sequence with \(\lVert Ms_k\rVert_2^2\to\tfrac13\) , and for the identity \(\lVert Ie_k\rVert=1\) .