MHB Show by induction that the determinant is equal to n

[mathmari]

Hey!

For $n\in \mathbb{N}$ let $A_n$ be the real $n\times n$-matrix with the elements \begin{equation*}a_{ij}=\begin{cases}i , &\text{ if } i=j-1 \\ 1, & \text{ if } i=j \\ -j, & \text{ if } i=j+1 \\ 0 , & \text{ otherwise } \end{cases}\end{equation*}

For $n=1, 2, 3$ we get the matrices :
\begin{equation*}A_1=\begin{pmatrix}1\end{pmatrix} , \ \ A_2=\begin{pmatrix} 1 & 1 \\ -1 & 1\end{pmatrix}, \ \ A_3=\begin{pmatrix}1 & 1 & 0 \\ -1 & 1 & 2 \\ 0 & -2 & 1 \end{pmatrix}\end{equation*}

The determinants are:
\begin{align*}\det (A_1)&=1 \\ \det (A_2)&=\begin{vmatrix} 1 & 1 \\ -1 & 1\end{vmatrix}=1\cdot 1-(-1)\cdot 1=1+1=2 \\ \det (A_3)&=\begin{vmatrix}1 & 1 & 0 \\ -1 & 1 & 2 \\ 0 & -2 & 1 \end{vmatrix}\overset{ \text{ Sarrus } }{ = } \begin{vmatrix}1 & 1 & 0 \\ -1 & 1 & 2 \\ 0 & -2 & 1 \end{vmatrix}\begin{matrix}1 & 1 \\ -1 & 1 \\ 0 & -2\end{matrix} \\ & =1\cdot 1\cdot 1+1\cdot 2\cdot 0+0\cdot (-1)\cdot (-2)-0\cdot 1\cdot 0-(-2)\cdot 2\cdot 1-1\cdot (-1)\cdot 1 \\ & = 1+4+1 =6\end{align*} Now I want to show using induction for $n$ that \begin{equation*}\det (A_n)=n!=n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot 2\cdot 1\end{equation*}

I have done the following:

Base case: From the above we have that the statement holds for $n=1, 2, 3$, since $\det (A_1)=1=1!$, $\det (A_2)=2=2!$, $\det (A_3)=6=3!$. Induction hypothesis: Let $n\geq 2$. We assume that the statement holds for all $k\leq n$, i.e. that $\det (A_k)=k!$. (IH)

Or do we not use strong induction? (Wondering) Induction step: We want to show that the statement holds then also for $n+1$, i.e. that $\det (A_{n+1})=(n+1)!$.

Could you give me a hint how we could show that? Do we have to expand somehow to use the induction hypothesis? (Wondering)

 

[I like Serena]

Hey mathmari! (Wave)

Did you consider the Laplace expansion applied to, say, the bottom most row?

 

[mathmari]

Did you consider the Laplace expansion applied to, say, the bottom most row?

At that row all elements are equal to $0$ except the last two, which are $-(n-1)$ and $1$ respectively, right? (Wondering)

 

[I like Serena]

At that row all elements are equal to $0$ except the last two, which are $-(n-1)$ and $1$ respectively, right?

For an $(n+1)\times(n+1)$ matrix that should be $-n$ and $1$, shouldn't it? (Wondering)

 

[mathmari]

For an $(n+1)\times(n+1)$ matrix that should be $-n$ and $1$, shouldn't it? (Wondering)

Oh yes, I thought of a $n\times n$-matrix (Blush) But how can we know the formula for the expansion having a general matrix? I got stuck right now. (Wondering)

 

[I like Serena]

But how can we know the formula for the expansion having a general matrix? I got stuck right now.

Isn't the expansion:
$$\det A_{n+1} = 1\cdot \det A_n - (-n)\cdot \det B_n$$
where $B_n$ is $A_{n+1}$ with column $n$ and the bottom row removed? (Wondering)

 

[mathmari]

Isn't the expansion:
$$\det A_{n+1} = 1\cdot \det A_n - (-n)\cdot \det B_n$$
where $B_n$ is $A_{n+1}$ with column $n$ and the bottom row removed? (Wondering)

We have that \begin{equation*}A_{n+1}=\begin{pmatrix}A_n & v \\ -v^T & 1 \end{pmatrix}\end{equation*} where $v=\begin{pmatrix}0 \\ \vdots \\ 0 \\ n\end{pmatrix}$.

Applying the Laplace expansion to the bottom most row, we get \begin{align*}\det (A_{n+1})&=(-1)^{n+1+n}\cdot (-n)\cdot \det (B_n)+(-1)^{n+1+n+1}\cdot 1\cdot \det (A_n)\\ & =(-1)^{2n+1}\cdot (-n)\cdot \det (B_n)+(-1)^{2n+2}\cdot 1\cdot \det (A_n) \\ & = (-1)\cdot (-n)\cdot \det (B_n)+1\cdot 1\cdot \det (A_n) \\ & = n\cdot \det (B_n)+\det (A_n)\end{align*}

The matrix $B_n$ is the matrix $A_{n-1}$ together with the last column $v$ and the last row the last row of $A_n$, or not? (Wondering)

 

[I like Serena]

We have that \begin{equation*}A_{n+1}=\begin{pmatrix}A_n & v \\ -v^T & 1 \end{pmatrix}\end{equation*} where $v=\begin{pmatrix}0 \\ \vdots \\ 0 \\ n\end{pmatrix}$.

Applying the Laplace expansion to the bottom most row, we get \begin{align*}\det (A_{n+1})&=(-1)^{n+1+n}\cdot (-n)\cdot \det (B_n)+(-1)^{n+1+n+1}\cdot 1\cdot \det (A_n)\\ & =(-1)^{2n+1}\cdot (-n)\cdot \det (B_n)+(-1)^{2n+2}\cdot 1\cdot \det (A_n) \\ & = (-1)\cdot (-n)\cdot \det (B_n)+1\cdot 1\cdot \det (A_n) \\ & = n\cdot \det (B_n)+\det (A_n)\end{align*}

The matrix $B_n$ is the matrix $A_{n-1}$ together with the last column $v$ and the last row the last row of $A_n$, or not?

(Nod)

 

[mathmari]

(Nod)

If we apply the Laplace expansion to the last column of $B_n$, i.e. at $v$ we get $\det (B_n)=(-1)^{n+n}\cdot n\cdot \det (A_{n-1})=n\cdot \det (A_{n-1})$, or not?

So we get \begin{align*}\det (A_{n+1})&=n\cdot n\cdot \det (A_{n-1})+\det (A_n)\ \overset{\text{ Inductive hypothesis }}{ = } \ n\cdot n\cdot (n-1)!+n!=n\cdot n!+n!=(n+1)\cdot n! \\ & =(n+1)!\end{align*}

(Wondering)

 

[I like Serena]

If we apply the Laplace expansion to the last column of $B_n$, i.e. at $v$ we get $\det (B_n)=(-1)^{n+n}\cdot n\cdot \det (A_{n-1})=n\cdot \det (A_{n-1})$, or not?

So we get \begin{align*}\det (A_{n+1})&=n\cdot n\cdot \det (A_{n-1})+\det (A_n)\ \overset{\text{ Inductive hypothesis }}{ = } \ n\cdot n\cdot (n-1)!+n!=n\cdot n!+n!=(n+1)\cdot n! \\ & =(n+1)!\end{align*}

Yep.
And it turned out that we indeed needed strong induction. (Nod)

 

[mathmari]

Yep.
And it turned out that we indeed needed strong induction. (Nod)

Great! Thank you! (Smile)