Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
23 views

Eigenvalues of dense vs. sparse stochastic matrix

For a stochastic matrix $A$, it is known that the maximum eigenvalue is $1$ and that each eigenvalue $\lambda_i$ satisfies the inequality: $|\lambda_i| \leq 1$. Given a dense (and possibly symmetric)...
1
vote
0answers
39 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-...
1
vote
0answers
56 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 ...
1
vote
0answers
31 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 ...
0
votes
1answer
28 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: ...
2
votes
2answers
103 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 ...
0
votes
1answer
25 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.
1
vote
0answers
15 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)}+\...
0
votes
2answers
71 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$ ...
1
vote
1answer
56 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, ...
3
votes
1answer
142 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 ...
4
votes
1answer
127 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}...
2
votes
1answer
116 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 ...
2
votes
0answers
65 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 ...
3
votes
2answers
240 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} ...
2
votes
2answers
793 views

Proving or disproving product of two stochastic matrices is stochastic

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$ ...
0
votes
2answers
46 views

Stochastic matrix question

A stochastic matrix is one which each column sum equal one. $$P= \begin{bmatrix} P_{11} & P_{12} & \ldots & P_{1N} \\ P_{21} & P_{22} & \ldots & P_{2N} \\ \ldots & \ldots ...
2
votes
1answer
82 views

Possible Jordan decompositions of stochastic matrices

Which are the possible Jordan normal forms for the stochastic matrices? For some reason I got the idea that they always consist of trivial $1\times 1$ blocks even if eigenvalues of multiplicity $>1$...
2
votes
1answer
273 views

When are the inverses of stochastic matrices also stochastic matrices?

A stochastic matrix, with elements $\in[0,1]$ and rows summing to 1 are known to have one eigenvalue 1 (stationary distribution) and the rest of lower magnitude. However I don't know about many ...
0
votes
1answer
72 views

What are Markov matrices and can they be used to model migration?

I have been looking at Markov matrices and have been having some difficulty getting my head around them. I was wondering if someone could explain to me in somewhat simple manners how they work. Also, ...
1
vote
1answer
189 views

Eigenvalue of stochastic matrix [duplicate]

Why is the eigenvalue of a stochastic matrix always $1$? I have found lots of articles simply saying it is obvious that the eigenvalue is $1$ but can't get my head around the proofs.
0
votes
2answers
284 views

Is the convex combination of stochastic matrices also stochastic?

Let's say we have two stochastic matrices $S$ and $A$. How can I show that $M$ is also stochastic when $M$ is given by?: $M = (1-m)A + mS$ EDIT 1: $m \in \ \mathbb{R} : 0 < m < 1$
2
votes
1answer
123 views

Doubly stochastic matrices as linear combinations of permutation matrices

For a doubly stochastic matrix ($n \times n$) that is a linear combination of $N$ permutation matrices, how do we prove that $N = (n - 1)^2 + 1$ suffices?
0
votes
1answer
54 views

Preposition about the Entries of the Product of Markov Matrices.

Definition: A Markov matrix is an $n \times n$ complex matrix with the sum of the elements in every column equal to 1. My task is to prove that: If A, B are Markov matrices such that $|a_{ij}|\leq1$ ...
2
votes
1answer
664 views

Eigenvector corresponding to eigenvalue $ 1 $ of a stochastic matrix

I am trying to justify fact $ 5 $ in this link which states that if $ A $ is a column stochastic matrix, then $ A $ has eigenvalue $ 1 $ and a unique eigenvector such that all entries are either ...
4
votes
0answers
62 views

Skew-symmetric parts of stochastic matrices

It's easy to see that the set $\{W - W^T : W \in \mathbb{R}^{n \times n}\}$ is precisely the set of real skew-symmetric matrices. This continues to be the case if we restrict to (entry-wise) non-...
0
votes
1answer
63 views

Parameterise doubly stochastic matrices

Given the set of doubly stochastic matrices of dimension $n$, $D$, is it possible to find a continuous bijective mapping $f: \mathbb{R}^i \to D$ for $i \leq n^2$. The motivation is to be able to ...
0
votes
0answers
121 views

Orthogonality of stochastic matrix

Given a column stochastic matrix $P$, I wanted to give a relation between $\|P\|$ and orthogonality of $P$. One simple way to think about how close $P$ is to being orthogonal is $\|P^{\top}P - I\|$. ...
4
votes
1answer
309 views

Sinkhorn theorem for doubly stochastic matrices

