User:Daviddaved/Special matrices and determinants

< User:Daviddaved

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 vivj means that the vertex vj is a neighbor of vi.

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


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:


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.

Expressing area of a traingle in terms of determinant of a matrix

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.