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:

$l_{ij}:={\begin{cases}\sum _{v_{i}\rightarrow v_{j}}w_{ij}{\mbox{ if}}\ i=j,\\-w_{ij}{\mbox{ if}}\ v_{i}\rightarrow v_{j},\\0,{\mbox{ otherwise,}}\end{cases}}$

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.

$L(G)={\begin{pmatrix}A&B\\C&D\end{pmatrix}}$

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

$u|_{intG}=-D^{-1}Cu|_{\partial G}.$

Let

$M=\left[{\begin{matrix}A&B\\C&D\end{matrix}}\right]$

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

$M/D=A-BD^{-1}C.$

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

$\det M=\det(M/D)\det D.$

Suppose the graph G has N boundary nodes then the hitting probability matrix $H(G)=\{h_{ij}\}$ 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:

$W(G)=D_{A}^{-1}(D_{A}-A)+(D_{A}^{-1}B)(\sum _{k}(D_{D}^{-1}(D_{D}-D))^{k}D_{D}^{-1}C=I-D_{A}^{-1}(A-BC^{-1}D).$

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

$w_{kl}=\sum _{v_{k}{\xrightarrow[{}]{path}}v_{l}}\prod _{e\in path}l(e)/l_{kk}.$

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

$c={\frac {\det {\begin{bmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{bmatrix}}}{(a_{1}-a_{2})+(b_{2}-b_{1})}}.$

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