Matrices Help Relationships

William A. McWorter Jr.

Once when I was a graduate student I had a conversation with a philosophy professor friend about epistomology. He said there is a problem with the referent theory of meaning. The planet Venus and the Morning Star have the same referent, the planet, but the phrases clearly have different meanings. Being a student of mathematics, I had recently learned that mathematicians treat relationships as objects like any other object. So I suggested "why not include relationships as referents?". Then the Morning Star would have as one of its referents the relationship between Venus and the morning, distinguishing that phrase from the planet Venus. The philospher said "then the universe would have too many objects". Not long after that I gave up on philosophy. It seemed to me that philosphers were not interested in the truth. They prefer to haggle endlessly over dilemmas.

Mathematicians turn relationships into objects by defining a relationship as a set of ordered pairs. For example, the relationship of "more famous than" between Phylis Diller (P), Jimmy Durante (J), and Elizabeth Taylor (E) would be recorded as the set of ordered pairs {(E,J),(J,P),(E,P)}, a set of objects. (E,J) means Elizabeth Taylor is more famous than Jimmy Durante, (J,P) means Jimmy Durante is more famous than Phylis Diller, and (E,P) means Elizabeth Taylor is more famous than Phylis Diller. This objectification of relationships has proved enormously useful in mathematics, but it has its limits. The above set of ordered pairs can represent other relationships, like "occurs earlier in the alphabetical ordering by first names", or uncharitably, "prettier than".

This same relationship can be recorded as a matrix. Label the rows and columns of matrix by E, J, and P. Place a 1 in a cell of the matrix provided the row label of the cell is related to the column label of that cell. Put zeros in all other cells of the matrix.

         E  J  P
     E | 0  1  1
     J | 0  0  1
     P | 0  0  0

This matrix is called the incidence matrix of the relationship. But why bother with this method of recording a relationship? Because the immensely powerful subject linear algebra, spreadsheet mathematics for those who don't know what linear algebra is, can now be brought to bear on the study of relationships.

But before we get into the applications of linear algebra to relationships, let's first exploit an obvious observation. The ones in an incidence matrix can be counted two different ways, by columns or by rows.

Consider the famous problem from the russian high school mathematics competition.

Show that the number of people in the world who have shaken hands an odd number of times is even.

Define a relationship between handshakes and people by "is a handshake involving person". Create the incidence matrix for this relationship with rows labelled by handshakes and columns are labelled by people.

          p1     p2      p3  ...
     h1 |                               Ph1
     h2 |                               Ph2
     h3 |                               Ph3
     .  |                                .
     .  |                                .
     .  |                                .
          Hp1     Hp2     Hp3 ...

Then there is a 1 in row hi, column pj if and only if hi is a handshake involving person pj.

We can't know where all the ones and zeros are in this incidence matrix but we do know some things. Each row has exactly 2 ones because a handshake involves 2 people. Hence, adding up all the ones in all the rows, Ph1 + Ph2 + ..., the total number of ones in the incidence matrix is an even number. The column sums, Hpj, all add up to this same even number. Therefore, the number of Hpj which are odd must be even. But, of course, each Hpj is the number of times that person pj shakes hands. Hence the number of people who shake hands an odd number of times is even.

In this vein let's try another problem. A deltahedron is a 3d figure whose faces are each equilateral triangles. The tetrahedron, octahedron, and the icosahedron are deltahedra. The tetrahedron has 4 faces, the octahedron 8 faces, and the icosahedron 20 faces. It turns out that all deltahedra have an even number of faces. To see why, set up the incidence matrix for the relationship between faces and edges of a deltahedron by "is a face containing the edge". For any deltahedron label the rows of the incidence matrix by the faces and its columns by the edges. Then each row of the incidence matrix has 3 ones because an equilateral triangle contains 3 edges. Hence the sum of all the ones in the incidence matrix is 3F, where F is the number of faces in the given deltahedron. Also, each column of the incidence matrix has exactly 2 ones because each edge is on two faces. Thus 3F=2E, where E is the number of edges of the deltahedron. Now, since 3 is relatively prime to 2, it follows that 2 must divide F, implying that a deltahedron must have an even number of faces.

Related material

  • Eigenvalues of an incidence matrix
  • Addition of Vectors and Matrices
  • Multiplication of a Vector by a Matrix
  • Multiplication of Matrices
  • Matrix Groups
  • Eigenvectors by Inspection
  • Vandermonde matrix and determinant
  • When the Counting Gets Tough, the Tough Count on Mathematics
  • Merlin's Magic Squares
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny