Using the matrix tree theorem to compute a matrix determinant

672 Views Asked by At

Use the matrix tree theorem to compute the determinant of the $n × n $ matrix with entries

$$a_{ij} = \begin{cases} 2 & \text{if $i=j$} \\ -1 & \text{if $i=j \pm 1$} \\ 0 & \text{otherwise} \end{cases}$$

I know how to do this for a specified n value but not sure how to do this as a general case.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the cycle $C_{n+1}$ on $n+1$ vertices with all edges weighted $1$. Then the laplacian of $C_{n+1}$ has $2$ on the diagonal, $-1$ on the super and sub diagonal, and $-1$ at $a_{1,n+1}, a_{n+1,1}$. Then if we remove the first row and first column, we get the matrix you described.

One version of the matrix tree theorm states that the determinant of the submatrix of the lapcian obtained by removing the $i$th row and $i$th column is equal to the number of spanning trees rooted at vertex $i$. It is not hard to see there are $n+1$ such spanning trees in $C_{n+1}$, since spanning trees are exactly obtained by removing one edge from the graph.

Hence the determinant of your matrix is $n+1$.

Here is a reference (I use matrix tree theorem version 2).