6

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.

John Gowers
  • 24,959
An old man in the sea.
  • 5,241
  • 1
    If you want to prove something for all diagonal matrices, then $n=1$ is the correct starting point. The premise of being diagonal will likely be used somewhere in the induction step. If you start with $n=2$ then you would have only proven the proposition for diagonal matrices of size $\ge 2$, and you would have to go back and prove the case $n=1$ separately. – dxiv Oct 13 '16 at 19:39
  • 3
    You may not have used the assumption that the matrix is diagonal directly, but you did use the assumption that it is 1x1, which is stronger. – Ryan Reich Oct 13 '16 at 21:57
  • 5
    "So, how can we be sure that the reason it's right is due to being a diagonal matrix" - it doesn't matter. Heck, the very concept of the "reason why something is true" is too vague and ill-defined for us to try to prove anything about it. Proofs are all about why we know things are true, not why the things are true. – user2357112 Oct 13 '16 at 23:44

3 Answers3

12

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.

Andreas Blass
  • 71,833
  • 1
    +1. Exactly. This is part of my point. In the induction step, will have to assume there's a difference, and use that difference to prove that the implication is true. However, that difference is not present in the basis...

    To me, this doesn't seem to be an entirely 'canonical'/correct use of the principle...

     – An old man in the sea. Oct 13 '16 at 20:04
  • 2
    You don't need to assume there is a difference. You'll probably need to assume that you're dealing with diagonal matrices. It's conceivable that there's no difference, that the proposition is true for all matrices even though you're only trying to prove it for diagonal matrices. That wouldn't prevent you from giving a proof by induction for diagonal matrices. – Andreas Blass Oct 13 '16 at 20:07
  • Let's suppose the proposition was only true for diagonal matrices. In the proof of the implication we had to assumed the matrix was specifically diagonal, in a dimension where we can distinguish between being diagonal and not.

    What about in this case?

     – An old man in the sea. Oct 13 '16 at 20:17
  • 2
    OK, if the proposition is true only for diagonal matrices, then the assumption "diagonal" will have to be used in the proof. It can't really be used in the basis case, since it adds no information when $n=1$. So it will be used in the induction step, just as I said in my answer. – Andreas Blass Oct 13 '16 at 20:20
  • @Anoldmaninthesea. If you don't have to assume "diagonal" in the base case, nor in the inductive step, then the thing you are proving probably applies to all matrices not just diagonal ones. – user253751 Oct 14 '16 at 05:28
  • 2
    @Anoldmaninthesea: You need not expect that in a "canonical/correct" use of induction, the base case must use all the properties assumed for the theorem. 1 is often special, but it can still serve as your base. For that matter, if you can make the proof come out with the base case as $n = 0$ then by all means go ahead and do it: there are no matrices of dimension zero, and so a statement of the form "for all diagonal matrices of dimension $n$..." is vacuously true. But when you do this, you sometimes (not always) find that you need to handle a special case for $n = 1$ in the inductive step. – Steve Jessop Oct 14 '16 at 10:43
  • @SteveJessop: "there are no matrices of dimension zero" - eh, that depends on your definition. By the definitions I know, if you're considering 0-by-0 matrices to be a meaningful concept, there's exactly one 0-by-0 matrix, representing the one linear transformation from a 0-dimensional vector space to itself. – user2357112 Jan 03 '17 at 18:30
10

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

Community
  • 1
John Gowers
  • 24,959
1

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.

hamam_Abdallah
  • 62,951