20 Comments

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.

Expand full comment

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!

Expand full comment

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?

Expand full comment

Hi! Thanks :)

An irreducible matrix is already in Frobenius normal form: it only has a single block.

Expand full comment

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?

Expand full comment

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.

Expand full comment

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!

Expand full comment

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.

Expand full comment

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.

Expand full comment

Thanks! You are correct. What I should have said is that this relation induces a partial order.

Expand full comment

I see math, I click like.

Expand full comment

The figures illustrating your article are superb... Did you use tikz to produce them?

Expand full comment

Thanks! I have rendered the images with QuickLaTeX (https://quicklatex.com/) and drew the images in Inkscape (https://inkscape.org/).

Expand full comment

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?

Expand full comment

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!

Expand full comment

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?

Expand full comment

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.

Expand full comment

Ok thank you!

Expand full comment

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 .

Expand full comment

Thanks! Yeah, Math3ma has really great posts, I also recommend them for everyone.

Expand full comment