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.
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?
Thanks :) Sadly, I am not familiar with the topic you mention.
My knowledge about the matrix-graph connection is coming from my studies in Markov chains and other stochastic processes, so it is limited to that area.
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 there, thanks! You are definitely correct in the v7 case :) I'll fix it by adding one more edge to the matrix. Regarding the transposition matrix, which text part are you referring to exactly? I am unable to find it right now.
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.
I am not sure which example you refer to, but in the large one in the section abouty strongly connectedness, v4 is in the second block. The blocks are determined by the strongly connected components.
Regarding v1: yes, you could have started with any point in that component; what matters is that the root component comes first. If it helps, you can draw a "meta-graph", whose points are the components of the example graph, and whose edges are connections between the components.
Hope that my answer helped. Let me know if you still have questions!
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.
Thanks, I see the issue! You are correct, there should be ones on the diagonal, except on the i-th and j-th row. Fixing it now!
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?
Hi! Thanks :)
An irreducible matrix is already in Frobenius normal form: it only has a single block.
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?
Thanks :) Sadly, I am not familiar with the topic you mention.
My knowledge about the matrix-graph connection is coming from my studies in Markov chains and other stochastic processes, so it is limited to that area.
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 there, thanks! You are definitely correct in the v7 case :) I'll fix it by adding one more edge to the matrix. Regarding the transposition matrix, which text part are you referring to exactly? I am unable to find it right now.
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.
Thanks! You are correct. What I should have said is that this relation induces a partial order.
The figures illustrating your article are superb... Did you use tikz to produce them?
Thanks! I have rendered the images with QuickLaTeX (https://quicklatex.com/) and drew the images in Inkscape (https://inkscape.org/).
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 there, thanks!
I am not sure which example you refer to, but in the large one in the section abouty strongly connectedness, v4 is in the second block. The blocks are determined by the strongly connected components.
Regarding v1: yes, you could have started with any point in that component; what matters is that the root component comes first. If it helps, you can draw a "meta-graph", whose points are the components of the example graph, and whose edges are connections between the components.
Hope that my answer helped. Let me know if you still have questions!
Sure, so the block containing nodes 4-5-6-7 and 8-9 are both “order 1”. How did you select which one should be “first”? Or are they equivalent?
You can switch the numbering, so the two-element block can be 4-5 and the four-element block can be 6-7-8-9.
The important part is that no edge should go to a block where the elements are earlier in the indexing.
Ok thank you!
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 .
Thanks! Yeah, Math3ma has really great posts, I also recommend them for everyone.