How to prove that the number of diagonals of a $M \times N$ matrix is $M+N-1$?

Question

Given a matrix $M \times N$, how to prove that the number of diagonals that can be drawn, like in the figure below, is equal to $M + N - 1$?

My idea would be to prove it with induction and consider the 3 possible cases: $M=N$, $M>N$ and $M<N$. But I don't know how to do it.

@Angle For a moment I've thought it was possible to use the Induction principle both on $M$ and $N$, but I was so wrong — reuseman, Jul 29 '18 at 10:43
So this means that there are 3 cases to consider $M=N$, $M>N$, $M<N$ with $M$ fixed, and other 3 with $N$ fixed? — reuseman, Jul 29 '18 at 10:46
No, just go from a matrix $M\times N$ to a matrix with one more row, that is a matrix $M\times N+1$. — nonuser, Jul 29 '18 at 10:47

score 3 · Accepted Answer · answered Jul 29 '18 at 10:36

3

This is a counting problem.

Start at the first row and count diagonals passing through elements on the first row. You get $N$ of those.

Now go down through the last column and you get $M$ of those.

There is one which is counted twice, so the total is $M+N-1$

answered Jul 29 '18 at 10:36

Mohammad Riazi-Kermani

68,728

Is this a valid way to prove it for all the possible values of $M$ and $N$? – reuseman Jul 29 '18 at 10:44
Yes, it works for all values of $M $and $N$. Go through some examples and you figure it out. – Mohammad Riazi-Kermani Jul 29 '18 at 10:46

score 0 · Answer 2 · answered Jul 29 '18 at 11:35

Each entry of the matrix is given by the row number $i$ and the column number $j$, and we say that $(i,j)$ is the index of this entry. Notice that the $k$-th diagonal is defined by $(i,j)$-entries with $i+j=k+1$. Since $i\in\{1,2,\ldots,M\}$ and $j\in\{1,2,\ldots,N\}$, we see that $$k=i+j-1\in\{1,2,\ldots,M+N-1\}\,.$$

Each $k\in\{1,2,\ldots,M+N-1\}$ corresponds to a nonempty diagonal line. For $k=1,2,\ldots,M$, the $k$-th diagonal contains the entry indexed by $(k-1,1)$. For $k=M+1,M+2,\ldots,M+N-1$, the $k$-th diagonal contains the entry indexed by $(M,k+1-M)$.

How to prove that the number of diagonals of a $M \times N$ matrix is $M+N-1$?

2 Answers2