I was reading something about doubly stochastic matrices and got stuck while reading the original proof of the uniqueness part of the Sinkhorn theorem. I'm not able to understand the logic. Could ...
0
votes
0answers
211 views

Diagonalization of Markov matrices

If we're given a $ \displaystyle 2 \times 2 $ Markov matrix (so all entries are non-negative and columns add to 1) M$(a,b)$ such that $$M = M(a,b) := \begin{bmatrix}1 - a & b\\a & 1 - b \end{...
0
votes
1answer
170 views

Finding eigenpairs for Markov matrices

If we're given a $ \displaystyle 2 \times 2 $ Markov matrix (so all entries are non-negative and columns add to 1) M$(a,b)$ such that $$M = M(a,b) := \begin{bmatrix}1 - a & b\\a & 1 - b \end{...
0
votes
1answer
369 views

Do the matrices representing Markov chains need to be square?

I assume so — I ask in the context of defining an irreducible set. If a set is non-irreducible, you should be able to find a "smaller" Markov chain matrix nested within a larger one. That "smaller" ...
6
votes
0answers
108 views

Birkhoff representation of a stochastic matrix

From the Birkhoff theorem, it is known that every doubly stochastic matrix can be written as a convex combination of permutation matrices, although this representation might not be unique. Assume ...
0
votes
1answer
104 views

Diagonalization of stochastic matrices

Can a stochastic matrix be written as $V^{-1} D V $? V is an invertible matrix and D is diagonal. I think so but I can't think of a good proof. Also, the left eigenvectors and right eigenvectors are ...
2
votes
0answers
544 views

Decomposing a stochastic matrix into a product of stochastic matrices

It is well-known that any square real matrix of small rank $k$ can be decomposed into a product of a skinny matrix with $k$ columns and a fat matrix with $k$ rows by means of an SVD. This question is ...
1
vote
0answers
46 views

Birkhoff-Neumann like result for stochastic matrices?

During my research, I came along a nice lemma which looks like a Birkhoff-Neumann-theorem result, but in a version for stochastic matrices. Namely, I have: Lemma. Let $M$ be a stochastic matrix, then ...
2
votes
1answer
2k views

Inverse of a regular stochastic matrix

Is it true that the inverse of a regular stochastic matrix is also regular? Are there any other interesting features that the inverse may have of a regular stochastic matrix? Hope someone could ...
0
votes
1answer
603 views

Stochastic matrix problem

A (left) stochastic matrix is one which has only non-negative entries, and such that the entries in each column sums up to $1$. Let $A$ be any (general) $2 \times 2$ stochastic matrix. a) Show ...
1
vote
1answer
2k views

Proof that the square of a stochastic matrix is stochastic

We know that the square of a stochastic matrix is also stochastic, because the two-step transition matrix of a Markov chain is necessarily stochastic. However, in there another way to independently ...
2
votes
2answers
96 views

Question on MIT video on Markov matrices

Markov matrices are pretty new to me and I'm a little rusty with my linear algebra. My question stems from watching this video from YouTube on Markov matrices. For those who wish to skip the video, ...
17
votes
1answer
877 views

Eigenvalues for $3\times 3$ stochastic matrices

This is a plot of the non-real eigenvalues of $10^4$ randomly generated $3\times3$ stochastic matrices. It's pretty clear that they lie in the convex hull of the three cube roots of unity. The ...
3
votes
2answers
5k views

Is it true that for any square row-stochastic matrix one of the eigenvalues is $1$?

I have a stochastic matrix $A \in R^{n \times n}$ whose sum of the entries in each row is $1$. When I found out the eigenvalues and eigenvectors for this stochastic matrix, it always happens that one ...
45
votes
5answers
24k views

Proof that the largest eigenvalue of a stochastic matrix is $1$

The largest eigenvalue of a stochastic matrix (i.e. a matrix whose entries are positive and whose rows add up to $1$) is $1$. Wikipedia marks this as a special case of the Perron-Frobenius theorem, ...
8
votes
1answer
4k views

No solutions to a matrix inequality?

Let $A$ be a stochastic matrix. Thus $A$ has nonnegative entries, and the sum of the elements in each row is 1. This implies that the vector $\begin{bmatrix} 1 & 1 & \cdots & 1 \end{...
5
votes
3answers
2k views

Duality with a stochastic matrix

If I have a stochastic matrix $X$- the sum of each row is equal to $1$ and all elements are non-negative. Given this property, how can I show that: $x'X=x'$ , $x\geq 0$ Has a non-zero solution? ...