Characterization of two-step 2x2 stochastic matrices Show that:

A 2 x 2 stochastic matrix is two-step transition matrix of a Markov chain if and only if the sum of its principal diagonal terms is greater than or equal to $1$.

 A: Encode the Markov matrix $\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$ by the couple $(a,b)$ with $a$ and $b$ between $0$ and $1$. The square of this matrix is encoded by the couple
$$
(a(2-a-b),b(2-a-b)),
$$ 
hence the question is to determine for which $a$ and $b$ between $0$ and $1$, there exists $x$ and $y$ between $0$ and $1$ such that
$$
a=x(2-x-y),\qquad b=y(2-x-y).
$$
If $x$ and $y$ exist, their sum $s$ solves $s(2-s)=a+b$ hence $(s-1)^2=1-a-b$, in particular 
$$
a+b\le1.
$$ 
Assume this condition holds. Then $s=1\pm\sqrt{1-a-b}$, hence 
$$
x=a/(2-s)=a/(1\mp\sqrt{1-a-b}),
$$
and
$$y=b/(2-s)=b/(1\mp\sqrt{1-a-b}).
$$
Since $1+\sqrt{1-a-b}$ is between $1$ and $2$, at least the choice $+$ in $\mp$ yields solutions $x$ and $y$ between $0$ and $1$.
Finally the Markov matrix $\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$ is the square of a Markov matrix if and only if 
$$
a+b\le1.
$$
A: Updated:  I've revived my answer with an alternative solution. Despite Didier's excellent direct solution to the problem, I think there 
may be some  benefit for students to also see the spectral point of view. 
Begin with a two by two Markov matrix $P=\pmatrix{1-a&a\cr b&1-b}$
for any $0\leq a,b\leq 1$. 
Every Markov matrix has eigenvalue 1 (with the eigenvector of all ones). 
The trace of our matrix $2-(a+b)$ is the sum of the eigenvalues so the 
other eigenvalue must be $\lambda:=1-(a+b)$. This eigenvalue satisfies $-1\leq \lambda \leq 1$.
Our problem is to show that $P\ $ has a Markov square root if and only if $\lambda\geq 0$. 
Sufficiency
The other eigenvalue of $P^2$ is $\lambda^2\geq 0$. 
Necessity
If $a+b=0$ then $P\ $ is the identity matrix and the problem is trivial.
If $a+b\neq 0$, then we can diagonalize the matrix as 
$$P= \pmatrix{1&-a\cr 1&b} \pmatrix{1&0\cr 0&\lambda} \pmatrix{{b\over a+b}&{a\over  a+b}\cr {-1\over  a+b}&{1\over  a+b}}$$
so that
\begin{eqnarray*}
\sqrt{P} &=& \pmatrix{1&-a\cr 1&b} \pmatrix{1&0\cr 0&\sqrt{\lambda}} 
             \pmatrix{{b\over a+b}&{a\over  a+b}\cr {-1\over  a+b}&{1\over  a+b}}\cr
         &=& \pmatrix{\displaystyle{b+a\sqrt{\lambda} \over a+b}&\displaystyle{a(1-\sqrt{\lambda})\over  a+b}\cr 
                    \displaystyle  {b(1-\sqrt{\lambda} )\over  a+b}&\displaystyle{a+b \sqrt{\lambda}\over  a+b}}.
\end{eqnarray*}  
In fact $P\ $ has two square roots of this type depending on which square root of $\lambda$ we take. 
If $0\leq \lambda\leq 1$, then one of its square roots 
satisfies  $0\leq \sqrt{\lambda}\leq 1$  and this choice gives a Markov matrix $\sqrt{P}$
by the above formula.  The other square root of $P\ $ might also be Markov, or it might have some negative values. 
Note that the diagonalization argument immediately shows the more general result that if $\lambda\geq 0$, then $P\ $ is an $n$-step Markov transition matrix for any $n\geq 1$. 
Granted, the two state Markov chain is especially simple as the transition  matrix is always diagonalizable. This will fail, in general, even for three state chains. 
Nevertheless, 
the analysis of a Markov chain via the eigenvalues of its transition matrix is a powerful and important tool. 
I think every student should be exposed to this idea.
