4 ms·
whew! I thought I was missing something obvious (I'm a graph/matrix nerd, can't you tell?)
by dekhn 4y ago
whew! I thought I was missing something obvious (I'm a graph/matrix nerd, can't you tell?)
- bee_rider 4y agoIt was a pretty nonsensical joke anyway. Something obvious that I missed which sort of spoils the joke is that if you take a binary tree, look at it as a directed graph, and then take the adjacency matrix of the graph, it is obviously not invertible. Do'h!
- dekhn 4y agoI don't think that's true- at least, I see literature saying that inversting the adjacency matrix of a graph is useful. Is there something about the property of the graph that makes it non-invertible?
- bee_rider 4y agoFor sure they are useful in general. In the case of a binary tree, though -- I guess it depends on how you think of the graph. If it is directed -- a parent only points down to it's children (so, no backwards links up the tree), the adjacency matrix is clearly rank deficient. The row (or column depending on how you want the adjacency matrix to be set up) for edges going in to node 1 is empty. If we think of the graph as undirected, it is still not invertible, but I don't know that there's anything immediately intuitive about it. With 7 nodes we'd have (numbered as in a breadth first traversal): . 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 1 0 0 1 1 0 0 3 1 0 0 0 0 1 1 4 0 1 0 0 0 0 0 5 0 1 0 0 0 0 0 6 0 0 1 0 0 0 0 7 0 0 1 0 0 0 0 Rows 4 and 5, as well as 6 and 7 are clearly degenerate (all the leaf nodes).