4 ms·
This is a big post. I'll point out what is especially interesting in terms of equivalences. A square matrix on the Booleans is indeed also equivalent to a dire
by Kednicma 6y ago
This is a big post. I'll point out what is especially interesting in terms of equivalences.
A square matrix on the Booleans is indeed also equivalent to a directed graph, as explained. It is also equivalent to a Chu space [0], specifically a sort of unitary Chu transformation.
We can specialize slightly. Let our square matrices be upper triangular; that is, let the lower triangle not including the diagonal be all 0/false. Then the corresponding graph is a DAG. (Apologies if this was in the article; I saw hints of it, but never the direct statement!) The corresponding Chu space has poset structure. These three facts are all related by fourth fact that the matrix's rows are labels for a topological sorting of the DAG, and the fifth fact that DAGs are equivalent to posets; we obtain a sixth fact that posets are equivalent to upper triangular Boolean matrices.
[0] http://chu.stanford.edu/ http://chu.stanford.edu/
- bmc7505 6y agoInteresting! I was not aware of the connection to Chu spaces, will have a look into that! Algebraic topology seems to have a endless trove of many interesting dualities. I did find the connection between topological ordering and boolean matrix multiplication to be really interesting. I was taught a queue-based algorithm as an undergrad, so learning about this was a pleasant surprise.
- adamnemecek 6y agoAll dualities are the same duality, namely adjoint functors. Wrote a brain dump on it https://github.com/adamnemecek/adjoint https://github.com/adamnemecek/adjoint
- bennofs 6y agoI was about to comment that these chu spaces look vaguely like galois connections. Turns out galois connections are just a special case of adjoint functors as well, so thanks for making that connection!
- brzozowski 6y agoInteresting, thanks for the pointer Adam!