# On 2D Inverse Problems/Special matrices

An important object containing information about a weighted graph *G(V,E,w)* is its **Laplacian matrix**. Given a numbering of the vertices of the graph, it's an *n* by *n* square matrix *L _{G}*, where

*n*is the number of vertices in the graph, with the entries:

where *v*_{k} → *v*_{l} means that there is a directed edge from vertex *v*_{k} to the vertex *v*_{l}, and where *w* is the weight function.

**Exercise (*)**. Given a directed graph*G*without cycles, prove that one can number its vertices so that the corresponding Laplacian matrix*L*is triangular._{G}

Given a weighted graph with boundary it is often convenient to number its boundary vertices first and to write its Laplacian matrix in the block form.

The **Schur complement** of the matrix w/respect of the invertible block *D* is the matrix

**Exercise (*).**Prove the following determinant identity:

The following matrix *W(G)* consisting of random walk exiting probabilities (sums over weighted paths in a graph) plays an important role as boundary measurement for inverse problems. Suppose a weighted graph *G* has *N* boundary nodes, then the *kl* 'th entry of the *N* by *N* matrix equals to the probability that the first boundary vertex, that a particle starting its random walk at the boundary vertex *v _{k}* occupies, is the boundary vertex

*v*. For a finite connected graph the columns of the matrix

_{l}*W(G)*add up to

*1*.

**Exercise (**).**Derive an explicit formula for the matrix in terms of the blocks of Laplace matrix of the graph*G*:

**Exercise (***).**Prove the following expansion formulas for entries and blocks of the matrix*W(G)*,

- for two boundary vertices
*p*and_{k}*p*of a graph_{l}*G*

Hint: use the Leibniz definition of the determinant

- for two distinct boundary vertices
*v*and_{k}*v*of a graph_{l}*G*

where

- for two disjoint subsets of boundary vertices
*P*and*Q*of size*n*of a graph*G*, see [6],[7] and [14]

where

The exercises above provide a bridge b/w connectivity property of graph *G* and ranks of submatrices of its Laplacian matrix *L(G)* and the matrix of hitting probabilities *W(G)*.

**Exercise (*).**Let*G*be a planar graph w/natural boundary, numbered circulary. Let*P*and*Q*be two non-interlacing subsets of boundary nodes of size*n*. Prove that

w/the strict inequality iff there is a disjoint set of paths from *P* to *Q*.

**Exercise (*).**Show that the numbers of paths in the following graph are equal to the binomial coefficients.

Gluing the graphs w/out loops corresponds to multiplication of the weighted paths matrices.

**Exercise (**).**Use the result of the previous exercise to it to prove the following**Pascal triangle**identity, see[13],