# 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?

• Anyone knows this trickery? Or a neat solution which is not brute force? – merkenN Jan 12 '14 at 20:42

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)