# Product of doubly stochastic matrix

I have a question:

Definitions A matrix $A$ is doubly stochastic if:

a) $0\leq a_{ij}\leq1.$

b) $\sum_{j=1}^{n}a_{ij}=1\;\forall i=1,2,\ldots, n.$

c) $\sum_{i=1}^{n}a_{ij}=1\;\forall j=1,2,\ldots, n.$

# Prove that the product of two doubly stochastic matrices is doubly stochastic.

Part a)

$$0\leq b_{kj}\leq 1,\forall k,j\in\{1,\ldots,n\}$$ $$\implies0\leq a_{ik}\cdot b_{kj}\leq a_{ik},\forall i\in\{1,\ldots,n\}$$ $$0\leq \sum_{k=1}^{n} a_{ik}b_{kj}\leq\sum_{k=1}^{n}a_{ik}$$ $$\implies0\leq c_{ij}\leq1.$$

Part b) I use this property: $$\sum_{p=1}^{m}(\sum_{k=1}^{n}a_{ik}\cdot b_{kp})=\sum_{k=1}^{n}(\sum_{p=1}^{m}a_{ik}\cdot b_{kp})$$ $$\sum_{k=1}^{n} c_{ik}=\sum_{k=1}^{n}(\sum_{p=1}^{n}a_{ip}b_{pk})\mbox{, definition}$$ $$\implies \sum_{p=1}^{n}(\sum_{k=1}^{n}a_{ip}b_{pk}).$$ $$\implies\sum_{p=1}^{n} a_{ip}(\sum_{k=1}^{n}b_{pk}).$$ But $\sum_{k=1}^{n}b_{pk}$ is the sum of elements in one row of matrix $B$ and it is equal to 1 (doubly stochastic).

$$\implies\sum_{p=1}^{n}a_{ip}\cdot1=\sum_{p=1}^{n}a_{ip}$$ And $\sum_{p=1}^{n}a_{ip}$ eis the sum of elements in one row of matrix $A$ and it is equal to 1 (doubly stochastic).

Quote of today:

"Firstly, it is connected with technology. In order to do numerical analysis, you essentially need a machine."

Jacques-Louis Lions

• Could you just take transposes? The transpose of a doubly stochastic matrix is also doubly stochastic. – πr8 Apr 6 '17 at 23:27

Let $A, B$ be doubly stochastic matrices. We define $C = A.B = [c_{ij}]$ where $c_{ij} = \sum _{k=1}^{n} a_{ik}b_{kj}$, $\forall i,j = 1,2, \cdot \cdot \cdot ,n$
Calculating for all $j = 1,2, \cdot \cdot \cdot , n :$
$\sum_{i=1}^{n} c_{ij} = \sum _{i=1}^{n}(\sum_{k=1}^{n} a_{ik}b_{kj}) = \sum _{k=1}^{n}(\sum_{i=1}^{n} a_{ik}b_{kj}) = \sum _{k=1}^{n}(\sum_{i=1}^{n} b_{kj}a_{ik}) = \sum _{k=1}^{n}(b_{kj}(\sum_{i=1}^{n} a_{ik})) = \sum _{k=1}^{n}(b_{kj} .1) = \sum _{k=1}^{n}(b_{kj}) = 1.$
Note: $\sum _{i=1}^{n}(a_{ik}) = 1$ because $A$ is a doubly stochastic matrix and $\sum _{k=1}^{n}(b_{kj}) = 1$ because $B$ is a doubly stochastic matrix.
In part a) of your demonstration missing specify : $\forall i, j, k \in \lbrace 1,2,...,n \rbrace$.
• Thank you! I'll study your proof. I'll specify $\forall i,j,k \in \{1,2,\ldots,n\}$ – Oromion Apr 7 '17 at 4:48