Eigenvalue range of $P+P^T$ (P is a transition matrix) $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:)
 A: 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)$.
