I have a physics/computer science background. I'm writing up some research, and I keep hesitating and second-guessing myself when it comes to the formal definitions. I would like to settle my mind and get all of this defined strictly; I have found some resources that discuss related concepts, but they often seem to be loosely defined (often using sentences rather than logical steps), and I want to be consistent.

Consider a graph $G(E,V)$, with adjacency matrix $A(G)$.

  • One way of describing $A$ is $A(G) \in \mathcal{C}^{|V|\times|V|}$
  • Another is $A(G) : \mathcal{C}^{|V|} \rightarrow \mathcal{C}^{|V|}$.

Further, I now wish to define operations $s$ on such a matrix, such that the space remains unchanged:

  • One way of describing $s$ is $s: \mathcal{C}^{|V|\times|V|} \rightarrow \mathcal{C}^{|V|\times|V|}$
  • Another way is $s : (\mathcal{C}^{|V|} \rightarrow \mathcal{C}^{|V|}) \rightarrow (\mathcal{C}^{|V|} \rightarrow \mathcal{C}^{|V|})$

And, finally, I would like to map $s(A(G))$ back to a graph $G'(V,E')$ with the same vertices $V$, such that $A(G') = s(A(G))$. As the space which $A(G)$ acts on is defined through the vertices $V$, it would make sense to define a function $\tilde{s}$ on graphs such that $s(A(G)) = A(\tilde{s}(G))$. For the functions $s$ that I'm looking at, I can describe algorithms that provide $\tilde{s}$.

My questions are as follows:

  1. Am I overcomplicating things? Is there a simpler way of describing this? Which of the the physics/computer science notations are valid in this context?
  2. Is it valid to say that $V$ forms the basis of $A(G)$?
  3. Given that the basis of $A(G)$ is well defined, is it correct to say that the operations $s$ have counterparts $\tilde{s}$ that act directly on the graph?

I would say this is overcomplicated. I would say that $A(G) \in M_{n\times n}(\mathbb{R})$ (or $\mathbb{Q}$ or $\mathbb{C}$, depending on what I need to do with eigenvalues), where $n = |V|$. There are times when you would want to consider the adjacency matrix as a map from $\mathbb{R}^{V} \to \mathbb{R}^{V}$, but I think these cases are somewhat rare (and usually I would define a linear map that is not explicitly given by a matrix; I would say $\alpha: \mathbb{R}^{V} \to \mathbb{R}^{V}$ is defined by multiplication by $A$).

Since a simple graph is completely determined by its adjacency matrix, I would just define the operation $s$ in whatever setting it is most intuitive, and say this corresponds to modifying the other setting in ____ fashion, and we call this operation $\hat{s}$ (or with a tilde or whatever symbol). Note that if you say "$s$ is an operation on D" then the implication is that $s: D \to D$.

I can't answer about physics/comp sci notations.

You would not say that V forms the basis for $A(G)$; $A(G)$ is just a matrix, so it does not have a basis.

  • $\begingroup$ Thank you for your answer. In my setting, the matrix is being used as a map in some situations, but as it's still well defined in the matrix setting I will be okay. I was not aware that one could describe a graph fully by the adjacency matrix - does that also count if there is a labelling on the graph (something I neglected to mention)? I figured that this would require further information - and, as eigenvectors (in my case) have specific meaning with regards to the vertices. Is there a notational way of saying "$sM$ corresponds with $\tilde{s}G$"? Otherwise, you have bought my mind to ease! $\endgroup$ – JArkinstall Dec 8 '15 at 19:10
  • $\begingroup$ Yes, actually the adjacency matrix explicitly gives a labeling of the graph (with the $i$th row/column corresponding to the vertex numbered "$i$"). I don't know that there is a standard notational device for this, so define something in your paper that is clear, simple and intuitive and you should be good. $\endgroup$ – Morgan Rodgers Dec 8 '15 at 21:48
  • $\begingroup$ Brilliant, that's spot on. Thanks! $\endgroup$ – JArkinstall Dec 8 '15 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.