# Relations Represented As Matrices

The question is, "How many nonzero entries does the matrix representing the relation $R$ on $A=\{1,2,3,...,100\}$ consisting of the first $100$ positive integers have if $R=\{(a, b)|a=b+1\}$?

I rewrote the condition for an ordered-pair to be in the relation as $a-b=1$, just because it was a little more comprehensive.

I reasoned that, for the first row, there will be all in zeros in it; because if a=1 and b=1, the difference would be zero, which wouldn't satisfy the condition; furthermore, the b values, from then on, become increasingly larger, resulting in negative number differences. I knew from this that the rest of the ninety-nine rows would have at least one element in the row that was one. But as I went out to the fourth row, things became a little more tricky than I suspected. In the forth row, the first element is a zero, (4, 1) doesn't satisfy the condition; but the third element in the fourth row is a 1, (4,3) satisfies the condition. So, I am having a little trouble seeing the pattern.

-

HINT: Look at a smaller example: replace $100$ by $5$, say. Now you have

$$M_R=\begin{bmatrix} 0&0&0&0&0\\ \color{red}{1}&0&0&0&0\\ 0&\color{red}{1}&0&0&0\\ 0&0&\color{red}{1}&0&0\\ 0&0&0&\color{red}{1}&0 \end{bmatrix}\;.$$

Is the pattern a bit clearer now?

-

In your relation, the value of $a$ must be one more than the value of $b$, and this is possible for each $b = 1, 2, \dots, 99$, and for each such value of $b$, there is exactly one value of $a$ making $a = b+1$.

Thus there are exactly 99 pairs satisfying the relation, and hence exactly 99 entries in the matrix which are 1, and then $100^2-99 = 9901$ entries which are zero. I.e. there are exactly 99 nonzero entries.

-