Every stochastic $n\times n$ matrix corresponds to a Markov chain for which it is the one-step transition matrix. However, not every stochastic matrix $n\times n$ is the two-step transition matrix of a Markov Chain. In particular, show that a $2\times 2$ stochastic matrix is the two-step transition matrix of a Markov Chain if and only if the sum of its principal diagonal elements is greater than or equal to 1.
I'm not so sure about what they mean two-step transition matrix, buf if $$P=\begin{bmatrix}P_{00}&P_{01}\\P_{10}&P_{11}\end{bmatrix}$$ is a one-step transition matrix, I think that $$P^{(2)}=P^2=\begin{bmatrix}P_{00}&P_{01}\\P_{10}&P_{11}\end{bmatrix}*\begin{bmatrix}P_{00}&P_{01}\\P_{10}&P_{11}\end{bmatrix}$$ is a two-step transition matrix.
I know by definition that $\forall i,j\space P_{ij}\geq 0$ and $\sum_{j=0}^1 P_{ij}=1$, and I need to proof that
$(1)$if $P^{(2)}$ is a two-step matrix then $\sum_{j=0}^1 P_{ii}\geq 1$
$(2)$ if $\sum_{j=0}^1 P_{ii}\geq 1$ then $P^{(2)}$ is a two-step matrix
I tried to prove $(1)$ and $(2)$ using contradiction, but I did not get anywhere.
Your understanding of the question is correct.
For part 1, look at $P^{(2)}_{00}+P^{(2)}_{11}=P_{00}^2+2P_{01} P_{10}+P_{11}^2$. Replace $P_{01}=(1-P_{00})$ and $P_{10}=(1-P_{11})$, so that there are only two variables involved. Then you have $P_{00}^2+2(1-P_{00})(1-P_{11})+P_{11}^2$. Expand, simplify, and complete the square.
For part 2, a linear algebraic approach would be to calculate the matrix square root under that assumption and then check that the result is a stochastic matrix. There is probably a convenient probabilistic proof, though.
(Note that I am assuming the convention $P_{ij}$ is the probability to go from $i$ to $j$, so that the row sums are $1$ and the column sums may or may not be $1$. Adjust accordingly if you have the opposite convention.)