<s>[INST] probability matrix with trace $1$ is square of probability matrix Consider as probability matrix a matrix $M \in [0,1]^{n \times n}$ while every row sums up to $1$.
Statement: Consider a $2\times 2$ probability matrix $M' \in [0,1]^{2 \times 2}$. Show, that the following holds:
$$\exists \text{ probability matrix } M : M^2 = M' \iff \operatorname{Trace}(M') \geq 1$$
I showed $\implies$, i.e. when $M'$ is square of another probability matrix, then one can show, that the trace must be greater or equal to one.
But I got stuck at the $\impliedby$ part. Any tipps?
So far considering user68061's answer: Let $M' = \begin{pmatrix} x & (1-x) \\ (1-y) & y \end{pmatrix}$ and $M = \begin{pmatrix} a & (1-a) \\ (1-b) & b \end{pmatrix}$, then $M^2 = \begin{pmatrix} a^2+(1-a)(1-b) & a(1-a)+b(1-a) \\ a(1-b)+b(1-b) & b^2+(1-a)(1-b)\end{pmatrix}$.
Hence we need to solve
$x = a^2+(1-a)(1-b),\ y=b^2+(1-a)(1-b)$ where $x+y \geq 1$.
But somehow I think I am missing the trickery in calculation to get this solution..can you help?
 [/INST] I don't know the nice way to do it, but you can brute force it.
Consider probability matrix $ \left( \begin{array}{cc}
a & 1-a \\
b & 1-b  \\ \end{array} \right)  $ is a probability matrix $  \left( \begin{array}{cc}
a^2+b(1-a) & a(1-a)+(1-a)(1-b) \\
ab+b(1-b) & b(1-a)+(1-b)^2  \\ \end{array} \right) $. So you need to show, that the equation $x=a^2 + b(1-a); y=b(1-a)+(1-b)^2$ has a solution in $a,b$ for $x+y \geq 1$. This can be solved directly (look at $x+y$, find $a-b$ then just substitute to the first equation)
</s>