1
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Thank you! I'll study your proof. I'll specify $\forall i,j,k \in \{1,2,\ldots,n\}$ $\endgroup$ – Oromion Apr 7 '17 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.