search

sangttruong / ginrummy

A data-driven approach for Gin Rummy hand evaluation
MIT License
8 stars 3 forks source link

Clarifications on adjacency matrix representations #3

Open ShutoAraki opened 3 years ago

ShutoAraki commented 3 years ago

One thing we need to really clarify on is how the elementary operations relate to adjacency matrix representations and if all the adjacency matrices representing the same graph have the same eigenvalues and eigenvectors.

ShutoAraki commented 3 years ago

https://rdrr.io/bioc/GraphAT/man/perms.html

Given an adjacency matrix, this function gives you another adjacency matrix (that is drawn from the permuted matrices) that represents the identical graph structure.

Given an adjacency matrix for a graph, permEdgesM2M will return an adjacency matrix after an Erdos-Renyi random permutation of the edges in the graph. perNodesM2M will return an adjacency matrix for a graph with identical structure, but with the node labels permuted.

ShutoAraki commented 3 years ago

I think it's making sense! The mystery of is just that they're similar matrices...? Still not sure how that's related to though...

Isomorphism and invariants Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given. G1 and G2 are isomorphic if and only if there exists a permutation matrix P such that In particular, and are similar and therefore have the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic.[9] Such linear operators are said to be isospectral.

https://en.wikipedia.org/wiki/Adjacency_matrix

ShutoAraki commented 3 years ago

I have an explanation for why similar matrices have the same eigenvalues

ShutoAraki commented 3 years ago

This is also a good question: https://math.stackexchange.com/questions/2741797/similar-adjacency-matrices-of-the-same-graph

Unanswered: How can we be sure that N! adjacency matrices have their corresponding permutation matrix P? (Sort of obvious when you think about actually permutation through all possible adj matrices though)

ShutoAraki commented 3 years ago

image from https://scholarworks.umt.edu/cgi/viewcontent.cgi?article=1166&context=tme

TODO: Digest the following sentence

Relabeling the vertices of the graph changes the adjacency matrix in the same way reordering the vectors of a basis of a n-dimensional vector space changes the matrix of a linear operator: the orignial matrix A and the new one B are similar, i.e. there exists an invertible square matrix P of order n such that B = P^-1AP

ShutoAraki commented 3 years ago

This is basically almost exactly what we did during the meeting lol https://www.youtube.com/watch?v=UCle3Smvh1s

ShutoAraki commented 3 years ago

More precise definition on adjacency matrix: https://math.stackexchange.com/questions/2910954/node-ordering-permutation-based-adjacency-matrix

ShutoAraki commented 3 years ago

TODO: Precisely define permutation matrix, graph isomorphism, and adjacency matrix

sangttruong commented 3 years ago

Permutations of elements in set as function: http://mathonline.wikidot.com/permutations-of-elements-in-a-set-as-functions

ShutoAraki commented 3 years ago

I think it's making sense! The mystery of ![](https://render.githubusercontent.com/render/math?math=E_{R}AE_{C} = A') is just that they're similar matrices...? Still not sure how that's related to ![](https://render.githubusercontent.com/render/math?math=E_{R}E_{C} A = A) though...

Isomorphism and invariants Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given. G1 and G2 are isomorphic if and only if there exists a permutation matrix P such that In particular, and are similar and therefore have the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic.[9] Such linear operators are said to be isospectral.

https://en.wikipedia.org/wiki/Adjacency_matrix

So the missing key is that left multiplication of an elementary permutation matrix swaps two rows whereas right multiplication swaps two columns because of how matrix multiplications are defined!

MasayukiNagai commented 3 years ago

Verify the following statements: 1) If adjacency matrices are similar, then the graphs are isomorphic. 2) If graphs are isomorphic, then the adjacency matrices are similar.