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\}$
Well, I know that $|A\times A|=100^2$. I also know that any of the ordered pairs where the first element in the pair is one won't won't be in the relation. There is only one ordered pair where 2 is the first element in the ordered pair, and satisfies the condition to be admitted into the relation, namely, $(2,1)$;in a similar fashion, for three, there are only the ordered-pairs $(3, 1)$ and $(3, 2)$. I know that I am required to use some sort of counting techniques, but I am not sure how to implement them.
I would appreciate your help, thank you!
I have another one, the relation is still on the same set, except the condition for an ordered-pair to be in the relation is different: $\{(a,b)|a=b+1\}$. I rewrote the condition 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.
Best Answer
You're almost there. You've correctly observed that there will be no 1s in the first row, a single 1 in the second row, two 1s in the third row, and so on up to 99 1s in the hundredth row. Then, to get the total number of 1s in your matrix you add up the 1s in each row. In other words you want the sum $$ S = 1 + 2 + 3 + \cdots + 97 + 98 + 99 $$ one way to do this is to observe that the sum is the same whether written front-to-back or back-to-front. In other words $$ \begin{align} S &= \ 1 + \ 2 + \ \ 3 + \cdots + 97 + 98 + 99 \\ S &= 99 + 98 + 97 + \cdots + 3 + 2 + 1 \end{align} $$ Now notice that if you add the two sums you'll see that the first terms in the sum, $1+99$, add to 100, as do the second terms, $2+98$, and the third terms, $3+97$ and in fact every pair of terms in the two sums add to 100 so adding both the sums above gives $$ 2S = (1+99) + (2+98) + (3+97) + \cdots + (97+3)+(98+2)+(99+1) $$ so we'll have $$ 2S = \underbrace{100 + 100 + \cdots 100 + 100}_{99\text{ terms}} = 100\cdot99 = 9900 $$ so $S=9900/2=4950$. So there will be 4950 1s in your matrix.
Another way to observe this is to break up your original matrix into three non-overlapping pieces: the main diagonal, the upper triangle (above the diagonal) and the lower triangle (below the diagonal). The upper triangle will contain nothing but zeros, the lower triangle will contain nothing but ones, and the diagonal will contain nothing but zeros. The upper and lower triangles will contain the same number of entries and the diagonal will contain 100 entries, so if we let $T$ be the number of entries in the lower triangle (equal to the number of entries in the upper triangle) we'll have $100\cdot100$ total entries in the matrix, so $100\cdot100=100+T+T$ and so we can solve for $T$ to find $T=(10000-100)=9900/2=4950$, so again there will be 4950 1s in the lower triangle.