Eigenvalue range of $P+P^T$ (P is a transition matrix)

Question

$P$ is a transition matrix of dimension $N\times N$. I know $\lambda_1=1$ and $|\lambda_i|<1, 2\leq i \leq N$. I want to know the eigenvalue range of $P+P^T$. Because $P$ is not symmetric, so I don't know how to handle my problem. Please help me out:)

Answer 1

Proposition. Let $$E=\pmatrix{ 1&0&\cdots&0&0\\ 1&0&\cdots&0&0\\ \vdots&\vdots&&\vdots&\vdots\\ 1&0&\cdots&0&0}, \ F=\pmatrix{ 0&0&\cdots&0&1\\ 1&0&\cdots&0&0\\ \vdots&\vdots&&\vdots&\vdots\\ 1&0&\cdots&0&0} $$ Then \begin{align} \lambda_\max(P+P^T)&\le\lambda_\max(E+E^T)=1+\sqrt{n},\\ \lambda_\min(P+P^T)&\ge\lambda_\min(F+F^T)=-\sqrt{n+2}. \end{align}

---

Proof. For any row stochastic matrix $P$, the sum $P+P^T$ is real symmetric. Therefore $$ \lambda_\max(P+P^T)=\max_{\|x\|=1}x^T(P+P^T)x=2\max_{\|x\|=1}x^TPx. $$ Yet $P+P^T$ is also entrywise nonnegative. Therefore, it has a nonnegative Perron vector $v$. Normalise $v$ to a unit vector. By permuting the row and column indices if necessary, we may assume that the entries of $v$ are arranged in descending order. Therefore $Pv\le Ev$ and in turn $\lambda_\max(P+P^T)=2v^TPv \le 2v^TEv \le \lambda_\max(E+E^T)$.

That settles the question for the maximum possible eigenvalue. For the minimum possible eigenvalue, it's a longer story.

We have $\lambda_\min(P+P^T)=2\min_{\|x\|=1}x^TPx$. Clearly, the minimum possible eigenvalue over all feasible $P$s must be negative. Consider any feasible $P$ such that $\lambda_\min(P+P^T)$ has a negative eigenvalue. Let $v$ be a corresponding unit eigenvector. Without loss of generality, we may assume that $$ v_1\ge v_2\ge\cdots\ge v_k\ge 0\ge v_{k+1}\ge\cdots\ge v_n. $$ Since $P+P^T$ is entrywise nonnegative, $v$ must have at least one positive entry and at least one negative entry. In other words, we must have $v_1>0>v_n$. As $-v$ is also an eigenvector, we may also assume that $v_1\ge |v_n|$. Now, let $$ u^T=(v_1,-v_2,\ldots,-v_k,v_{k+1},\ldots,v_n). $$ Denote the $i$-th entry of $Pv$ by $(Pv)_i$. Then \begin{align} v^TPv &= \sum_{i\le k} v_i(Pv)_i + \sum_{i>k} v_i(Pv)_i\\ &\ge \sum_{i\le k} v_iv_n + \sum_{i>k} v_iv_1\\ &= v_1v_n + \sum_{i=2}^k v_iv_n + \sum_{i>k} v_iv_1\\ &\ge v_1v_n + \sum_{i=2}^k (-v_iv_1) + \sum_{i>k} v_iv_1\quad(\because v_1\ge|v_n|)\\ &= u_1u_n + \sum_{i=2}^k u_iu_1 + \sum_{i>k} u_iu_1\\ &= u_1u_n + \sum_{i>1} u_iu_1\\ &= u^TFu. \end{align} Therefore $\lambda_\min(P+P^T)=2v^TPv \ge 2u^TFu \ge \lambda_\min(F+F^T)$.