Inspired by the hexagonal shape of France, I wondered: how many ways can we connect all its 6 vertex cities so that each can reach the others without any redundant paths, that is to say without cycles. It’s not like I’m trying to reinvent the wheel here. Honestly, I’m just showing off my knowledge of a beautiful problem that has been known to mankind for over 180 years (since 1847), three years before the term "matrix" itself was introduced by James Joseph Sylvester in 1850.
Data science is such a huge trend these days, but to be honest, I’m still not entirely sure what it actually means. I understand "data" and "science" individually, but the specific role of a data scientist/analyst still feels a bit vague. It makes me wonder: would those 19th-century mathematicians who pioneered matrix theory be considered data scientists by today’s standards?
Let’s take the hexagon below and think about how we can describe it using data, just 0s and 1s, and perhaps some +/- signs to indicate directions. By the way, my apologies to the people of Montpellier and Paris if my hexagonal map made you feel left out. No hard feelings intended! I’ll also make sure Lyon and anyone I forgot to mention gets a proper sorry.
Et voilà! Here is the data, represented in the following matrix M
| LS | SN | NT | NB | NN | TB | BN | NL | |
|---|---|---|---|---|---|---|---|---|
| v₁ | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| v₂ | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 |
| v₃ | 0 | 1 | -1 | -1 | -1 | 0 | 0 | 0 |
| v₄ | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 0 |
| v₅ | 0 | 0 | 0 | 1 | 0 | 1 | -1 | 0 |
| v₆ | 0 | 0 | 0 | 0 | 1 | 0 | 1 | -1 |
Each column in this matrix corresponds to one of the eight roads on the map of France above, and each row corresponds to a city, represented as a vertex $v_{i}$. For example, the first column corresponds to the edge from v1 (Lille) to v2 (Strasbourg) denoted by LS. That’s why the first row, where the road starts, has a -1, the row where it ends has a 1, and all other rows in the first column are 0. But nothing stops us from swapping the rows and columns so that the rows represent roads and the columns represent cities. Et voilà $M^{T}$, we’ve transposed the matrix!
$$ \begin{bmatrix} -1 & 1 & 0 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & 0 & 0 & -1 \end{bmatrix} $$
Let’s now multiply those matrices (6 × 8) and (8 × 6) to get a 6 × 6 matrix $ MM^{T} $, so that none of the matrices above feel offended.
$$ \begin{bmatrix} 2 & -1 & 0 & 0 & 0 & -1 \\ -1 & 2 & -1 & 0 & 0 & 0 \\ 0 & -1 & 4 & -1 & -1 & -1 \\ 0 & 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 0 & -1 & 3 \end{bmatrix} $$
Let’s see what the data tell us. One has to be a genius like me to notice that on the diagonal we get the degrees of the vertices, a number showing how many roads start from each city. For example, the 3rd vertex of Nice has 4 roads connecting to the city. As for the off-diagonal elements, we get either -1 or 0: -1 if the vertex is connected to another vertex, and 0 otherwise.
That’s it, we’ve seen the pattern. And don’t forget the word "pattern" comes from the French word patron, which itself comes from the Latin patronus, derived directly from pater, meaning "father". Some "Marseillaise" here would be nice... "Allons enfants de la Patrie..."
Now, what about the word "matrix"? In ancient Rome, a matrix (matrix/matrim) referred to a womb or a female animal kept for breeding. It was the "source" from which life was generated. So we’ve identified the "father", we’ve identified the "mother".
What remains, you might ask? Well, we need a child "Enfant"! Voyons! And to sound cool and keep up with current trends, we’ll call it an AI. Because that’s exactly what you get when you breed patterns with matrices
So, let’s try to determine the child of the "pattern" and "matrix" above… ah, damn it! As we can see, the rows are dependent. The sum of all the rows is 0. That means the determinant of this matrix is 0. No child… damn it!
It seems this pattern/matrix is not fertile, so we will amputate the first row and the first column and then see if the remaining 5x5 pattern/matrix is fertile or not
$$ \det \begin{bmatrix} 2 & -1 & 0 & 0 & 0 \\ -1 & 4 & -1 & -1 & -1 \\ 0 & -1 & 2 & -1 & 0 \\ 0 & -1 & -1 & 3 & -1 \\ 0 & -1 & 0 & -1 & 3 \end{bmatrix} = 29 $$
So this means The France hexagon graph above has 29 distinct ways to connect all its cities without creating closed cycles. Basically 29 baby-spanning-trees. So good luck with choosing names for the children. Slightly crazy challenge!
For a complete graph $K_n$ (where every city is connected to every other city), the total number of spanning tree-roads is:
$$T(K_n) = n^{n-2}$$
So, luckily I didn't start with $K_6$; otherwise, I would have had to draw all 1,296 of them
$$T(K_6) = 6^{6-2} = 6^4 = 1,296$$
I’m sorry if you were expecting to see neural networks in this post. But here’s some consolation: a neural network is essentially just a graph with a few (quite a few) tweaked patterns.