The single most undervalued fact of linear algebra: matrices are graphs, and graphs are matrices
I was thinking of this passage: "we define the so-called transposition matrices by switching the i-th and j-th rows of the identity matrix". If it's the identity matrix, then it has 1s on the diagonal everywhere but on lines i and j I suppose. It caught my eye because otherwise I don't see how P^2 = I could work out.
Fascinating post, many thanks!
If I understood correctly, it doesn't matter whether the nonnegative matrix A is irreducible or not, it always has a Frobenius normal form. However, is irreducibility (or reducibility) of A somehow reflected in the normal form?
wonderful content, I would appreciate more on this series matrices and graphs. I am building an application to visualize graph theory, and I was researching how to draw planar graphs, do you have something similar using matrices?
Hi, new subscriber her, thanks for this enlightening explanation!
I have 2 naive comments. They might be mistakes, or just things I missed. First, it seems that the image of a transposition matrix doesn’t match the text, as it has 0s on it’s diagonal instead of 1s. I’m guessing these 1s should be there, unless it’s a notation thing I’m missing. Second, when building the subsets of the graph, I think the leftmost subset doesn’t match the definition of « mutually reachable », since the node that ends up labeled v7 is not reachable from the rest of the subset.
I look forward to reading what you come up with next!
Hi Tivadar, great post! I really enjoyed reading it. When you "skeletonize" the graph into its strongly connected components, I'm skeptical of your claim that the relation is a partial order (referring to the image labeled "Numbering of the classes"). Such relations must be transitive, and the relation created by those edges is not. For example, 0->2 and 2->3, but there's no edge between 0 and 3. I could be misunderstanding what the exact relation is here though.
The figures illustrating your article are superb... Did you use tikz to produce them?
New sub here, love the content, subbed immediately.
Basic question: I don’t understand how you chose which of the two blocks contained v4, because they were both class 1?
By the same token, how do you choose v1? Does it matter which node within the block you start with?
Hi Tivadar! Just read this post and thanks for all your writings (I have your early access math for ml book). FYI some other nice blog posts on the topic IMO are https://www.math3ma.com/blog/matrices-as-tensor-network-diagrams and https://www.math3ma.com/blog/matrices-probability-graphs .