Cholesky decompositions of integral operators and the Fredholm determinant

This paper presents an operator version of the well-known and popular tool for calculating the determinant of matrix using its Cholesky decomposition:

$$\log\det M=2\sum_{i=1}^{n}\log L_{ii}$$

where $LL^{\top}\!=M$ is the Cholesky decomposition of $M$.

The equivalent result for operators in $L^{2}[0,1]$ is

$$\log\det(\mathbf{I}+M):=\log(\text{Fredholm determinant of }M)=\int_{0}^{1}\!T(t,t)\>\mathrm{d}{t}.$$

where $M$ is an integral operator, and $(\mathbf{I}+T)(\mathbf{I}+T^{*})=(\mathbf{I}+M)$ is the Cholesky decomposition of $M$.

Background

Consider the Hilbert space $\mathbb{H}$ of square-integrable functions on $[0,1]$, $\mathbb{H}=\mathcal{B}(L^{2}[0,1];\mathbb{R})$. Let $K$ be an integral operator in $\mathcal{B}(\mathbb{H})$. We shall use the same symbol for an integral operator and its kernel, ie.:

$$Kf(t)=\int_{0}^{1}\!K(t,s)f(s)\>\mathrm{d}{s},\quad f\in L^{2}[0,1]$$

Furthermore, we shall denote the identify operator by $\mathbf{I}$ and use ^∗ to denote the adjoint of an operator.

We define the Fredholm determinant for an integral operator $K\in\mathcal{B}(L^{2}[0,1];\mathbb{R})$ by:

$$Fd(K)=\sum_{k=0}^{\infty}\frac{1}{n!}\int_{0}^{1}\dots\int_{0}^{1}\det[K(x_{p},x_{q})]_{p,q=1}^{n}\>\mathrm{d}x_{1}\dots\>\mathrm{d}x_{n},$$ (1)

Here the function $z\mapsto Fd(zK)$ is an entire function on the complex plane (Fredholm, 1903). $Fd(K)$ is well-defined if $K$ is block-continuous, but not for triangular operators (as the integral along the diagonal is ambiguous if $K$ is discontinuous across the diagonal). We refer to the discussion in Bornemann (2010) regarding different definitions of the Fredholm determinant.

The Fredholm determinant is the equivalent of the ”usual” determinant for operators on $\mathbb{R}^{n}$ (ie. matrices) and was introduced in Fredholm (1903) to solve integral equations on the form $\phi=f+zK\phi$ for unknown $\phi\in L^{2}[0,1]$.

Cholesky decomposition for matrices

One of the most appreciated computational tools for positive definite matrices is the Cholesky decomposition: Let $M\in\mathbb{R}^{n\times n}$ be positive definite. Then there exists a unique decomposition $M=LL^{\top}\!$, where $L$ is a lower triangular matrix. There exist specialised algorithms for computing the Cholesky decomposition, something which many programming languages implements; the Wikipedia entry on the Cholesky decomposition has a good overview.

The Cholesky decomposition may aid in various computations involving $M$. Assume $M$ has the Cholesky decomposition $M=LL^{\top}\!$ and assume $y\in\mathbb{R}^{n}$:

• Inner product using $M$ or $M^{-1}$: $y^{\top}\!My=||L^{\top}\!y||^{2}$, $y^{\top}\!M^{-1}y=||L^{-1}y||^{2}$.

• Inversion of $M$: $M^{-1}=L^{-1,\top}L^{-1}$.

• Log-determinant of $M$: $\log\det M=2\sum_{i=1}^{n}\log L_{ii}$

where the triangular structure furthermore can be used for fast calculations of $L^{-1}$ and $L^{-1}y$.

Cholesky decomposition for operators on $L^{2}[0,1]$

We can also define Cholesky decompostions for integral operators on $\mathbb{H}$, though some care needs to be taken as integral operators are not generally invertible.

Let $A\in\mathcal{B}(\mathbb{H})$ be a positive definite integral operator. We define the cholesky decomposition of $\mathbf{I}+A$ as $(\mathbf{I}+T)(\mathbf{I}+T^{*})$, where $T$ is a triangular operator (ie. an integral operator where $T(x,y)=0$ for $x>y$).

The Cholesky decomposition of $\mathbf{I}+A$ satisfy inversion and inner product properties similar to matrices:

$$(I+A)^{-1}=(\mathbf{I}+T^{-1,\ast})(\mathbf{I}+T^{-1})$$

and

$$\langle f,(I+A)^{-1}f\rangle=||(\mathbf{I}+T^{-1})f||^{2}$$

We refer to (Gohberg et al., 1993, chap. XXII) for a general discussion on LU decompositions of operators on $L^{2}[0,1]$.

The Cholesky decomposition and the determinant

