# 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 _{G}* is triangular.

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.

**Exercise (*).** Prove that a function/vector *u* is harmonic at the interior nodes of a graph *G* if

Let

be a block matrix with an invertible square block *D*.

Then the Schur complement of the matrix *M* w/respect of the block *D* is the matrix

The Leibniz definition of **determinant** (a multilinear function in the rows and columns) of a square *n* by *n* matrix *M* is:

**Exercise (*).** Prove the following determinant identity for a square matrix *M*:

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 *W(G)* in terms of the blocks of Laplace matrix *L(G)* 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*

- 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],

**Exercise (***).** Give a proof of a Menger's theorem based on the results of the exercise above: Let *G* be a finite graph and *p* and *q* two vertices that are not neighbors. Then the size of the minimum vertex cut for *p* and *q* (the minimum number of vertices whose removal disconnects *p* and *q*) is equal to the maximum number of pairwise vertex-independent paths from *p* to *q*.