How many nonzero entries does the matrix representing relati

How many non-zero entries does the matrix representing relation R on set of numbers {1, …1000} have if R = {(a, b) | a + b <= 1001}

Solution

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++97+98+99S=1+2+3++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

SS= 1+ 2+  3++97+98+99=99+98+97++3+2+1S= 1+ 2+  3++97+98+99S=99+98+97++3+2+1

Now notice that if you add the two sums you\'ll see that the first terms in the sum, 1+991+99, add to 100, as do the second terms, 2+982+98, and the third terms, 3+973+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)++(97+3)+(98+2)+(99+1)2S=(1+99)+(2+98)+(3+97)++(97+3)+(98+2)+(99+1)

so we\'ll have

2S=100+100+100+10099 terms=10099=99002S=100+100+100+10099 terms=10099=9900

so S=9900/2=4950S=9900/2=4950. So there will be 4950 1s in your matrix.