Matrix determinant as Dickson polynomial $\frac{x^{n+1}-y^{n+1}}{x-y}$

Question

Given matrix $$ A=\begin{bmatrix} x+y&xy&0& .&.&. &0\\ 1&x+y&xy&0& .&.&0 \\ 0&1&x+y&xy&.&.&. \\ .&.&.&.&.&.&. \\ .&.&.&.&.&.&0 \\ .&.&.&.&.&.&xy \\ 0&.&.&.&0&1&x+y \end{bmatrix} $$

prove by induction that $$|A|=\frac{x^{n+1}-y^{n+1}}{x-y}$$ $x \neq y$, $A_{n \times n}$.

The determinant expression appears to be Dickson polynomial of second kind.

Let $D_n$ be the determinant of $A_n$. We can see that the appropriate recurrence relation is $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$

Base cases: $$D_1=x+y=\frac{x^2-y^2}{x-y}$$

$$ D_2=(x+y)^2-xy=x^2+xy+y^2=\frac{x^3-y^3}{x-y} $$

Suppose that $$D_n=(x+y)D_{n-1}-xyD_{n-2}$$ Then we need to prove that $$D_{n+1}=(x+y)D_{n}-xyD_{n-1}$$

Which can be developed as: $$ D_{n+1}=(x+y)((x+y)D_{n-1}-xyD_{n-2})-xyD_{n-1}= $$ $$ =(x+y)^2D_{n-1}-xy(x+y)D_{n-2}-xyD_{n-1}= $$ $$ =(x^2+xy+y^2)D_{n-1}-xy(x+y)D_{n-2}= $$ $$ =\frac{x^3-y^3}{x-y}D_{n-1}-xy(x+y)D_{n-2} $$

I tried doing this up to $D_{n-6}$ in order to get any insights into possible simplification but I'm pretty stuck.

Answer 1

Your base cases are good. For the induction step, assume that $$D_n=\frac{x^{n+1}-y^{n+1}}{x-y}\quad \text{and}\quad D_{n-1}=\frac{x^{n}-y^{n}}{x-y}.$$ Then you have that $$D_{n+1}=(x+y)D_n-xyD_{n-1},$$so you only have to show that $$(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y}=\frac{x^{n+2}-y^{n+2}}{x-y}.$$ Developping the LHS gives you \begin{align}(x+y)\frac{x^{n+1}-y^{n+1}}{x-y}-xy\frac{x^{n}-y^{n}}{x-y} & = \frac{x^{n+2}+x^{n+1}y-xy^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1}}{x-y}\\ & = \frac{x^{n+2}-y^{n+2}}{x-y}.\end{align}

Answer 2

A linear algebra approach to the recurrence relation is to write it in matrix form: $$\mathcal{D}_n\equiv \begin{pmatrix} D_{n} \\ D_{n-1}\end{pmatrix}=\begin{pmatrix} x+y & -xy\\1 & 0 \end{pmatrix}\begin{pmatrix} D_{n-1} \\ D_{n-2}\end{pmatrix}\equiv M \mathcal{D}_{n-1},\hspace{4mm} \mathcal{D}_0 = \binom{1}{0}.$$ (I choose $D_0=1,D_{-1}=0$ so that the recurrence for $D_n$ in terms of $D_{n-1},D_{n-2}$ valid for $n\geq 1$.) Then $D_n=(\mathcal{D}_n)_1=(M^n \mathcal{D}_0)_1=(M^n)_{11},$ so computing $D_n$ amounts to matrix multiplication. But the eigenvalues and eigenvectors are simple enough in this case, yielding the spectral decomposition $$M=\Lambda D \Lambda^{-1}=\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x & 0 \\ 0 & y\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1}$$ and therefore \begin{align} M^n &=(\Lambda D \Lambda^{-1})^n \\ &= \Lambda D^n \Lambda^{-1} \\ &= \begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}\begin{pmatrix}x^n & 0 \\ 0 & y^n\end{pmatrix}\begin{pmatrix}x & y \\ 1 & 1\end{pmatrix}^{-1} \\ &= \begin{pmatrix}x^{n+1} & y^{n+1} \\ x^n & y^n\end{pmatrix}\cdot \frac{1}{x-y}\begin{pmatrix}1 & -y \\ -1 & x\end{pmatrix}\\ &=\frac{1}{x-y}\begin{pmatrix}x^{n+1}-y^{n+1} & x y^{n+1}-x^{n+1}y \\ x^{n}-y^{n}& xy^{n}-yx^{n}\end{pmatrix}. \end{align} From the upper-left corner we read off the anticipated result.

Answer 3

You did the base cases $n=1,2$, then you do the inductive step using strong induction; suppose your claim is true for any $m \leq n$, then using the recursive formula, for $n \geq 3$: \begin{align} D_{n+1} &=(x+y)D_n-xyD_{n-1} =\\ &=(x+y)\frac{x^{n+1}-y^{n+1}}{x-y} -xy\frac{x^n-y^n}{x-y} = \\ &= \frac{1}{x-y}(x^{n+2}-xy^{n+1}+yx^{n+1}-y^{n+2}-x^{n+1}y+xy^{n+1})= \\ &= \frac{x^{n+2}-y^{n+2}}{x-y} \end{align} which proves the claim for $m=n+1$. By induction, the claim is true for any $n$.