Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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?

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.