# Month: June 2015 « Comme pour n’importe quel tableau, chaque faux suppose une recherche. Un peintre, qu’il soit faussaire ou non, est, toute sa vie, un étudiant qui se met à l’école de l’art. Je n’ai pas fait un seul Matisse ou un seul Renoir, je les ai faits en dix exemplaires, jusqu’à ce que je comprenne leur nature et leur sens. On ne peut pas créer une œuvre de cette importance du premier coup. On commet des erreurs, on détruit, on recommence… » Guy Ribes (1948 – ) in Autoportrait d’un faussaire, p. 120, 2015.

La lecture de l’autoportrait de Guy Ribes est passionnante ! On y trouve le récit d’une vie romanesque, une description sans fard du marché de l’art, mais aussi, au fil des pages, une réflexion pleine de fraîcheur sur la création et l’originalité. Peut-on classer les artistes en créateurs et interprètes ? La réalité est beaucoup plus complexe, en peinture comme en musique ou en mathématiques. D’une certaine manière, les mathématiciens sont eux aussi des faussaires, créant bien souvent des œuvres à la manière de, comme le faisait Guy Ribes.

« Qu’est-ce que, au fond, un peintre ? C’est un collectionneur qui veut se constituer une collection en faisant lui-même les tableaux qu’il aime chez les autres. C’est comme ça que je commence et ça devient autre chose. … C’est par ce qu’on ne réussit pas à imiter un maître qu’on fait quelque chose d’original. » Pablo Picasso (1881 – 1973), in Daniel-Henry Kahnweiler Huit entretiens avec Picasso, Le Point, Mulhouse, n°XLII, oct. 1952, p. 22-30.

This post is devoted to the Gustav Kirchhoff formula which expresses the invariant measure of an irreducible finite Markov chain in terms of spanning trees. Many of us have already encountered the name of Gustav Kirchhoff in Physics classes when studying electricity.

Let ${X={(X_t)}_{t\geq0}}$ be a continuous time Markov chain with finite state space ${V=\{1,\ldots,n\}}$, and with infinitesimal generator or Q-matrix ${Q}$, meaning that

$Q_{i,j}=\partial_{t=0^+}\mathbb{P}(X_t=j|X_0=i), \quad \mathbb{P}(X_t=j|X_0=i)=\left(e^{tQ}\right)_{i,j}.$

The off-diagonal entries of ${Q}$ are non-negative and the rows of ${Q}$ have zero sum:

$\forall i,j\in V, \quad i\neq j, \quad Q_{i,j}\geq0, \quad Q_{i,i}=-\sum_{k\neq i}Q_{i,k}.$

The skeleton graph ${G=(V,E)}$ of ${Q}$ is the oriented graph defined by

$(i,j)\in E\quad\mathrm{iff}\quad Q_{i,j}>0.$

Let us assume that ${Q}$ is irreducible, which means that ${G}$ is connected. The Perron-Frobenius theorem states then that there exists a unique invariant probability measure, in other words ${\mathrm{ker}(Q^\top)}$ contains up to scaling a unique vector with positive coordinates. We will provide an explicit formula for it!

Since the sum of the columns of ${Q}$ is zero, it follows that for every ${i,j\in V}$,

$(\mathrm{cof}(-Q))_{i,j}:=(-1)^{i+j}\det(-Q^{(i,j)})=\det(-Q^{(i,i)})=:\mu_i.$

In other words the cofactors matrix of ${-Q}$ has constant rows (identical columns). Now by expanding the determinant along an arbitrary column ${j\in V}$ we get

$0=\det(-Q)=-\sum_{i=1}^nQ_{i,j}(-1)^{i+j}\det(-Q^{(i,j)}) =-\sum_{i\in V}Q_{i,j}\mu_i$

which shows that the vector ${{(\mu_i)}_{i\in V}}$ is invariant for ${Q}$. The fact that ${{(\mu_i)}_{i\in V}}$ has positive coordinates follows from the Kirchhoff formula

$\mu_i:=\det(-Q^{(i,i)})=\sum_{T\in\mathcal{T}_i}\prod_{(j,k)\in T}Q_{j,k}$

where the sum runs over the set ${\mathcal{T}_i}$ of spanning trees of ${G}$ rooted at ${i}$. Recall that a spanning tree or covering tree of ${G}$ rooted at ${i\in V}$ is a sub-graph of ${G}$ with edge set ${V}$ which is a tree rooted at ${i}$. Note that ${\mathcal{T}_i}$ is non-empty since ${G}$ is connected. Note that ${\mathcal{T}_1,\ldots,\mathcal{T}_n}$ do not have necessarily the same cardinal due to the fact that the edges are oriented: a covering tree rooted at ${i}$ contains any ${j}$ as a vertex but not necessarily as a possible root due to the arrows.

