Characterization of two-step 2x2 stochastic matrices

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. $$

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.