# Proving by induction that strictly lower triangular matrix is nilpotent

Let matrix $$A \in \mathbb{K}^{n \times n}$$ have the property $$a_{ij} = 0$$ for $$1 \leq i \leq j \leq n$$. Show that $$A^n = 0$$.

Proof by induction:

Base Case:

for $$n=2: A= \left[ {\begin{array}{cc} 0 & 0 \\ a_{21} & 0 \\ \end{array} } \right]$$

So $$A^2 = \left[ {\begin{array}{cc} 0 & 0 \\ a_{21} & 0 \\ \end{array} } \right] \cdot \left[ {\begin{array}{cc} 0 & 0 \\ a_{21} & 0 \\ \end{array} } \right] = \left[ {\begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} } \right]$$

Inductive Hypothesis(IH):

Assume $$A^n = 0$$ holds true for some $$n$$.

Inductive Step:

$$n \rightarrow n+1$$, to show: $$A^{n+1} = 0$$

$$A^{n+1} = A^n \cdot A =^{IH} 0 \cdot A = 0$$

It seems to be too simple. Is it correct to prove this by induction?

• First check if your inductive step really takes you from $n=2$ to $n=3$. Can you see what the problem is? Dec 15 '19 at 11:18

Yes, induction is certainly a good way to try and prove the result. However, there are some problems with your attempt to do so.

One problem is that the $$\ A\$$ in your induction hypothesis is an $$\ n\times n\$$ matrix, whereas the one in your induction step has to be an arbitrary $$\ (n+1)\times(n+1)\$$ matrix satisfying the stated conditions. That means it cannot be the same $$\ A\$$ as the one appearing in the induction hypothesis.

To fix the proof, your induction hypothesis must be something like $$"\ A^n = 0\$$ for all strictly lower triangular $$\ n\times n\$$ matrices $$\ A\$$." Also, in the induction step, an identity you will probably find useful is $$\pmatrix{B&0 _{n\times1}\\b^\top&0}^k=\pmatrix{B^k&0 _{n\times1}\\b^\top B^{k-1} &0}\ ,$$ for any $$\ n\times n\$$ matrix $$\ B\$$ and $$\ n\times1\$$ column vector $$\ b\$$.

• $\pmatrix{B&0 _{n\times1}\\b^\top&0}^k=\pmatrix{B^k&0 _{n\times1}\\b^\top B^{k-1} &0}\$ How did you get from one side of the equation to the other? Dec 15 '19 at 18:00
• Shouldn't it be something like this: $\pmatrix{0_{1\times(n-1)}&0\\B&0_{(n-1)\times1}}^k$. Since a Matrix B is wrapped around in zeros. Dec 15 '19 at 18:19
• The identity is clearly true for $\ k=1\$, and if it holds for some given $\ k\$, then \begin{align} \pmatrix{B&0 _{n\times1}\\b^\top&0}^{k+1}&= \pmatrix{B&0 _{n\times1}\\b^\top&0}\pmatrix{B^k&0 _{n\times1}\\b^\top B^{k-1} &0}\\ &= \pmatrix{B^{k+1}&0 _{n\times1}\\b^\top B^k&0}\ , \end{align} so the identity holds for every $\ k\$ by induction. Dec 15 '19 at 20:16
• The point of the identity is that if $\ A\$ is *any* strictly lower triangular $\ (n+1)\times (n+1)\$ matrix, then it *must be* true that $$A= \pmatrix{B&0 _{n\times1}\\b^\top&0}\ ,$$ where $\ B\$ is a *strictly lower triangular* $\ n\times n\$ matrix. While it's also true that $$A= \pmatrix{0_{1\times n}& 0\\C&0_{n\times1}}\ ,$$ where $\ C\$ is an $\ n\times n\$ matrix, $\ C_{11}=A_{21}\$ is not necessarily $0$ in this case, so $\ C\$ is not necessarily strictly lower triangular, so I don't see how that decomposition would be of any use for proving the result by induction. Dec 15 '19 at 20:17

If you try to deduce the $$n=3$$ case from $$n=2$$ that you describe, this happens:

$$\begin{pmatrix} 0 & 0 & 0 \\ a_{21} & 0 & 0 \\ a_{31} & a_{32} & 0 \end{pmatrix}^{3} = \begin{pmatrix} 0 & 0 & 0 \\ a_{21} & 0 & 0 \\ a_{31} & a_{32} & 0 \end{pmatrix}^{2} \begin{pmatrix} 0 & 0 & 0 \\ a_{21} & 0 & 0 \\ a_{31} & a_{32} & 0 \end{pmatrix}$$ You can't conclude that $$A^2 = 0$$ because this matrix is $$3\times 3$$ and not $$2\times 2$$ like your previous case.