Show that $P^n$ is double stochastic.

Question

A transition matrix $P$ is said to be doubly stochastic if the sum over each column equals one, that is $\sum_i P_{ij}=1\space\forall i$.

If $P$ is doubly stochastic, show that $P^n$ is doubly stochastic $\forall n\in\Bbb{N}$

I was thinking to prove this with induction but I got stuck in the base case showing that every column's sum equals one.

Answer 1

Base Case: $n=2$

I want to show that the sum of every column of $P^2$ equals $1$

let $J$ be the number of rows of P

Expanding the elements of the product of $P^2$

$\sum_{j\in J}P^2=\sum_{j\in J}(\sum_{s\in J}P_{js}P_{sk})=\sum_{s\in J}P_{sk}\sum_{j\in J}P_{js}$ $\ \ \ \ ,(k\in J$)

Here we use the fact that P is double stochastic, therefore:

$\sum_{s\in J}P_{sk}\sum_{j\in J}P_{js}=\sum_{s\in J}P_{sk}=1$

We suppose it is true for m = n:

$\sum_{j\in J}P^{m+1}=\sum_{j\in J}(\sum_{s\in J}P_{js}P_{sk}^m)=\sum_{s\in J}P_{sk}^m\sum_{j\in J}P_{js}$ $\ \ \ \ ,(k\in J$)

Here we use our induction hypothesis:

$\sum_{s\in J}P_{sk}^m\sum_{j\in J}P_{js}=\sum_{s\in J}P_{sk}^m=1$

$q.e.d.$