Can we use mathematical induction when induction basis is 'too' broad?

For $n=1$, a result for diagonal matrices is the same as that result for arbitrary matrices; a difference between the two situations shows up only when $n\geq2$. So, if you start the induction at $n=1$, the difference will show up only in the induction step, not in the basis of the induction. That is, if the result is correct only for diagonal matrices and not for all matrices, then you'll need to assume "diagonal" in the induction step, even though it didn't matter in the basis.


The induction principle you are trying to use is:

Suppose that $P(1)$ is true and that if $P(n)$ is true then $P(n+1)$ is true. Then $P(n)$ is true for all $n$.

In this case, $P(n)$ is the statement

For all diagonal matrices of dimension $n$, [...something...]

You are confused about showing that $P(1)$ is true, because every matrix of dimension $1$ is diagonal. The good news is that you needn't be worried about this - if you show that the statement is true for all $1\times 1$ matrices, then you've proved $P(1)$.

You worry that:

So, how can we be sure that the reason it's right is due to being a diagonal matrix, and not because it's non-diagonal matrix

But you needn't worry about this. The principle of induction says nothing about the reason that something is true.

In your case, it turns out that all $1\times 1$ matrices have your property, but once you switch to $2\times 2$ matrices, only the diagonal matrices have that property. But you've proved that if all $n\times n$ diagonal matrices have the property, then all $(n+1)\times(n+1)$ diagonal matrices have that property. So you can get from case $1$ to case $2$ as follows:

All $1\times1$ matrices have the property $\Rightarrow$

All diagonal $1\times 1$ matrices have the property (as you know, this is actually equivalent) $\Rightarrow$

All diagonal $2\times2$ matrices have the property (using the induction rule) $\Rightarrow$

All diagonal $3\times3$ matrices have the property (using the induction rule again) $\Rightarrow$

and so on

Tags:

Induction