Lesson 8

We derive the theorem from the following lemma.

Lemma. For \(S \subseteq E\), such that \(|S|=n-1\), the following holds: \[|\det(I_{i}[S])|= \begin{cases}1,&\text{if \(S\) is a spanning tree,}\\ 0&\text{otherwise.}\end{cases}\] Proof. If \(S\) is not a tree, then it contains a cycle. Take the edges of this cycle and orient them somehow—for example, clockwise. Next, take those columns whose edge orientations match the chosen one with coefficient \(1\), and the remaining ones with coefficient \(-1\). It is easy to see that such a linear combination equals zero: for each vertex of the cycle, there is one incoming and one outgoing edge. Hence, the determinant is zero.

Now assume that \(S\) is a tree, and prove that the absolute value of the determinant is equal to one using induction on \(n\). Base case \(n=2\): in this case \[I[S]=\begin{pmatrix}1\\-1\end{pmatrix} \ ,\] so \(I_{i}[S]=\pm 1\) and \(|\det(I_{i}[S])|=1\).

Inductive step \(n-1 \to n\). A tree with at least two vertices has at least two leaves, so choose a leaf \(j \ne i\), and let \(k\) be its neighbor. Rearrange the remaining rows and the columns of the matrix so that vertex \(j\) becomes the last row, and edge \(\{k,j\}\) becomes the last column. This operation may change the sign of the determinant, but we are only evaluating its absolute value. Then, in the last row, only the bottom-right element is \(\pm 1\), while all others are zero. Therefore, the modulus of the determinant \(I_{i}[S]\) is equal to the modulus of the determinant of its upper-left submatrix of size \((n-1) \times (n-1)\). This submatrix corresponds to removing vertex \(j\) and edge \(\{k,j\}\). At the same time, the set \(S \setminus \{\{k,j\}\}\) remains a tree on the remaining vertices, so we continue by induction.◼