Triangles, Triangular Numbers, and the Adjacency Matrix

One of the cool things about math is that there are many interconnections and interrelations between the various ideas and concepts and looking at things from a broader perspective can often be enlightening.

The area of a triangle is something that we learn in elementary school, its formula, often stated as one half the base times the height, is:

It’s pretty basic stuff, perhaps even boring.

In Number Theory and Discrete Math there is a sequence of numbers known as the Triangular numbers, each triangular number (T_n) is the sum of all the integers up to an including itself. For example

T₁ = 1 = 1

T₂ = 1 + 2 = 3

T₃ = 1 + 2 + 3 = 6

T₄ = 1 + 2 + 3 + 4 = 10

…

T_n = 1 + 2 + 3 + ... + (n -1) + n

These can be generalized by the following formula:

The capital Sigma notation is Summation, which is equivalent to the following simple Java code snippet:

public int triangularNumber(int n)

int result = 0;

for(int k = 1; k <= n; k++) {

result += k;

}

return result;

}

Triangular numbers are the additive analog to the factorial function, i.e. the addition of 1..n vs. the multiplication of 1..n to and can also computed recursively:

T_n = n + T_n-1

T_n = n + ((n - 1) + T_n-2)

. . .

T_n = n + (n - 1) + ... + 2 + 1

Which can be implemented in Java as:

public int triangularNumber(int n)

if(1 == n)

return n;

else

return n + triangularNumber(n - 1);

}

Triangular numbers can be drawn visually as a triangle made up of dots, the first 5 triangular numbers are 1, 3, 6, 10 and 15:

There is another, better way, to compute triangular numbers, a closed formula that Gauss¹ came up with when he was a child:

If you assign (n + 1) to be the base and (n) to the height, the formula bears a striking resemblance to the formula for the area of a triangle, seen visually as:

As you can see the base of the triangle ends being one larger than the actual size of the triangle and results in an "area" is larger than would be expected by the continuous area. I think this might be doing the equivalent to what the ceiling function does to round up and acquire the "extra bits" of the discrete case. This triangle was referred to by Fermat as the Collateral Triangle, although I think the term "discrete triangle" is better, and this concept relates to the differences between discrete and continuous mathematics. This is explored in more detail by David J. Pengelley specifically in the following the paper: "The bridge between the continuous and the discrete via original sources" and partial chapter: "The Bridge Between Continuous and Discrete". Actually his work, especially in regards to the Collateral Triangle aka discrete triangle was something of a missing link for my ideas here.  The following graph was derived from a graph in one of his papers.  I refactored it to use the function y=x and pimped it out a bit to better demonstrate my triangle theme, visually shows the differences between the discrete and continuous "areas" in terms of Summation and Integration:

                  

         

The "area" of discrete vs. continuous triangles

The diagram shows how the discrete area picks up more in that jagged edge than the continuous area does and ends up being a larger quantity, n/2 to be exact as seen in the formulas, this is the type of graph that is usually used as an introduction to integral calculus to show how integration works, where in the continuous world the rectangular sections are infinitesimal.  In this example the function y = x creates an area under its curve that is a unique² triangle, drawn in red, the famous 45-45-90 triangle which is both right and isosceles and in this case the height and base are equal, both the value of n so the area is (n*n)/2 which is the result of the above integral which measures the area of the red triangle where height = n and  base = n.  The discrete triangle, Fermat’s Collateral Triangle, is superimposed into each 1 x 1 cell of the graph as light blue circles with its area represented by the summation below the diagram and to the left.  Also note that integration and Summation are continuous and discrete analogs of each other.  I think there’s probably a lot more to this but that’s all I need for my purposes so I’m going to have to leave it there.

Triangular numbers have the property if you add two consecutive triangular numbers they add to a square which can be expressed as the following equation:

T_n-1 + T_n = n²

This addition can be seen visually as:

T₄ + T₅ =  10 + 15  =  5²  =  25

Since, from our recursive definition, T_n = n + T_n-1 we can rewrite (T_n-1 + T_n = n²) from above as:

T_n-1 + T_n-1 + n  =  2 ∙ T_n-1 + n  =  n²

This can be seen visually as:

2 ∙ T₄ + 5  =  2 ∙ 10 + 5  =  5²  =  25

Another pattern in drawing triangular numbers is to replace the dots with ones (hold this thought for a moment):

