Literature on Non-Scalar weights on edges of Graph?

Question

I need to survey, if there exists, the literature that uses non-scalar weights on Graphs.

In my case, I would like to have weight matrices $\mathbf{W}_{ij}$ instead of scalars $w_{ij}$ on the edges of my graph.

I know that the usual graph and hence their Laplacian matrices are co-ordinate independent.

But in my case, the Laplacian depends on the co-ordinates. Is there any literature available regarding this kind of situations?

Answer 1

A quiver is a directed multigraph. A representation of a quiver assigns a vector space to each vertex and a linear map to each directed edge. For each edge, once a basis is chosen for the vertices at its ends, the linear map can be expressed as a matrix. Maybe there's literature on the Laplacian of a representation of a quiver, but I didn't find any through simple searching.

For unweighted directed multigraphs, the Laplacian matrix is defined. To generalize to your linear maps setting, you could construct a discrete Laplacian in a space which is the direct sum of your vertex spaces with each of your $A_{ij}$, elements of your adjacency matrix, being your linear maps.

In detail:

• Let $\{v_i\}_{i =1}^{N} = V$ be your set of vertices. You have assigned to $v_i$ vector space $U_i$ of dimension $d(i)$. So duplicate $v_i$ a total of $d(i)$ times, producing the new vertices $v_{i,1}, \dots, v_{i,d(i)}$
• You have assigned to each directed edge, $(v_i, v_j)$, a map $M_{ij}: U_i \rightarrow U_j$. (I suppose if you have undirected edges, you should ensure that your map is invertible, split the edge into two directed edges, use the forward map in one direction and the inverse map in the other.) Replace that map with scalar weighted edges $(v_{i,m}, v_{j,n})$ weighted by $\left(M_{ij}\right)_{m,n}$. That is, the $(m,n)^\text{th}$ entry of $M_{ij}$ is the weight of the edge from the $m^\text{th}$ copy of $v_i$ to the $n^\text{th}$ copy of $v_j$.
• Delete any edge with a weight of zero. (Or not. It will only appear as an additional summand of zero in the following.)

This new directed multigraph is the one you want to work with. It models the components of vectors, one each in the vector spaces on the vertices of the original graph, via the duplicated vertices. It models the maps by splitting them into what they do to each (domain basis vector, codomain basis vector) pair. Having reduced this to a scalar weighted directed multigraph, we can renumber the vertices to simplify notation. Extract the degree matrix ($D_{k,k}$ is the sum of the outgoing weights of the $k^\text{th}$ vertex and zero everywhere else) and adjacency matrix ($A_{p,q}$ is the total weight of edges from vertex $p$ to vertex $q$). Then your Laplacian is $D - A$. The eigenvalues of this matrix will tell you about the graph made by duplicating vertices. You should be able to pull back that information to the representation of the quiver with which you started.

One might be concerned that change of basis could alter the Laplacian. As a matrix, this is certainly the case. However, its eigenvalues will be unchanged as long as the change of basis matrix is unitary. (That is, the determinant of the matrix of one set of basis vectors in terms of the other is $1$.) This will be equivalent to multiplying the degree and adjacency matrices by an identity matrix (for all the unchanged bases) with the block corresponding to the altered basis instead multiplied by the change of basis matrix. (That we can think of this is as a block matrix is the content of "direct sum" a few paragraphs back.) This changes none of the eigenvalues. (And although it changes the coordinates of the eigenvectors, it does not change the eigenvectors.)