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

Question

Imagine I wanted to use the induction principle to prove that a certain proposition was true for diagonal matrices. The induction is done in the dimension of the matrix.

So, the induction basis is for $n=1$. However, at this basis, there is no difference between a diagonal matrix and a non-diagonal matrix. 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. Shouldn't the basis be $n=2$?

Any help would be appreciated.

Answer 1

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.

Answer 2

It depends on what you want to prove.

if you want to prove that

$\forall n\geq n_0$ a certain property $P_n$,

you have to begin by checking $P_{n_0}$.

then you take $n\geq n_0$ such that $P_n$ is true and you prove that $P_{n+1}$ is true.

Answer 3

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