On 2D Inverse Problems/Special matrices

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 LG, where n is the number of vertices in the graph, with the entries:

where vkvl means that there is a directed edge from vertex vk to the vertex vl, 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 LG 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.

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 vk occupies, is the boundary vertex vl. For a finite connected graph the columns of the matrix 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 pk and pl of a graph G

Hint: use the Leibniz definition of the determinant

  • for two distinct boundary vertices vk and vl of a graph G


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


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.
The numbers of the paths of the graph are binomial coefficients
The numbers of the paths of the graph are 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],