matrix representation of relations over A = <mo fence="false" stretchy="false">{ 1 ,

Abram Boyd

Abram Boyd

Answered question

2022-06-14

matrix representation of relations over A = { 1 , 2 , 3 , , 1000 }
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 , , 1000 } consisting of the first 1000 positive integers have if R is:
a) R = { ( a , b ) a + b = 1000 }
b) R = { ( a , b ) a + b 1001 }
c) R = { ( a , b ) a 0 }
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?

Answer & Explanation

rioolpijpgp

rioolpijpgp

Beginner2022-06-15Added 19 answers

Your answers to parts (a) and (c) are correct.
Step 1
In row k, there are 1001 k entries which satisfy the condition since we require that k + b 1001 b 1001 k.
Step 2
Hence, the number of admissible ordered pairs is k = 1 1000 ( 1001 k ) = n = 1 1000 n = 1000 1001 2 = 500 , 500 where n = 1000 k.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?