1
$\begingroup$

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?

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

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\ $.

$\endgroup$
4
  • $\begingroup$ $\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? $\endgroup$
    – franz3
    Dec 15 '19 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – franz3
    Dec 15 '19 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 15 '19 at 20:16
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 15 '19 at 20:17
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.