3 ms·
This seems related to the way graphs are often implement in code - https://en.wikipedia.org/wiki/Adjacency_matrix https://en.wikipedia.org/wiki/Adjacency_matrix
by ajuc 8y ago
This seems related to the way graphs are often implement in code - https://en.wikipedia.org/wiki/Adjacency_matrix https://en.wikipedia.org/wiki/Adjacency_matrix
Just in that case you can start with any graph, not necessarily bipartite, so you don't divide vertices into 2 sets X and Y, just use the same set of all vertices V twice, so the matrix is always square:
V * V -> R
I wonder if the properties from this article still hold on adjacency matrices. Would be very useful.
- edflsafoiewq 8y agoYes, it's really the same graph. There really no difference between drawing two copies of V with arrows going from one to the other, and drawing one copy of V with arrows just staying in that copy. Either way, if you trace the arrows from a given vertex you will end up at the same spots. So for example the interpretation of matrix multiplication as path composition given here explains why the nth power of the adjacency matrix gives the number of length-n walks. (I think the precise relation is that if A the adjacency matrix for G, then if you draw the graph from this article for the matrix A, the adjacency matrix of that graph will be the block matrix 0 A A 0 That's assuming the edges in the article are regarded as undirected; if they are directed, just replace one of the As with 0.)
- ajuc 8y agoThanks. It's crazy to me that I've had graph theory on university, and many graph algorithms, and I don't remember ever hearing that multiplicating adjacency matrices have this properties. Maybe I just forgot about it. It would make some algorithms much easier :)
- edflsafoiewq 8y agoHeh. No one noticed but that should have been 0 A^T A 0 In the matrix-as-arrows-from-dots-in-Y-to-dots-in-X picture, the transpose means "turn all the arrows around". This also explains the connection between the transpose and the categorical dual.