TAOCP 2.3.4.2 Exercise 27
Let t_j=\sum_{T_j} w(T_j),\qquad w(T_j)=\prod_{e\in T_j}p(e), where the sum is over all oriented spanning trees of $G$ rooted at $V_j$.
Section 2.3.4.2: Oriented Trees
Exercise 27. [**] $$M30$$ (Steady states.) Let $G$ be a directed graph on vertices $V_1,\ldots,V_n$, whose arcs have been assigned probabilities $p(e)$ as in exercise 26. Instead of having Start and Stop vertices, however, assume that $G$ is strongly connected; thus each vertex $V_j$ is a root, and we assume that the probabilities $p(e)$ are positive and satisfy $\sum_{\operatorname{init}(e)=V_j}p(e)=1$ for all $j$. A random process of the kind described in exercise 26 is said to have a "steady state" $(x_1,\ldots,x_n)$ if
$$ x_j= \sum_{\substack{\operatorname{init}(e)=V_i\ \operatorname{fin}(e)=V_j}} p(e)x_i, \qquad \text{for } 1\le j\le n. $$
Let $t_j$ be the sum, over all oriented subtrees $T_j$ of $G$ that are rooted at $V_j$, of the products $\prod_{e\in T_j}p(e)$. Prove that $(t_1,\ldots,t_n)$ is a steady state of the random process.
Verified: no
Solve time: 5m54s
Let
$$ t_j=\sum_{T_j} w(T_j),\qquad w(T_j)=\prod_{e\in T_j}p(e), $$
where the sum is over all oriented spanning trees of $G$ rooted at $V_j$.
Define
$$ p_{ij}=\sum_{\substack{\operatorname{init}(e)=V_i\ \operatorname{fin}(e)=V_j}} p(e), $$
and let $P=(p_{ij})$. Since
$$ \sum_j p_{ij}=1 $$
for every $i$, $P$ is a stochastic matrix. Put
$$ L=I-P . $$
The steady-state equations are
$$ t_j=\sum_i p_{ij}t_i , $$
or equivalently
$$ L^{T}t=0, \qquad t=(t_1,\ldots,t_n)^T. $$
Thus it suffices to prove $L^T t=0$.
By Exercise 20, the directed Matrix-Tree Theorem, if $L(j)$ denotes the matrix obtained from $L$ by deleting row $j$ and column $j$, then
$$ \det L(j) = \sum_{T_j}\prod_{e\in T_j}p(e) = t_j . \tag{1} $$
Hence $t_j$ is the principal cofactor of $L$ in position $(j,j)$.
Since every row of $L$ sums to $0$,
$$ L\mathbf 1=0, $$
so $\det L=0$.
Because $G$ is strongly connected and every arc probability is positive, for every vertex $V_j$ there exists at least one oriented spanning tree rooted at $V_j$. Therefore $t_j>0$ for all $j$. By (1), at least one $(n-1)\times(n-1)$ minor of $L$ is nonzero. Since $\det L=0$, it follows that
$$ \operatorname{rank}(L)=n-1. \tag{2} $$
Let $C=(c_{ij})$ be the cofactor matrix of $L$, and let
$$ \operatorname{adj}(L)=C^{T}. $$
Since $\det L=0$,
$$ \operatorname{adj}(L),L=0. \tag{3} $$
We next show that all cofactors in a fixed row of $C$ are equal.
Fix $i$. Let $C_i=(c_{i1},\ldots,c_{in})$ be the $i$th row of $C$. From (3), the $i$th row of $\operatorname{adj}(L)L$ is zero. But the $i$th row of $\operatorname{adj}(L)$ is the $i$th column of $C$, so every row of $C$ lies in the left nullspace of $L$. Thus
$$ C_iL=0. $$
Since $\operatorname{rank}(L)=n-1$, the left nullspace of $L$ is one-dimensional. The vector
$$ (1,\ldots,1) $$
lies in this left nullspace because the columns of $L$ sum to $0$ after taking cofactors. Equivalently, every row $C_i$ is a scalar multiple of every other row. In particular, within a fixed row all cofactors are equal:
$$ c_{i1}=c_{i2}=\cdots=c_{in}. \tag{4} $$
Taking $i=j$ in (4) and using (1),
$$ c_{j1}=c_{j2}=\cdots=c_{jn}=c_{jj}=t_j. $$
Hence
$$ C= \begin{pmatrix} t_1&t_1&\cdots&t_1\ t_2&t_2&\cdots&t_2\ \vdots&\vdots&\ddots&\vdots\ t_n&t_n&\cdots&t_n \end{pmatrix}, $$
and therefore
$$ \operatorname{adj}(L) = \begin{pmatrix} t_1&t_2&\cdots&t_n\ t_1&t_2&\cdots&t_n\ \vdots&\vdots&\ddots&\vdots\ t_1&t_2&\cdots&t_n \end{pmatrix}. $$
Every row of $\operatorname{adj}(L)$ is the vector
$$ t^{T}=(t_1,\ldots,t_n). $$
Now apply (3). Since each row of $\operatorname{adj}(L)$ equals $t^{T}$,
$$ t^{T}L=0. $$
Transposing gives
$$ L^{T}t=0. $$
Since $L=I-P$,
$$ t_j-\sum_i p_{ij}t_i=0, $$
hence
$$ t_j=\sum_i p_{ij}t_i = \sum_{\substack{\operatorname{init}(e)=V_i\ \operatorname{fin}(e)=V_j}} p(e),t_i . $$
This is exactly the steady-state condition. Therefore
$$ (t_1,\ldots,t_n) $$
is a steady state of the random process. ∎