The determinant is not well-defined for operators on $L^{2}[0,1]$, so it is not obvious if or how one could have a statement similar to $\log\det M=\sum_{i=1}^{n}\log L_{ii}$. However, knowing that the Fredholm determinant plays a role with many similarities to the ordinary determinant, we could hope for a statement along these lines.

This is indeed the case if we define $\det(\mathbf{I}+M)=Fd(M)$. The theorem is the following:

Theorem 1.

Let $A$ be an integral operator on $[0,1]$ with continuous kernel. Suppose $\mathbf{I}+A$ decomposes $\mathbf{I}+A=(\mathbf{I}+T)(\mathbf{I}+T^{*})$ where $T$ is a triangular operator.

Assume that $T$ is continuous on the closed lower triangle $\{(x,y)|0\leq x\leq 1,0\leq y\leq x\}$ (in general, $T$ is not continuous as a function on $[0,1]^{2}$). We then have

$$\log\det(\mathbf{I}+A)=\int_{0}^{1}\!T(t,t)\>\mathrm{d}{t}.$$

The theorem can be justified heuristically from the ’matrix-like’ approximation of $\mathbf{I}+A$: $1+T(t,t)$ corresponds to the diagonal elements, and $\log(1+T(t,t))\approx T(t,t)$ when $T(t,t)$ is small.

Proof.

In the following, we define $\det(\mathbf{I}+M)=Fd(M)$ whenever $Fd(M)$ is well-defined.

It can easily be proved that the Fredholm determinant has the block-property of ordinary matrices; ie.:

$$\det\begin{pmatrix}\mathbf{I}+U&0\\ V&\mathbf{I}+X\end{pmatrix}=\det\begin{pmatrix}\mathbf{I}+U&V\\ 0&\mathbf{I}+X\end{pmatrix}=\det(\mathbf{I}+U)\det(\mathbf{I}+X)$$

for continuous integral operators $U,V,X$ of appropriate sizes.

Define $A_{t}$ and $T_{t}$ to be the restrictions of $A$ and $T$ to $[0,t]$ for $0\leq t<1$. By construction, $\mathbf{I}+A_{t}=(\mathbf{I}+T_{t})(\mathbf{I}+T_{t}^{*})$.

Fix $t$, and let $s>0$ s.t. $t+s<1$. Suppose $\mathbf{I}+T_{t+s}$ and $\mathbf{I}+A_{t+s}$ admit the following decompositions:

$$\mathbf{I}+T_{t+s}=\begin{pmatrix}\mathbf{I}+T_{t}&0\\ K_{s}&\mathbf{I}+X_{s}\end{pmatrix}$$

and

$$\mathbf{I}+A_{t+s}=\begin{pmatrix}\mathbf{I}+A_{t}&B_{s}^{*}\\ B_{s}&\mathbf{I}+C_{s}\end{pmatrix}$$

Using the Schur complement, we get

$$\begin{pmatrix}\mathbf{I}+A_{t}&B_{s}^{*}\\ B_{s}&\mathbf{I}+C_{s}\end{pmatrix}=\begin{pmatrix}\mathbf{I}&0\\ B_{s}(1+A_{t})^{-1}&\mathbf{I}\end{pmatrix}\begin{pmatrix}\mathbf{I}+A_{t}&B_{s}^{*}\\ 0&\mathbf{I}+C_{s}-B_{s}(I+A_{t})^{-1}B_{s}^{*}\end{pmatrix}$$

which is valid since $\mathbf{I}+A_{t+s}$ is positive definite. By expanding the relation $(\mathbf{I}+T_{t+s})(\mathbf{I}+T_{t+s})=\mathbf{I}+A_{t+s}$, one can show that that $(\mathbf{I}+X_{s})(\mathbf{I}+X_{s}^{*})=\mathbf{I}+C_{s}-B_{s}(\mathbf{I}+A_{t})^{-1}B_{s}^{*}$, and therefore

$$\det\begin{pmatrix}\mathbf{I}+A_{t}&B_{s}^{*}\\ B_{s}&\mathbf{I}+C_{s}\end{pmatrix}=\det\begin{pmatrix}\mathbf{I}+A_{t}\end{pmatrix}\det\begin{pmatrix}\mathbf{I}+X_{s}+X_{s}^{*}+X_{s}X_{s}^{*}\end{pmatrix}.$$ (2)

Lemma 1.

Assume $T$ is continuous in a neighbourhood around $(t,t)$ as a function on the closed lower triangle. Then

$$\lim_{s\rightarrow 0}\frac{\det(I+X_{s}+X_{s}^{*}+X_{s}X_{s}^{*})-1}{s}=M(t,t).$$ (3)

ie.

$$\frac{d}{ds}\det(I+X_{s}+X_{s}^{*}+X_{s}X_{s}^{*})\Big{|}_{s=0}=M(t,t)$$

Proof.

