Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a symmetric stochastic matrix, such that the sum over the columns, for each row, is 1, and all elements are positive. $A$ dimensions are $n \times n$

Let's say that $B$ is a matrix which is not necessarily of the same column and row dimension, $B$'s dimensions are $n \times m$.

We also have the property for $B$, like $A$, that all elements are positive, and the sum over columns is 1.

What can we say about the product $A \times B$? What if we continuously apply $B_{t+1} \leftarrow A \times B_t$ where $B_1 = B$? Is there anything I can read about?

Any clues appreciated. Thanks.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Firstly, note that if $A$ is row-stochastic (i.e. the sum across columns is equal to 1 for every row and the entries are non-negative) and symmetric then it must also be column-stochastic, hence doubly stochastic. Also, since the entries are positive, the Perron-Frobenius Theorem would be very useful here. Basically, the matrix $A$ represents a discrete time Markov chain with a finite state space, and understanding the effect of repeatedly multiplying $B$ by $A$ requires an understanding of whether the following limit exists: $\lim_{t \to \infty} A^t$. This is a well-studied problem in the theory of Markov Processes (coming from results in linear algebra), and the answer is that if the matrix is irreducible and aperiodic (equivalently, if there exists some $k$ such that for all $m > k$, $A^k$ has all positive entries) then this limit exists.

Given that in this case $A$ has all positive entries, the infinite product of the matrix will have a limit, which is a matrix with identical rows $s$ given by the equation: $sA = s$. In other words, the limiting matrix $\lim_{t \to \infty} A^t$ is the $n \times n$ matrix with every row equaling the left eigenvector associated with the eigenvalue 1.

So, as you multiply $B$ repeatedly, you will find that $B_t$ will converge to a matrix with identical rows, where the entry in column $i$ is a weighted average of the column $i$ of $B$, with weights given by $s$.

A great reference for you would be Carl Meyer's book Matrix Analysis and Applied Linear Algebra. Alternatively, you'll find the essence of what you need in the following journal article's appendix: Jackson, Golub - Naive Learning in Social Networks and the Wisdom of Crowds

share|improve this answer

I assume that when you say that for $B$ the "sum over the columns equals $1$," that means that the sum of the elements in each column of $B$ is $1$. Is that right?

In that case, the answer is that the iteration $B(t+1) = A B(t)$ will converge, in the limit as $t \rightarrow \infty$, to a matrix whose every entry is $1/n$.

To prove this, it suffices to show that for any vector $v(0)$ the iteration $$ v(t+1) = A v(t)$$ converges to a vector whose every entry is the average of the vector $v(0)$.

Note that a positive stochastic matrix will have a single eigenvalue at $1$, and every other eigenvalue will have magnitude strictly less than $1$. Moreover, the eigenvalue $1$ will be associated with the all-ones eigenvector, which I'll denote by ${\bf 1}$. Thus the limit $\lim_t A^t v(0)$ will be a multiple of ${\bf 1}$, i.e. a vector $c {\bf 1}$ for some number $c$ ( to see this, note that because $A$ is symmetric, it has a set of orthogonal eigenvectors; expand $v(0)$ in the basis of these eigenvectors, and look at what multiplication by $A$ does). Next, we must figure out what $c$ is; observe that by symmetry of the matrix $A$, multiplication by the matrix $A$ preserves the sum of the entries of a vector $$ \sum_{i=1}^n (Ax)_i = {\bf 1}^T A x = (A {\bf 1})^T x = {\bf 1}^T x = \sum_{i=1}^m x_i,$$ which tells you that the constant $c$ must be the average of the entries of $x(0)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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