Given an undirected graph, can we always find a way to assign weights to every edge so that the adjacent matrix is double stochastic matrix?
(edit: We allow the matrix has positive element on (i,i), so strictly speaking, it is not an adjacent matrix)
The background is about distributed optimization. We can see each node as a computer, and they want to exchange information(like gradients or parameters) via edges in the connected graph to solve an optimization problem, for example, a machine learning problem. So, there is a weight matrix W, whose (i,j) element is the weight of information sent from node i to node j. Because node i can use its own information, so diagonal elements of W should be positive. The question is can we always find a doubly stochastic matrix W.
Best Answer
The answer is no. For example, consider the path of length $3$, which has adjacency matrix $$ A = \pmatrix{0&1&0\\ 1&0&1\\ 0&1&0}. $$ In order for the first row to have a sum of $1$, the edge $(1,2)$ must have weight $1$. However, in order for the second row to have a sum of $1$ (and for the edge $(2,3)$ to have a non-zero weight), the edge $(1,2)$ must have weight less than $1$.
That said, if we can give distinct weights to the edge in each direction, then we can at least produce a row-stochastic matrix in the form of the transition matrix corresponding to a simple random walk over the graph. In particular, this means that the (directed) edge $i \to j$ is given the weight $\frac 1{i}$. For the path of length $3$, this gives us the matrix $$ P = \pmatrix{0&1&0\\1/2&0&1/2\\0&1&0}. $$
For the question as I now understand it, the answer is yes. It suffices to assign weights as follows:
Let $d$ denote the degree of the graph (i.e. the maximal vertex degree). Let $d_i$ denote the degree of vertex $i$. It suffices to assign the weight $\frac 1{d}$ to all off-diagonal entries (i.e. to all non-loop edges) and weight $\frac{d-d_i}{d}$ to the $i$th diagonal entry (i.e. the loop on the $i$th vertex).
That is, let $D$ denote the degree matrix, the diagonal matrix whose $i$th diagonal entry is the degree of the $i$th vertex. Then the matrix $ \frac 1d [dI + A - D] $ is doubly stochastic.
We could also write this as $\frac 1d[dI - L]$, where $L$ denotes the graph Laplacian.