Define $Y_{s}:=X_{s}+X_{s}^{*}+X_{s}X_{s}^{*}$.

Since $T$ is continuous, $X_{s}$ is bounded and hence the kernel for $X_{s}X_{s}^{*}$ decreases rapidly towards zero for $s\rightarrow 0$. Using continuity of $T$ in $(t,t)$, we conclude that the kernel of $Y_{s}$ deviate from $T(t,t)$ by less than $\epsilon_{s}$ where $\epsilon_{s}\rightarrow 0$ for $s\rightarrow 0$.

Using dominated convergence on the terms of the Fredholm determinant (indexed by $n$ starting from zero), we will show that all higher-order terms of eq. (3) vanish in the limit, leaving an expression resembling a first-order Taylor expansion.

Let $n\geq 2$. The corresponding entry in the Fredholm determinant of $Y_{s}$ is:

$$\frac{1}{n!}\int_{[0,s]^{n}}\det[(Y_{s})(x_{p},x_{q})]_{p,q=1}^{n}\>\mathrm{d}x_{1}\dots\>\mathrm{d}x_{n}<\\ s^{n}(T(t,t)+\epsilon_{s})^{n}$$

which tend to zero for $s\rightarrow 0$ when multiplied by $s^{-1}$. The entry for $n=1$ is

$$\int_{0}^{s}\!Y_{s}(x,x)\>\mathrm{d}{x}$$

which multiplied by $s^{-1}$ converges to $T(t,t)$ for $s\rightarrow 0$. The entry for $n=0$ is trivially 1.

Now select $\tilde{s}>0$ such that $\epsilon_{\tilde{s}}<1$ and $\tilde{s}(T(t,t)+1)<\tfrac{1}{2}$. Then

$$s^{-1}(d(Y_{s})-1)<s^{-1}\int_{0}^{s}\!Y_{s}(x,x)\>\mathrm{d}{x}+\sum_{n=2}^{\infty}s^{n-1}(T(t,t)+\epsilon_{s})^{n}<\\ s^{-1}\int_{0}^{s}\!(T(t,t)+1)\>\mathrm{d}{x}+\sum_{n=2}^{\infty}\tilde{s}^{n-1}(T(t,t)+1)^{n}<\\ {(T(t,t)+1)}+(T(t,t)+1)\sum_{n=2}^{\infty}(1/2)^{n-1}$$

for $0<s<\tilde{s}$. Hence we may apply the dominated convergence theorem and conclude

$$\lim_{s\rightarrow 0}s^{-1}(Fd(Y_{s})-1)=\lim_{s\rightarrow 0}\left(-s^{-1}+\sum_{n=0}^{\infty}\frac{1}{s(n!)}\int_{[0,s]^{n}}\det[(Y_{s})(x_{p},x_{q})]_{p,q=1}^{n}\>\mathrm{d}x_{1}\dots\>\mathrm{d}x_{n}\right)=\\ \sum_{n=1}^{\infty}\lim_{s\rightarrow 0}\frac{1}{s(n!)}\int_{[0,s]^{n}}\det[(Y_{s})(x_{p},x_{q})]_{p,q=1}^{n}\>\mathrm{d}x_{1}\dots\>\mathrm{d}x_{n}=T(t,t)$$

This proves the result. ∎

Now, returning to $A_{t+s}$,

$$\frac{d}{dt}\det(\mathbf{I}+A_{t})=\lim_{s\rightarrow 0}\frac{\det(\mathbf{I}+A_{t+s})-\det(\mathbf{I}+A_{t})}{s}=\\ \det(\mathbf{I}+A_{t})\lim_{s\rightarrow 0}\frac{\det(\mathbf{I}+X_{s}+X_{s}^{*}+X_{s}X_{s}^{*})}{s}=\det(\mathbf{I}+A_{t})M(t,t)$$

using Eq (2) and Lemma 1. Therefore,

$$\frac{d}{dt}\log\det(\mathbf{I}+A_{t})=T(t,t)$$ (4)

Using that $\det(\mathbf{I}+A_{0})=1$ and integrating (4), we get

$$\log\det(\mathbf{I}+A_{t})=\int_{0}^{t}\!T(s,s)\>\mathrm{d}{s},\quad 0\leq t\leq 1$$

∎

Discussion

The Fredholm determinant has a definition (Eq. 1) which makes it very hard to evaluate by direct calculation. This work presents a simple and elegant solution to this problem using the Cholesky decomposition. Naturally, applications of Theorem 1 rely on knowing the Cholesky decomposition of the operator $\mathbf{I}+A$. One approach is to do applications with triangular matrices as the building block: we design or propose a triangular operator $T$ (or a class of triangular operators), and then construct the positive definite matrix $\mathbf{I}+A=(\mathbf{I}+T)(\mathbf{I}+T^{*})$.