MHB Induction to find the determinant

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Suppose we have the matrix $A_n=(A_{ij})\in \mathbb{C}^{n\times n}$ with $a_{ij}=\left\{\begin{matrix}
1 , & i=j\\
-1 , & i=j-1\\
j^2, & i=j+1\\
0 , & \text{ otherwise}
\end{matrix}\right.$ for $1\leq i,j\leq n$.

I want to find the determinant using induction.

I have done the following:

To see the patern I have made some examples:

For $n=2$ we have the matrix $A_2=\begin{pmatrix}1& -1 \\ 1& 1\end{pmatrix}$. The determinant is $|A_2|=\begin{vmatrix}1& -1 \\ 1& 1\end{vmatrix}=2=n(n-1)$.

For $n=3$ we have the matrix $A_3=\begin{pmatrix}1& -1& 0 \\ 1 & 1 & -1 \\ 0 & 4 & 1\end{pmatrix}$. The determinant is $|A_3|=\begin{vmatrix}1& -1& 0 \\ 1 & 1 & -1 \\ 0 & 4 & 1\end{vmatrix} \ \ \overset{R_2=R_2-R_1}{ = } \ \ \begin{vmatrix}1& -1& 0 \\ 0 & 2 & -1 \\ 0 & 4 & 1\end{vmatrix}=\begin{vmatrix} 2 & -1 \\ 4 & 1\end{vmatrix}=2-(-4)=6=n(n-1)$. So, we want to prove that the determinant is $|A_n|=n(n-1)$, for $n\geq 2$, right? (Wondering) Induction on $n$.

Base case: For $n=2$, as shown above, it holds.

Inductive hypothesis: We suppose that it holds for $n=k$, i.e., $|A_k|=k(k-1)$.

Inductive step: We want to prove it for $n=k+1$, i.e., that it holds that $|A_{k+1}|=(k+1)k$. When we consider the matrix without the last row and without the last column, it is the matrix $A_k$.

But what is the relation between the determinant of $A_k$ and that of $A_{k+1}$ ? (Wondering)
 
Physics news on Phys.org
I did some more examples, and I think that the determinant of $A_n$ is $n!$.

The matrix is of the form $$A_k=\begin{pmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-1)^2& 1 & -1\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& k^2 & 1\end{pmatrix}$$

Since at the last row all the elements are zero, except of two, we have the following:
$$|A_k|=\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-1)^2& 1 & -1\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& k^2 & 1\end{vmatrix} \\ =(-1)^{k+k-1}k^2\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-1)^2 & -1\end{vmatrix}+(-1)^{k+k}\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-1)^2& 1 \end{vmatrix}$$

The second summand is $|A_{k-1}|$ and the first one is the following:

$$\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-1)^2 & -1\end{vmatrix}=-(-1)^{2k-2}\begin{vmatrix}1& -1 & 0 & 0 & \ldots & 0 \\ 1 & 1 & -1 & 0 & \ldots & 0 \\ 0 & 4 & 1 & -1 &\ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & 0 & \ldots & 1\end{vmatrix}=-|A_{k-2}|$$ Is this correct? (Wondering)
 
Last edited by a moderator:
I did a mistake at the matrix. It must be as follows:

In the inductive step we have the matrix:
$$|A_{k+1}|=\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 &0 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots & \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & -1 & 0\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & 1 & -1 \\ 0 & 0 & 0& 0 & 0 & \ldots & 0& 0 & k^2 & 1 \end{vmatrix}$$

As for the ast line we get:
\begin{align*}|A_{k+1}|=&(-1)^{k+1+k}k^2\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & 0\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & -1 \end{vmatrix} \\ & +(-1)^{k+1+k+1}\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & -1 \\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & 1 \end{vmatrix} \\ = & -k^2\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & 0\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & -1 \end{vmatrix} \\ & +\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 &0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots \\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & -1 \\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & 1 \end{vmatrix}\end{align*}

The second term is the determinant of the matrix $A_k$. To calculate the first term of the sum, we develop as for the last column:
$$\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots& \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 & 0\\ 0 & 0 & 0& 0 & 0 & \ldots & 0& (k-1)^2 & -1 \end{vmatrix} \\ =(-1)^{k+k}\cdot (-1)\cdot \begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 \end{vmatrix} \\ =- \begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 \end{vmatrix}$$

The determinant $\displaystyle{\begin{vmatrix}1& -1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 4 & 1 & -1 & 0 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0& 0 & 0 & \ldots & (k-2)^2& 1 \end{vmatrix}}$ is the determinant of the matrix $A_{k-1}$. Therefore, we have \begin{align*}|A_{k+1}|&=-k^2\cdot (-|A_{k-1}|)+|A_k|=k^2|A_{k-1}|+|A_k|=k^2(k-1)!+k! \\ &=k\cdot k(k-1)!+k! =k\cdot k!+k!=k!\cdot (k+1) =(k+1)!\end{align*} Is everything correct? Could we improve something or write it more formal? (Wondering)
 
Back
Top