# Questions tagged [stochastic-matrices]

A right stochastic matrix is a nonnegative square matrix with each row summing to 1. A left stochastic matrix is a nonnegative square matrix with each column summing to 1. A doubly stochastic matrix is both right stochastic and left stochastic.

84 questions
Filter by
Sorted by
Tagged with
31 views

### How does Pagerank iteratively calculate an eigenvector?

I understand that Pagerank works by finding the eigenvector $\lambda$ to the eigenvalue $\epsilon=1$ of a Markov matrix $A \in \mathbb{R}^{n \times n}$. And, as far as I know, the iterative algorithm ...
18 views

### Relationship between the minimal singular value and the matrix size of a stochastic matrix

I have done some numerical experiments. Given a stochastic matrix $A$, the smallest singular value decreases sharply as the matrix size increases. I just want to know whether there are some analyses ...
36 views

### What is the steady state of a stochastic matrix if it has two linearly independent eigenvectors corresponding to the eigenvalue $1$?

A stochastic matrix $A$ is a matrix with the following two properties: All entries of $A$ are $\geq 0.$ All columns of $A$ add up to $1$. It is known that for a stochastic matrix, $\lambda = 1$ is ...
32 views

76 views

60 views

### Eigenvector of stochastic matrix

$P$ is stochastic matrix, $v$ is stochastic vector, $\frac{1}{n}(v + vP + vP^{2} + \cdots + vP^{n}) \to u$. Prove that $uP = u$. I understood that I need to show that u is eigenvector with eigenvalue ...
26 views

