# User:DVD206/Special matrices and determinants

An important object containing information about a graph 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*_{i} → *v*_{j} means that the vertex *v*_{j} is a neighbor of *v*_{i}.

**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 a 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 *L(G)* if

Let

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

Then the **Schur complement** of the block *D* of the matrix *M* is the matrix

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

Suppose the graph *G* has *N* boundary nodes then the hitting probability matrix is such that the entry *h(ij)* equals to the probability that the next boundary vertex that a particle starting its random walk at the boundary vertex *v_i* occupies is the boundary vertex *v_j*. The columns of the matrix *H(G)* add up to *1*. We will derive an explicit formula for the matrix *H(G)* in terms of the blocks of Laplace matrix *L(G)* of the graph G.

The following matrix *W(G)* of sums over weighted paths in a graph plays an important role as boundary measurement for inverse problems:

**Exercise (*).** Prove that for two different boundary vertices of *G*,

The following exercise will play an important role in the solution of an inverse boundary problem.

**Exercise (**).** Prove that on the following picture the areas of the triangles are equal and

Note: the picture is not symmetric w/respect to the *x = y* line.