To prove the Kirchhoff formula, one can first label from ${1}$ to ${m=|E|}$ the edges of ${G}$, and define an ${n\times m}$ matrix ${L}$ called the incidence matrix as follows: if ${(i,j)}$ is the ${k}$-th edge of ${G}$ then ${L_{i,k}=Q_{i,j}^{1/2}}$, ${L_{j,k}=-Q_{i,j}^{1/2}}$, and ${L_{\cdot,k}=0}$ otherwise. Now

$-Q=LL^\top.$

We also have ${Q^{(i,i)}=L^{(i)}(L^{(i)})^\top}$. Next we use the Cauchy-Binet formula

$\det(-Q^{(i,i)}) =\sum_{s}\det(L^{(i,s)})^2$

where ${s}$ runs over the subsets of cardinality ${m-(n-1)}$. Every ${s}$ specifies ${n-1}$ edges of ${G}$. It can then be shown that these edges induce a spanning tree iif ${\det(L^{(i,s)})\neq0}$.

Random walk. Suppose now that ${Q_{i,j}\in\{0,1\}}$ for every ${i,j\in V}$ with ${i\neq j}$. Then ${X}$ is the nearest neighbors random walk on ${G}$, the diagonal of ${-Q}$ is formed by the degree sequence of ${G}$, and ${Q}$ is the Laplacian ${\Delta_G}$ of ${G}$. In this case ${Q_{j,k}=1}$ for every ${(j,k)\in G}$ and thus the Kirchhoff formula above boils down to

$\forall i\in V,\quad \mu_i=|\mathcal{T}_i|.$

Suppose now that ${Q}$ is additionally symmetric, meaning that ${G}$ is not oriented in the sense that ${(j,k)\in E}$ iff ${(k,j)\in E}$. In this case the invariant probability measure of ${Q}$ is then the uniform law on ${V}$. Due to the absence of orientation, the sets ${\mathcal{T}_1,\ldots,\mathcal{T}_n}$ have the same cardinal ${\kappa}$, which is the number of spanning trees of ${G}$ (without rooting). We have

$\forall i,j\in V,\quad \mu_i=(\mathrm{cof}(-Q))_{i,j}=(-1)^{i+j}\det(-Q^{(i,j)}) =|\mathcal{T}|_i=\kappa.$

In other words the cofactors matrix of the Laplacian of a non-oriented graph has constant entries equal to the number of spanning trees of the graph.

Let us connect ${\kappa}$ with the eigenvalues of the the symmetric matrix ${-Q}$, numbered as

$0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_n.$

Here ${\lambda_1}$ is simple since ${Q}$ is irreducible. The characteristic polynomial of ${-Q}$ is

$P_{-Q}(x)=\det(xI_n+Q)=x(x-\lambda_2)\cdots(x-\lambda_n).$

By looking at the coefficient of ${x}$ in this polynomial we get (Jacobi formula)

$(-1)^{n-1}\lambda_2\cdots\lambda_n =(-1)^{n-1}\mathrm{Tr}(\mathrm{cof}(-Q))$

which gives finally the remarkable Kirchhoff formula

$\lambda_2\cdots\lambda_n=n\kappa.$

(note that the left hand side is thus necessarily an integer!). Let us show how to recover from this formula the so-called Cayley formula which states that the complete graph ${K_n}$ possesses ${n^{n-2}}$ covering trees. In this case ${G=K_n}$ and ${-Q=nI-J}$ where ${J}$ is the ${n\times n}$ matrix full of ${1}$. The matrix ${-J}$ has rank ${1}$, its eigenvalues are ${0}$ with multiplicity ${n-1}$ and ${-n}$ with multiplicity ${1}$, and thus it follows that the eigenvalues of ${-Q}$ are ${0}$ with multiplicity ${1}$ and ${n}$ with multiplicity ${n-1}$. Hence ${\lambda_2=\cdots=\lambda_n=n}$ and finally ${\kappa=n^{n-2}}$.

Wilson algorithm. David Wilson invented an exact algorithm to generate a spanning tree of ${G}$ which follows the uniform distribution on the set of spanning trees of ${G}$. Starting from vertex ${1}$, the algorithm consists in setting ${A_1=\{1\}}$, and to simulate a path of the simple random walk on ${G}$ started from vertex ${2}$ until it reaches ${A_1}$. Then ${A_2}$ is the union of ${A_1}$ and of the loop erased version of this path. If ${A_2=V}$, the algorithm is stopped. If not, then we redo the same starting this time the path from smallest vertex not in ${A_2}$, stopping the path when it reaches ${A_2}$, and so on. The Wilson algorithm can be naturally related to the Green function of the random walk on ${G}$ with Dirichlet boundary conditions on a subset of ${V}$.

Markov matrix tree theorem. The Kirchhoff formula provides an exact and non-asymptotic formula for the invariant probability measure of a finite Markov chain (this is sometimes referred to as the Kirchhoff Markov matrix tree theorem). This is remarkable, and constitutes an alternative to the asymptotic formula

$\forall i,j\in V,\quad \mu_j=\left(\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{k=0}^{m-1} e^{kQ}\right)_{i,j}.$