Introduction to Graph Theory · Problem 5.27

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · determinant-tridiagonal-matrix

Problem

Let

n

be a positive integer. Let

A

be the

(n-1) \times (n-1)

-matrix

\begin{pmatrix} 2 & -1 & 0 & \cdots & 0 \\ -1 & 2 & -1 & \cdots & 0 \\ 0 & -1 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 2 \end{pmatrix},

whose

(i, j)

-th entry is

A_{i,j} := \begin{cases} 2, & \text{if } i = j; \\ -1, & \text{if } |i - j| = 1; \\ 0, & \text{otherwise} \end{cases} \qquad \text{for all } i, j \in \{1, 2, \ldots, n-1\}.

Prove that

\det A = n

. [Hint: Recall Example 5.4.4.]