Terminology request: operations on graph adjacency matrices

Question

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?

Answer 1

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.