Matrices are graphs
Tivadar Danka
I want to democratize machine learning. Math PhD with an INTJ personality. Chaotic good.
The single most undervalued fact of linear algebra: matrices are graphs, and graphs are matrices.
Encoding matrices as graphs is a cheat code, making complex behavior simple to study.
Let me show you how!
If you looked at the example above, you probably figured out the rule. Each row is a node, and each element represents a directed and weighted edge. The element in the ??-th row and ??-th column corresponds to an edge going from ?? to ??.
Why is the directed graph representation beneficial for us? For one, the powers of the matrix correspond to walks in the graph. Take a look at the elements of the square matrix. All possible 2-step walks are accounted for in the sum defining the elements of A2.
If the directed graph represents the states of a Markov chain, the square of its transition probability matrix essentially shows the probability of the chain having some state after two steps.
There is much more to this connection. For instance, it gives us a deep insight into the structure of nonnegative matrices. To see what graphs show about matrices, let's talk about the concept of strongly connected components.
A directed graph is strongly connected if every node can be reached from every other node. Below, you can see two examples where this holds and doesn't hold.
Matrices that correspond to strongly connected graphs are called irreducible. All other nonnegative matrices are called reducible.
Soon, we'll see why. (For simplicity, I assumed each edge to have unit weight, but each weight can be an arbitrary nonnegative number.)
Back to the general case!
Even though not all directed graphs are strongly connected, we can partition the nodes into strongly connected components.
领英推荐
Let's label the nodes of this graph and construct the corresponding matrix! (For simplicity, assume that all edges have unit weight.) Do you notice a pattern?
The corresponding matrix of our graph can be reduced to a simpler form. Its diagonal comprises blocks whose graphs are strongly connected. (That is, the blocks are irreducible.) Furthermore, the block below the diagonal is zero.
In general, this block-matrix structure is called the Frobenius normal form.
Let's reverse the question: can we transform an arbitrary nonnegative matrix into the Frobenius normal form? Yes, and with the help of directed graphs, this is much easier to show than purely using algebra.
We have already seen the proof:
Without going into the details, renumbering the nodes is equivalent to reordering the rows and the columns of our original matrix, resulting in the Frobenius normal form.
This is just the tip of the iceberg. For example, with the help of matrices, we can define the eigenvalues of graphs! Utilizing the relation between matrices and graphs has been extremely profitable for both graph theory and linear algebra.
Having a deep understanding of math will make you a better engineer.
I want to help you with this, so I am writing a comprehensive book about the subject. If you are interested in the details and beauties of mathematics, check out the early access!
Software Engineer - Infrastructure @PitchBook Data | Java/Kotlin | Senior Java Developer
11 个月The concept of encoding matrices as graphs is like a cheat code indeed. Awesome article??
Research Intern @CVC UAB | Prev Visiting Researcher, UGRIP @ MBZUAI | @CVIT IIIT-H | Computer Vision | 2x Merit Scholarship Awardee |
2 年When you understand the fact that linear algebra is not just solving equations to get answers, you will begin to love the beauty of maths. Btw, great article.
Decarbonising European Heating as a Solutions Engineer @ Gradyent
2 年Lisa-Marie Mueller Shervin Azadi Pirouz Nourian May be of interest ??
Failed at entrepreneurship; succeeding in remote software work
2 年Not all of the them!
??Mathematics in particular Linear Algebra is ubiquitous. ??We cannot reach our destination without travelling the path of Linear algebra... Mathematicians know the hack around... Thanks for sharing ??