I have an exercise in discrete math about matrix representation of relations that I want to be sure I have solved properly:
How many non-zero entries does the matrix representing the following relations on $A=\{1,2,3,\ldots,1000\}$ consisting of the first $1000$ positive integers have if $R$ is:
a) $R=\{(a,b)\mid a+b=1000\}$
b) $R=\{(a,b)\mid a+b\leq1001\}$
c) $R=\{(a,b)\mid a\neq0\}$
In the c case, one million since every entry will be 1.
In the a case, every entry, from the first one to the 999-th one, excluding the 1000th row, will have one non-zero entry, so 999
In the b case the whole first row satisfies the condition, the whole second row satisfies the condition and in the third row everything but the entry (3,999) satisfies the condition. In the fourth, everything but (4,999) and (4,998) satisfies the condition.
So we will have $1000 + 1000 + 999+998+997…+1$ non-zero entries in the matrix representing the relation. $999+998+997…+1 = 99(100) / 2 $
So we have $499500 + 2000 = 501500$ non zero-entries.
Is this the right way to solve the exercise?
Thanks a lot
Best Answer
Your answers to parts (a) and (c) are correct.
In row $k$, there are $1001 - k$ entries which satisfy the condition since we require that $k + b \leq 1001 \implies b \leq 1001 - k$. Hence, the number of admissible ordered pairs is $$\sum_{k = 1}^{1000} (1001 - k) = \sum_{n = 1}^{1000} n = \frac{1000 \cdot 1001}{2} = 500,500$$ where $n = 1000 - k$.