Triangular numbers show up in Graph Theory, the Complete Graph, the graph where all vertices are connected to every other vertex exactly once, will have T_{n -1} edges for a graph with n vertices, the complete graph is denoted as K_n.  The first three examples are:

T₁, T₂, and T₃ are the count of edges for K₂, K₃, and K₄. So if we define the function E(G) where G is a graph and E(G) is the edge count, i.e. number of edges in the graph, then E(K_n)=T_n-1, this only applies to the Complete Graphs K_n not all graphs. 

The formula for the E(K_n) and T_n-1 is:

Let’s consider the graph K₆:

Now in looking at the fully constructed graph we don’t really get a true sense intuitively about the relation to triangular numbers so let’s look the construction from an inductive and combinatorial perspective:

So let’s build K₆. We’ll start with vertex 1 which is blue and draw an edge (a blue line) to each other vertex which results in 5 blue edges.

 

Now we move (clockwise and numerically increasing) to vertex 2 in green, since we already have a blue line back to vertex 1 we don’t draw another, remember: no repeated edges. So we will only draw edges to vertices that we have not visited yet which leaves 4 remaining which are drawn in green.

As we continue this we add 3 red edges, 2 yellow, 1 black, and 0 purple since we have connected to all vertices upon reaching this last vertex.

As shown in the above diagram in the appropriate colors, the edges are added as 5 + 4 + 3 + 2 + 1 which is the 5^th Triangular Number for K₆ with 6 vertices.  Also this inductive construction is similar to the above recursive function; remember recursion and induction are related, except you would call it with (n - 1) e.g. triangularNumber(n -1).

The Adjacency Matrix is a way to represent the edges between vertices in a Matrix. For a graph of n vertices it has the form:

Each position a_r,c where r is the row and c is the column represents an edge, or possibly a count of edges, that connects vertex number r to vertex number c. The following gives the template structure for the matrix for K₆:

As you can see from the above matrix that each colored edge maps to the corresponding adjacency element, edge 1 –> 2 is represented by the blue a_1,2 and that all of the 1 -> n and n -> 1 edge elements appear in blue and this pattern repeats for all the colored edges. For this example we are only going to consider Simple Graphs, usually just referred to as Graphs, which only have one edge between any two edges as opposed to Multigraphs which allow edges to repeat between vertices so all elements of the matrix can only be either 0 or 1.  Also we are not considering graphs which have Loops so the diagonal where each the row equals the column a_i,i will always be 0.  So our template will now take the (très triangular) form:

We are only considering the Adjacency Matrix for the Undirected Graph which will have the property that the upper right triangular portion will be symmetric to the lower left triangular portion, or in other words the terms a_i,j and a_j,i are equal: a_i,j = a_j,i, this is referred to as a Symmetric Matrix.  From our colorful K₆ example from above we have the following adjacency matrix.  The color which maps to the edges to their representation in the matrix also helps illuminate the symmetry, if you visualize rotating the matrix around the diagonal of zeros you can see that they are the same.

Also you may have noticed, and this is not a coincidence, that this structure is very similar to our square constructed from n and the two  T_n-1 triangles (T_n-1 + T_n-1 + n). If you rotate the above square by 90 degrees either in a clockwise or counterclockwise direction and replace the black dots with zeros and the blue dots with ones you get the adjacency matrix for the K_n graph.

Well this is my first, but not last "pure" math post, except perhaps for the two code snippets.  I feel that these concepts are important and relevant to programmers and probably willso all positions of the graph can either be 0 or 1 only be more so in the future, the Adjacency Matrix is pretty important regarding anything relating to graph Theory like the Page Rank Algorithm or Social Network Theory, there is a lot more to say about it and I have at least one follow on post planned in this area as well.  The goal here was to present the Adjacency Matrix in a context that makes it more interesting and intuitive, and to convey some of the beauty of these structures, hopefully I succeeded in some small measure to do that.  I admit my approach here is somewhat unconventional and I may have taken some artistic license with some ideas such as the terms combinatorial and inductive, but I think they fit. Also I am not sure I fully understand the concept of area in the discrete context.  I hope you found this as enjoyable to read as I found it to write.  When I first had the idea I realized that I needed to draw a number of images, Processing really came in handy and was a blast to use for it, and it has given me a whole new perspective on geometric/graphical programming and visualization, I hope to do more with it including writing about it.  Additionally LaTex has been great for creating math expressions.

¹This was also known to ancient mathematicians.

²Only one right-isosceles triangle exists in Euclidean Geometry.