Suppose that I generate a k-regular graph like the following:
game <- sample_k_regular(k, r)
game <- as.matrix(as_adj(game))
Then, based on this adjacency matrix, suppose I replace the $1$'s with a correlation parameter $\rho$ and replace all the $0$'s in the diagonal with $1$. Then, this is a covariance matrix for something that is like a multivariate normal. However, this way of creating a matrix results in a NON-positive definite matrix. Is there a way to create a covariance matrix structure based on an adjacency matrix based on putting a correlation parameter $\rho$ where there are ties and $1$'s in the diagonal for a common variance? In other words, is there a way to create covariance matrices without running into the positive definiteness problem? Thanks.
Best Answer
Yes, for example if you choose $\rho$ small enough to ensure that your matrix is strictly diagonally dominant, then it is guaranteed to be positive definite. In this case "small enough" means $|\rho|<1/r$, where $r$ is the valency of the regular graph.
But possibly you do not want to choose $\rho$ so small. A useful thing to remember here is that a symmetric matrix is positive definite if and only if its eigenvalues are all positive. And since you are constructing your matrix as $$ M = I + \rho A$$ where $A$ is the adjacency matrix of the graph, it follows that the eigenvalues of $M$ are of the form $1+\rho\lambda$ as $\lambda$ ranges over the eigenvalues of $A$. So if you have a particular $\rho>0$ in mind, then the graphs that will work are precisely those for which all eigenvalues (of the adjacency matrix) satisfy the bound $\lambda > -1/\rho$. In other words, you need graphs whose negative eigenvalues aren't too large in magnitude. Note that for a regular graph with valency $r$, all its eigenvalues satisfy $|\lambda| \leq r$, which leads to the same sufficient condition $|\rho| < 1/r$ described above.
There is quite a bit of information available about graphs whose most negative eigenvalue isn't too large in magnitude; this falls within the subject of spectral graph theory. In particular, the problem of characterizing graphs whose eigenvalues satisfy $\lambda \geq -2$ is treated in the book Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2. It contains the following result, showing that with fairly trivial exceptions the bound $\lambda\geq -2$ is the best that we can hope for a regular graph to satisfy:
There are methods of constructing broad families of regular graphs which attain this bound, i.e. whose least eigenvalue is -2. The most basic one is the construction of a line graph. If you start with any graph $G$, you can construct a new graph $L(G)$, whose vertices correspond to the edges of $G$ and whose edges correspond to edge-incidences of $G$. This graph $L(G)$ is called the line graph of $G$, and it is guaranteed that its eigenvalues satisfy $\lambda \geq -2$, no matter which graph $G$ you start with. Moreover, if you start with a regular graph $G$ with valency $r$, then $L(G)$ will also be regular, with valency $2(r-1)$. This gives you a way to construct regular graphs for which you can take $\rho$ to be any value satisfying $|\rho|<1/2$ and end up with M being positive definite. In light of the result cited above, this is the best that is possible, unless you want to go with a complete graph (which allows $\rho$ to be arbitrarily close to 1) or an odd cycle (which allows $\rho$ to be a little larger than $1/2$, but by an amount which approaches zero as the size of the cycle increases), or a disjoint union of complete graphs and odd cycles.
If it is unsatisfactory to restrict to regular graphs with even valency, it's worth noting that you don't have to start with a regular graph $G$ in order for $L(G)$ to be regular. For instance, you could instead start with $G$ being a semiregular bipartite graph, where one of the two valencies is even and the other is odd, and this would result in $L(G)$ being regular with odd valency.