I have a problem for which the Markov matrix turns out to be the following: P = \begin{pmatrix} 0 & 0.5 & 0 & 0.5\\ 0.5 & 0 & 0.5 & 0 ... 2answers 45 views ### Eigenvalues of a special stochastic matrix I'm trying to find an explicit formula of all the eigenvalues for the following n by n stochastic matrix (sum of each row/column is one): \begin{bmatrix}0&\frac{1}{n-1}&\frac{1}{n-1}&... 1answer 23 views ### Special non-negative matrix decomposition Assume we have the following decomposition: M=AWA^T Where: M is non-negative symmetric (i.e. M_{i,j}\ge{0} and M_{i,j}=M_{j,i}) A is right stochastic (entries are non-negative and rows ... 1answer 29 views ### Two Primitive Stochastic Matrices with Eventually Equal Sequence of Powers Let A and B be two n\times n primitive row-stochastic matrices. That is, all of their entries are non-negative, all the rows sum up to 1, and there is an integer p\geq 1 such that all the ... 1answer 41 views ### Prove that the set of doubly stochastic 3 \times 3 matrices is a polyhedron Let B_3 be the set of 3 \times 3 matrices M with non-negative entries whose rows and columns all add up to 1. Show that B_3 is a polyhedron. Hint: represent a matrix M as a vector x in \... 0answers 92 views ### How can one make a periodic Markov chain aperiodic with the smallest change in the main structure of the chain? Or, how can one "deform" a stochastic, irreducible, periodic matrix into a stochastic, irreducible, aperiodic matrix with the smallest change? If there are several possible procedures, then please ... 1answer 89 views ### Eigenvalues of stochastic matrices A stochastic matrix is a real n\times n square matrix with nonnegative coefficients such that every row sums to 1. It is well known that 1 is an eigenvalue every stochastic matrix, the complex ... 0answers 28 views ### Diagonalizablity of a substochastic matrix Let D+E be a stochastic matrix i. e., D+E be the matrix with each row sum 1, where D and E are non-zero nonnegetive, irreducible matrices, I-D being non-singular. Can it be proved that D+kE is ... 1answer 61 views ### Spectral radius of a row-stochastic matrix plus a certain diagonal matrix Conjecture: Let A be a 4 \times 4 row-stochastic, primitive matrix. Let p_{i} be four probabilities such that p_1 + p_2 + p_3 + p_4 = 1. Let \begin{align} V &= \text{diag}_i\{p_{i + 1} + ... 0answers 83 views ### A “softmax”-like function for deciding on a partition Softmax can be derived as follows. Say that we are given k "log priors" b_i that our data belongs to the ith category in some categorical distribution. Then we can solve for the category ... 0answers 44 views ### If A and B are transition matrices such that ||A-B|| < c, then what can we say about ||A^n-B^n|| for a given n? Suppose there are two matrices, A and B, that are both transition matrices for a Markov chain (n\times n, non-negative and row-stochastic). I know that A and B are "close" in the sense that ||A-... 0answers 69 views ### Proving that a doubly stochastic matrix is a convex combination of permutation matrices [duplicate] This is a homework problem in my graph theory class and I wanted tips on how to solve it. Any tips would be appreciated.. Show that any doubly stochastic matrix is a convex combination of ... 0answers 37 views ### Proving that a matrix is nonnegative if its powers are nonnegative I am working on a problem involving doubly stochastic matrices where I must prove that P is doubly stochastic if and only if P^k is doubly stochastic for k = 1, 2, ... It is easy to show that if ... 1answer 31 views ### Does always a B with orthonormal rows/column be found so that BP=0? I am given, P_{n\times n} column stochastic, I need to see whether a matrix of suitable order B with an orthonormal column or rows can be constructed so that BP=0? I started trialing like this: ... 2answers 306 views ### Every finite state Markov chain has a stationary probability distribution I am trying to understand the following proof that every finite-state Markov chain has a stationary distribution. The proof is from here. Let P be the k \times k (stochastic) transition ... 1answer 50 views ### tensor product of two column stochastic matrix [closed] Is the tensor product of two column/row stochastic matrix is again a column/row stochastic? Thanks for helping. 1answer 171 views ### Perron Frobenius Theorem modified On this site I found a modified version of Perron Frobenius Theorem Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then: 1 is an eigenvalue of multiplicity one. 1 is ... 1answer 157 views ### How many positive eigenvalues for a symmetric doubly stochastic matrix? one interesting question is here about spectrum of symmetric doubly stochastic matrix. Given matrix A\in R^{n \times n}, which is a symmetric doubly stochastic matrix. and its spectrum is \... 0answers 16 views ### Ordering in \mathbb{R}^n and its representation in terms of stochastic matrix Let \mathbf{x},\mathbf{y} \in \mathbb{R}^n. We say that \mathbf{x} \leq \mathbf{y} iff x_{(1)} \geq y_{(1)}, x_{(1)}+x_{(2)} \geq y_{(1)}+y_{(2)},\cdots,x_{(1)}+\cdots+x_{(n-1)} \geq y_{(1)}+\... 2answers 117 views ### Prove that : There exists a vector x such that Mx = x , where M is a Markov matrix [closed] Here's a proof that I found which looks pretty simple but I can't understand the last step. (A Markov matrix is a square matrix whose columns sum to one; I is an identity matrix; M^T and I^T ... 1answer 97 views ### Maximum column sum of stochastic matrix For a stochastic matrix P of size n, we define\|P\|_1 := \max_{j \in [n]} \sum_{i \in [n]}|P(i,j)|i.e., the maximum column sum, which is based on the \|\cdot\|_1 matrix norm. Now, ... 1answer 208 views ### Is the Birkhoff–von Neumann theorem true for infinite matrices? The Birkhoff–von Neumann theorem states that every n \times n doubly stochastic matrix is a convex combination of permutation matrices. Is this true for \mathbb{N} \times \mathbb{N} matrices as ... 1answer 274 views ### Cesàro limit of a stochastic matrix Let A be a stochastic matrix. Then \begin{align*} \lim_{t \rightarrow\infty} A^t \end{align*} may not exist. For example: \begin{align*} A &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}... 1answer 320 views ### Examples of stochastic matrices that are also unitary? In general there is no relationship between stochastic matrices and unitary matrices because they are used in different fields. The stochastic matrix presents all the non-negative elements with sum ... 0answers 94 views ### Decompose stochastic matrix in product of two stochastic matrices There exist stochastic matrices Q such that there is no stochastic matrix P such that P^2=Q. I am interested in the following problem: For a given stochastic matrix Q, find stochastic ... 2answers 638 views ### Proving product of two column stochastic matrices is column stochastic (Proof verification) For a matrix to be column stochastic we know \sum_{i=1}^nA_{ij}=1 for each column j\in\{1,\ldots,n\}. We have\sum_{j=1}^n (AB)_{ji} = \sum_{j=1}^n \sum_{k=1}^n A_{jk}B_{ki} = \sum_{j=1}^nA_{jk} ...
Let $P$ and $Q$ be two stochastic matrices. Does the product $PQ$ have to be stochastic? Prove or disprove. What Im thinking is that since matrix multiplication is only defined for two matrices $A$ ...