I am going to tell you the best-kept secret of linear algebra: matrices are graphs and graphs are matrices.
Encoding matrices as graphs is a cheat code, making complex behavior extremely simple to study.
Let me show you how!
🧵 👇🏽
Encoding matrices as graphs is a cheat code, making complex behavior extremely 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 of a row represents a directed edge.
The element in the 𝑖-th row, 𝑗-th column corresponds to the edge in the graph, going from 𝑖 to 𝑗.
(Formal definition below.)
Each row is a node, and each element of a row represents a directed edge.
The element in the 𝑖-th row, 𝑗-th column corresponds to the edge in the graph, going from 𝑖 to 𝑗.
(Formal definition below.)
Why is the directed graph representation beneficial for us?
The first example is that the powers of the matrix correspond to walks in the graph.
Take a look at how to calculate the elements of the square of a matrix.
The first example is that the powers of the matrix correspond to walks in the graph.
Take a look at how to calculate the elements of the square of a matrix.
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 are more significant implications of this connection.
For instance, it gives us a deep result about the structure of nonnegative matrices.
According to the Frobenius theorem, every nonnegative matrix 𝐴 can be written in a very special form.
For instance, it gives us a deep result about the structure of nonnegative matrices.
According to the Frobenius theorem, every nonnegative matrix 𝐴 can be written in a very special form.
(Multiplying with a matrix 𝑃 and its transpose from left and right is called similarity transformation. This just means that we view the linear transformation 𝐴 in a different coordinate system.
Check this explanation, if you would like to see more!
Check this explanation, if you would like to see more!
https://twitter.com/TivadarDanka/status/1361332789749104640)
This result is really hard to prove purely with algebra.
With graphs, it is much easier. You only have to prove that every directed graph can be partitioned into disjoint subsets where every two node of a given subset can be mutually reachable from each other.
With graphs, it is much easier. You only have to prove that every directed graph can be partitioned into disjoint subsets where every two node of a given subset can be mutually reachable from each other.
I'll leave the details up to you, but here is an illustration to help.
This is a simple visual idea, opposed to the complex algebraic original proof.
This is a simple visual idea, opposed to the complex algebraic original proof.
To conclude, representations play an essential role in mathematics.
Often, solving a problem is not about finding a brilliant idea, but the right way to look at the objects.
Matrices as graphs is one of the prime examples for that.
Often, solving a problem is not about finding a brilliant idea, but the right way to look at the objects.
Matrices as graphs is one of the prime examples for that.
• • •
Missing some Tweet in this thread? You can try to
force a refresh
