[Math] Product of doubly stochastic matrix

linear algebramatrices

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).

Please help me for the part c) or complete my proof.
Thank you so much

Quote of today:

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

Jacques-Louis Lions

Best Answer

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$.

Related Question