[Math] Relations Represented As Matrices

discrete mathematicsmatricesrelations

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+1\}$?

I rewrote the condition for an ordered-pair to be in the relation 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

HINT: Look at a smaller example: replace $100$ by $5$, say. Now you have

$$M_R=\begin{bmatrix} 0&0&0&0&0\\ \color{red}{1}&0&0&0&0\\ 0&\color{red}{1}&0&0&0\\ 0&0&\color{red}{1}&0&0\\ 0&0&0&\color{red}{1}&0 \end{bmatrix}\;.$$

Is the pattern a bit clearer now?

Related Solutions

[Math] Partial Order Relations and Total Order Relations

Counting the partial order relations is a bit messy. Perhaps the most straightforward way is to organize them by their ‘shapes’. In the following diagrams the order is from bottom to top.

They can be linear:
```
 *  
 |  
 *  
 |  
 *
```
They have a minimum element but no maximum:
```
 *   *  
  \ /  
   *  
```
They can have a maximum but no minimum:
```
   *  
  / \  
 *   *
```
They can have two related elements and one unrelated element:
```
 *  
 |   *  
 *
```
They can have three unrelated elements:
```
 *   *   *
```

You’ve already counted the partial orders that are linear: there are indeed $3!=6$ of them. Now you just have to count the partial orders of types (2)-(5) above. To get you started, in type (2) any one of the three elements of $A$ can be the minimum element. Once you’ve chosen that, however, the partial order is completely determined:

    1   2                  2   1  
     \ /        and         \ /  
      3                      3

are the same partial order, just drawn differently. Thus, there are $3$ partial orders of type (2) on $A$.

[Math] Combination Problem With Relations

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.

Best Answer

Related Solutions

[Math] Partial Order Relations and Total Order Relations

[Math] Combination Problem With Relations

Related Question