Equalizing Geometric means of Graph Cycles

Question

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are equal? Also, I would like all outgoing edges to sum to 1.

For example, $p=\varphi^{-2}$ is a solution for the graph shown below, where $\varphi$ is the Golden ratio.

The geometric means for the two cycles are $(p\cdot1)^{1/2}=\varphi^{-1}$ and $(1-p)=(1-\varphi^{-2})=\varphi^{-1}$. The appearance of the Golden ratio here can be explained by observing the relation to sequences with no consecutive 1's (the number of such sequences of length $n$ is approximately $\varphi^n$).

Even though the number of constraints is much larger than the number of variables, I have not been able to construct a counterexample and I also don't know of a simple/direct proof of existence (I am aware of a purported indirect proof that exploits the ergodicity of the Markov chain - I would like to generalize this). I came across this question in my study of Markov chains. I have tried many numerical examples, and such a solution always exists (and is unique in my experience).

Any ideas, hints or references would be greatly appreciated!

Question is also on math.stackexchange (with some comments, but no answers).

Answer 1

I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple.

Let $V$ denote the vertex set of the underlying graph and let $A$ be the adjacency matrix, that is $A_{v,w} = 1$ if $v \to w$ and otherwise $A_{v,w} = 0$. This matrix is non-negative and irreducible, because the graph was strongly connected. Hence there is a positive eigenvalue $\lambda$ together with a right-eigenvector $c$ all of whose entries are positive. Moreover, for every $v \in V$ we have $(Ac)_v = \lambda c_v$, that is: $$ \sum_{w \colon v \to w} c_w = \lambda c_v. $$ So in particular (as all entries are positive) we have that for every directed edge $v \to w$, the value $p(v \to w) := \frac{c_w}{\lambda c_v}$ is well-defined and lies in the interval $(0, 1]$.

With this definition, we have for every vertex $v \in V$ $$ \sum_{w \colon v\to w} p(v \to w) = \frac{1}{\lambda c_v}(Ac)_v = 1. $$ Along every directed cycle, all the terms $\frac{c_v}{c_w}$ cancel out, and the accumulating power of $\lambda^{-1}$ is taken care of by definition of the geometric mean; hence every cycle has geometric mean $\lambda^{-1}$.