$A$ is a doubly stochastic matrix, how about $A^TA$

632 Views Asked by At

I am reading a paper with assumption that $A \in R^{n\times n}$ is a doubly stochastic matrix. However, the paper says $A^TA$ is symmetric and stochastic.

  1. Since $A^TA$ is symmetric, if $A^TA$ is stochastic, it must be doubly stochastic.

  2. The $(j,j)$ entry of $A^TA$ is exactly $a_{ij}^Ta_{ij}$ with $i=1,\ldots,n$.

Then is there any other condition I can use to prove this claim is true or false?

3

There are 3 best solutions below

0
On BEST ANSWER

If $A$ is doubly stochastic, then $A^T A$ is doubly stochastic too. Proof is strightforward. Let $B=A^T A$. At first, $$ b_{ij} = \sum_{k=1}^n (a^T)_{ik} a_{kj} = \sum_{k=1}^n a_{ki} a_{kj}. $$ Check property of doubly stochastic matrix: $$ \sum_{j=1}^n b_{ij} = \sum_{j=1}^n \sum_{k=1}^n a_{ki} a_{kj}= \sum_{k=1}^n \sum_{j=1}^n a_{ki} a_{kj} = \sum_{j=1}^n a_{ki}\sum_{k=1}^n a_{kj} = \sum_{j=1}^n a_{ki} = 1, $$ and analogously for $\sum_{i=1}^n b_{ij}$.

0
On

Just prove it from the definition: You have that $[A^TA]_{ij}=\sum_{k}a_{ki}a_{kj}$. To show it's (column) stochastic you need the column-sum to be 1:

$$\sum_{j=1}^n [A^TA]_{ij}=\sum_j\sum_{k}a_{ki}a_{kj}=\sum_k\sum_ja_{ki}a_{kj}=\sum_k a_{kj}\cdot 1=1.$$

0
On

I'm not sure I follow what you're trying to prove from which assumptions; I'll assume that the aim is to show that $A^TA$ is doubly stochastic if $A$ is doubly stochastic. You've already shown that since $A^TA$ is symmetric it suffices to show that it is right stochastic. Being right (left) stochastic means having the vector $e$ with all entries $1$ as a right (left) eigenvector with eigenvalue $1$. We have

$$A^TAe=A^Te=(e^TA)^T=(e^T)^T=e\;,$$

where the first equality holds because $A$ is right stochastic and the third one holds because $A$ is left stochastic.