How to prove that $\det(Z_{n}) = \det(Z_{n-1}) - \det(Z_{n-2})$?

Question

I'm given an $n \times n$ matrix $Z_{n}$ over $\mathbb{N}$ of which the entry in the $x$-th row and the $y$-th column equals 1 if $|x-y| < 1 $ or $ |x-y| = 1$ and zero otherwise. I'm trying to prove that for all $n \in \mathbb{N}$ where $n > 1$, the following statement holds.

$\det(Z_{n}) = \det(Z_{n-1}) - \det(Z_{n-2})$.

I tried proving this by induction but I'm not really sure how to use induction on recurrence relations, I only got that for $n = 2$ this must be right considering $\det(Z_{1}) =\det(Z_{0}) = 1$ and $\det(Z_{2}) = 0$ considering $Z_{2} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix} $.

Answer 1

We use cofactor expansion on the first row of $Z_n$ to find the determinant.

$\det(Z_n)=\underbrace{\left|\begin{matrix} 1&1&0&\cdots&0&0&0\\ 1&1&1&\cdots&0&0&0\\ 0&1&1&\ddots&0&0&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&\ddots&1&1&0\\ 0&0&0&\cdots&1&1&1\\ 0&0&0&\cdots&0&1&1 \end{matrix}\right|}_{n}\\= 1\times\underbrace{\left|\begin{matrix} 1&1&0&\cdots&0&0&0\\ 1&1&1&\cdots&0&0&0\\ 0&1&1&\ddots&0&0&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&\ddots&1&1&0\\ 0&0&0&\cdots&1&1&1\\ 0&0&0&\cdots&0&1&1 \end{matrix}\right|}_{n-1}+ (-1)\times\underbrace{\left|\begin{matrix} \not1&\not1&\not0&\not\cdots&\not0&\not0&\not0\\ 1&\not1&1&\cdots&0&0&0\\ 0&\not1&1&\ddots&0&0&0\\ \vdots&\not\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&\not0&0&\ddots&1&1&0\\ 0&\not0&0&\cdots&1&1&1\\ 0&\not0&0&\cdots&0&1&1 \end{matrix}\right|}_{n}\\= \det(Z_{n-1})+ (-1)\times\underbrace{\left|\begin{matrix} 1&1&\cdots&0&0&0\\ 0&1&\ddots&0&0&0\\ \vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&\ddots&1&1&0\\ 0&0&\cdots&1&1&1\\ 0&0&\cdots&0&1&1 \end{matrix}\right|}_{n-1 \text{ (expand on first column)}}\\= \det(Z_{n-1})+ (-1)\times\underbrace{\left|\begin{matrix} 1&\ddots&0&0&0\\ \ddots&\ddots&\ddots&\vdots&\vdots\\ 0&\ddots&1&1&0\\ 0&\cdots&1&1&1\\ 0&\cdots&0&1&1 \end{matrix}\right|}_{n-2}=\det(Z_{n-1})-\det(Z_{n-2})$

Answer 2

Perhaps this hint will help :)

As @Element118 says, think about the co-factor expansion (this is the usual way you compute the determinant when you first learn about it in linear algebra).

Answer 3

Considering $\mathrm{det}(Z_1) =\mathrm{det}(Z_0) = 1.$

For, $n = 2$, $$Z_2 = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix} $$ $$\mathrm{det}(Z_2) =\mathrm{det} \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix} = 1\cdot \mathrm{det}(Z_1) - 1\cdot 1\cdot \mathrm{det}(Z_0)=\mathrm{det}(Z_1) - \mathrm{det}(Z_0)(=0).$$

For, $n = k$, $$Z_k = \begin{pmatrix} 1 & 1 & 0 & \dots & 0\\ 1 & 1 & 1 & \dots & 0\\ \vdots &\vdots &\vdots & &\vdots \\ 0 & 0 & 0 & \dots & 1 \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix} $$ $$\mathrm{det}(Z_k) = \mathrm{det} \begin{pmatrix} 1 & 1 & 0 & \dots & 0\\ 1 & 1 & 1 & \dots & 0\\ \vdots &\vdots &\vdots & &\vdots \\ 0 & 0 & 0 & \dots & 1 \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}_{k\times k}$$ $$= 1\cdot \mathrm{det} \begin{pmatrix} 1 & 1 & 0 & \dots & 0\\ 1 & 1 & 1 & \dots & 0\\ \vdots &\vdots & \vdots & &\vdots \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}_{(k-1)\times (k-1)} - 1\cdot \mathrm{det} \begin{pmatrix} 1 & 1 & \dots & 0\\ 0 & 1 & \dots & 0\\ \vdots &\vdots & &\vdots \\ 0 & 0 & \dots & 1 \end{pmatrix}_{(k-1)\times (k-1)}$$

[Expanded based on the $R_1$.]

$$ = 1\cdot \mathrm{det} \begin{pmatrix} 1 & 1 & 0 & \dots & 0\\ 1 & 1 & 1 & \dots & 0\\ \vdots &\vdots & \vdots & &\vdots \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}_{(k-1)\times (k-1)} -1\cdot 1 \cdot \mathrm{det} \begin{pmatrix} 1 & 1 & 0 & \dots & 0\\ 1 & 1 & 1 & \dots & 0\\ \vdots &\vdots & \vdots & &\vdots \\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}_{(k-2)\times (k-2)}$$ [The second part is expanded based on the $C_1$.] $$ =\mathrm{det}(Z_{(k-1)})-\mathrm{det}(Z_{(k-2)}).$$