# Combination Problem With Relations?

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.

-

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.

-
Wow, that was brilliant! For class, we read a section on the basics of counting, and a section on permutations and combinations, is this a technique that we should learned in that section? If not, using the information from those sections, could we solve this problem? – Mack Nov 5 '12 at 18:28
@EMACK. It actually requires a prerequisite bit of information on sums of series, namely that $1+2+\cdots+n = n(n+1)/2$. This probably wouldn't be a direct part of what you did in permutations and combinations, but there's a very good chance that such sums were mentioned there. – Rick Decker Nov 5 '12 at 19:30
I don't intend to be bothersome, but I edited my post by adding another question; and I was wondering, should I have started a new thread? Do other users get a notification that I edited my post? – Mack Nov 6 '12 at 13:17
@EMACK. It's generally preferred that you post a new question, rather than editing your question to include a new topic. That will cause your question to appear on the main page, where it'll (briefly) be prominent. That increases the chance of getting answers. For your second question, no, respondents don't get notified that you edited your post. – Rick Decker Nov 6 '12 at 15:01

Hint: For $A = \{1,2,3,4\}$, the matrix looks like this $$(a_{i,j}) = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix}$$ where $a_{i,j} = 1$ if $\:\: i \,R\, j$. That matrix has $0 + 1 + \ldots + (4-1) = 0 + 1 + 2 + 3 = 6$ non-zero entries.

-
I can see how that works in your example, and I am sure it works in my problem, but I can't see it. I'm sorry. – Mack Nov 5 '12 at 15:57
@EMACK Where's the problem? In your problem, the matrix has 100 rows and columns, but it looks the same (i.e, it has ones below the diagonal, and zeros everywhere else). You thus have $0 + 1 + 2 + 3 + \ldots + 99$ ones... – fgp Nov 5 '12 at 19:40